网罗各种排序算法

2017年3月6日21:29:26 2 353

 网罗各种排序算法

 

插入排序

插入排序思路:
  1. 插入排序有两层循环,外层循环控制遍历数组。end 指向有序区间的末尾,tmp 保存有序区间下一个位置的值。
  2. 内层循环条件: end >= 0 保证 end 指向下标合法;a[end] > tmp 说明有序区间末尾的值大于 tmp 。所以循环内部把 end 位置的值向后移动,并且 --end。
  3. 内层循环退出后,由于最后一次循环把 end 移到 end+1 处,并且 --end ,此时原来 end 的位置就是空位,也就是现在的 end+1 处,所以把 tmp 的值放到现在的 end + 1处。

插入排序 - 希尔排序

希尔排序思路:
  1. 希尔排序是先进行间距为gap的预排序,而且每次预排序间距gap都在缩小,gap 等于 1 时就是普通的插入排序,每次预排序都让数组更接近有序。
  2. 希尔排序主要有两层循环,最外层循环条件 gap > 1控制间距,进入循环先 gap = gap / 3 + 1 ,加1的目的是最后一次间距gap等于1的最终插入排序。
  3. 第二层循环,控制多区间的同时插入排序,循环内就是间距为 gap 的插入排序。

选择排序

选择排序思路:
  1. 选择排序有两层循环,外层循环通过 end 缩小选择的区间, maxIndex 用来标记所选区间里最大值的下标。
  2. 内层循环从 0 到 end 区间里选出最大值。
  3. 内层循环结束后,把选出的最大值和end交换。

选择排序优化1:

优化1思路:
  1. left 和 right 两边同时向里移动,每次在所选区间里同时选出最小值和最大值,最小值和 left 交换,最大值和 right 交换。left指向数组0下标,right指向数组末尾。
  2. 外层循环条件left < right保证区间大小最少为两个元素,并缩小区间大小。
  3. 内层循环遍历整个区间,选出最大值和最小值的下标。内层循环结束后,把区间内最小的值和left交换,(如果maxIndex等于left,由于前面left的值和minIndex的值交换了,所以maxIndex应该指向到minIndex)把区间内最大的值和right交换,最后++left,--right缩小区间。

选择排序思路2:

思路2:(大量swap,效率并不高,所以不推荐)
  1. left 和 right 两边同时向里移动,每次在所选区间里把比 left 里小的值和 left 交换,把比 right 里大的值和 right 交换。left指向数组0下标,right指向数组末尾。
  2. 外层循环条件left < right保证区间大小最少为两个元素,并缩小区间大小。
  3. 内层循环遍历整个区间,把比left小的值和left交换,比right大的值和right交换。内层循环结束后++left,--right缩小区间。

选择排序 - 堆排序

堆排序思路:
  1. 堆排序的主要思想还是选择排序,但是不一样的是每次从0到end区间选择一个最大元素的方法。
  2. 堆排序首先通过向下调整函数把整个数组建成一个大堆,建堆时从最后一个非叶子节点开始(最后一个节点的下标减1再除2)直到根节点0,每个节点都向下调整。
  3. 建好堆后,就是选择排序的思路。end指向要排的数组的最后位置,循环条件 end > 0 保证最少有2个元素,把第0个元素和当前区间的最后一个元素交换(a[0]是堆中最大元素),保证当前的最后一个位置的元素都是现在这个序列之中最大的。然后从0到end-1重新建堆,--end缩小选择区间。

交换排序

交换排序 - 冒泡排序

冒泡排序思路:

n个数需要排n-1趟比较,第i趟需要从前向后比较n-1-i次,把大的数向后交换,第i趟比较完了,如果没有交换过数,说明[0, n-1-i]区间已经有序。

交换排序 - 快速排序

递归快速排序

递归快速排序思路:

快速排序的思想就是分治法,PartSort函数可以把区间划分成三个部分,div左边的数都比div小,右边的数都比div大,并返回数组下标div。也就是说div位置的值已经放在了合适的位置,只要div的左边和右边都有序了,那么整个数组就有序了,解决这两个子问题就可以了整个大问题就解决了。子问题的区间如果比较大同样用快速排序的PartSort函数进行切割问题,反之,直接用插入排序同样可以解决子问题。

  1. 如果区间大小为1或交叉就return(递归结束条件);
  2. 如果区间大小小于等于某个值就进行插入排序;
  3. 否则,调用PartSort函数把这个区间划分成三个部分:[left, div - 1],div, [div + 1, right]。div左边的数都比div小,右边的数都比div大。并返回数组下标div;然后递归快速排序[left, div - 1]和[div + 1, right]

左右指针法

挖坑法

挖坑法和左右指针法思路基本一致。所谓的坑就是,保存过的值,原位置可以被覆盖

前后指针法

快速排序有两个优化的地方:

  1. 小区间优化(插入排序使小区间有序);
  2. 三数取中算法避免这样情况:在数组已经有序的情况下,每次划分将得到最坏的结果(递归的深度变深)

其中三数取中算法简单实现如下:

非递归的快速排序

上面实现了三种快速排序的方法和两处优化,接下来讨论一下快速排序如何非递归实现?

归并排序

归并排序思路:
  1. 合并排序借助一个同样大的临时数组,对整个区间合并排序。
  2. 区间小于2或交叉直接return(递归结束条件)。函数中对[left, mid]和[mid+1, right]两个区间递归地合并排序(分小区间),两个区间都有序了,合并有序区间。把a里[left, mid]和[mid+1, right]两个有序区间合并成一个有序区间,合并结果在tmp里。
  3. 把合并好的[left, right]有序区间拷贝回a数组对应的位置。

其中合并有序区间的代码如下:

非比较排序

非比较排序 - 计数排序

给定一组要排序的序列,找出这组序列中的最大值,然后开辟一个最大值加1大小的数组,将这个数组里面的元素全部置零,然后用这个数组统计出要排序的序列中各个元素出现的次数。等到统计完成的时候,排序就已经完成了。

计数排序思路:
  1. 找出待排序序列里的最大值max;
  2. 开辟一个大小为max+1的临时数组tmp ,将数组元素的所有初值赋为0;
  3. 遍历待排序序列,将序列中出现值作为下标,对tmp 数组的对应位置数据进行++;
  4. 上述操作完成后,tmp中统计了每个数据在待排序列中出现的次数;
  5. 最后,将tmp数组里值不为0的所有下标拷进原序列(注意同一个下标可能有多个重复值,都要进行拷贝,不能遗漏),排序就算完成。

计数排序适用于数据比较集中的序列排序

计数排序的优化:找出要排序的这组元素中的最大值和最小值,这样就确定了这组元素的范围,然后开辟这个范围加1大小的数组,然后再将要排序的元素映射到这个新开辟的数组中就可以了。

非比较排序 - 基数排序

如果数组里的数位数相差比较大,基数排序效率比较低

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:2   其中:访客  1   博主  1

    • avatar 请输入您的QQ号 2

      快排的左右指针法:当跳出while循环后,即此时begin==end,因为你key值是对数组最后一个元素值的拷贝,所以当你最后swap(a[begin], key)时,会把此时a[begin]的值拷给key,而key仅仅是拷贝,并不会再放回到原数组,这么解释不知道博主能理解我意思不

        • avatar 小小雷 Admin

          @请输入您的QQ号 楼主理解的很透彻,分析的很有道理,看完后让我大彻大悟,bug已经修复了