Depeng's Blog for Algorithms

卢德鹏的算法刷题札记


  • 首页

  • 归档

  • 分类

  • 标签

  • 搜索

排序(5) 鸡尾酒排序

发表于 2019-04-01 | 分类于 Sorting | 阅读次数:

冒泡排序已经对算法进行有优化,但仍然不是最优。鸡尾酒排序又叫快乐小时排序,它基于冒泡排序又做了一点优化。博客中给出了鸡尾酒排序的优化版本。

阅读全文 »

排序(4) 冒泡排序

发表于 2019-04-01 | 分类于 Sorting | 阅读次数:

冒泡排序算法多次遍历数组,在每次遍历中连续比较相邻的元素,如果元素没有按照顺序排列,则互换他们的值。 博客中先给出了朴素版本,再给出了优化了每一轮内循环结束点(减少遍历轮次)的needNextPass版本和isSorted版本,还有进一步优化判断边界的sortBorder版本,sortBorder版本为最优化版本。

阅读全文 »

排序(3) 希尔排序

发表于 2019-04-01 | 分类于 Sorting | 阅读次数:

希尔排序又叫缩小增量排序,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。 希尔排序是对插入排序的优化,基于以下两个认识:1.数据量较小时插入排序速度较快,因为n和n²差距很小;2.数据基本有序时插入排序效率很高,因为比较和移动的数据量少。 希尔排序的时间复杂度和增量的选择策略有关,博客中的选择策略会导致排序的不稳定性。

阅读全文 »

排序(2) 插入排序

发表于 2019-04-01 | 分类于 Sorting | 阅读次数:

插入排序重复地将新的元素插入到一个排好序的子线性表中,直到整个线性表排好序。 遍历数组,遍历到i时,a0,a1,…,ai-1是已经排好序的,取出ai,从ai-1开始向前和每个比较大小,如果小于,则将此位置元素向后移动,继续先前比较,如果不小于,则放到正在比较的元素之后。可见相等元素比较是,原来靠后的还是排在后边,所以插入排序是稳定的。 当待排序的数据基本有序时,插入排序的效率比较高,只需要进行很少的数据移动。

阅读全文 »

排序(1) 选择排序

发表于 2019-04-01 | 分类于 Sorting | 阅读次数:

选择排序是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 遍历数组,遍历到i时,a0,a1,…,ai-1是已经排好序的,然后从i到n选择出最小的,记录下位置,如果不是第i个,则和第i个元素交换。此时第i个元素可能会排到相等元素之后,造成排序的不稳定。

阅读全文 »

剑指Offer(9) 用两个栈实现队列

发表于 2019-03-29 | 分类于 剑指Offer | 阅读次数:

阅读全文 »

剑指Offer(8) 二叉树的下一个节点

发表于 2019-03-28 | 分类于 剑指Offer | 阅读次数:

阅读全文 »

剑指Offer(7) 重建二叉树

发表于 2019-03-27 | 分类于 剑指Offer | 阅读次数:

阅读全文 »

剑指Offer(6) 从尾到头打印链表

发表于 2019-03-26 | 分类于 剑指Offer | 阅读次数:

阅读全文 »

剑指Offer(5) 替换空格

发表于 2019-03-24 | 分类于 剑指Offer | 阅读次数:

阅读全文 »
1…12131415
Depeng Lu

Depeng Lu

学会给自己找事,不要总闲下来;学会总结和反思,过一段时间,停下来总结得失;执行力比你的目标更重要,贯彻执行力,不要三天打鱼两天晒网

147 文章
21 分类
73 标签
RSS
GitHub E-Mail Weibo
神奇的链接
  • Fan Wu
  • Song Ba
  • Depeng Official Website
  • 尼古拉·特斯拉:发明了现代世界的人
  • 意味深长的叹息
  • 舐め犬本物のお香
  • 2015年8月“318川藏线”骑行学长博客(初生牛犊)
© 2018 — 2019 Depeng Lu | Site words total count: 144.1k
微信扫一扫,加我好友
0%