收藏到CSDN网摘
归并排序(Merge sort)是另外一个很有名的排序算法.其思想是: divide and conquer.将原序列分割为2个小序列,排序之后再merge到一起.分割部分可以递归完成,递归出口是序列长度为1,直接返回序列.
Bottom_Up归并排序是归并排序的非递归实现,从size=2开始,不断merge,直到所有元素排序完毕.
快速排序(Quick sort)是对随机打乱后的数组,用2个指针分别从左边和右边来扫描元素,在排序过程中保证:对某个元素j,a[j]已经被排好,其左边所有元素都不大于它,而右边所有元素都不小于它.j这个位置由分割函数partition()返回.具体实现(随机排序可以不用,用median-3来选择一个元素作为a[lo]即可):
(a) partition分割(设置j)
i, j = lo, hi, 当i<j时,repeat:
- i从左往右scan,只要a[i]<a[lo],扫描停止时,a[i]>=a[lo]
- j从右往左scan,只要a[j]>a[lo],扫描停止时,a[j]<=a[lo]
- 交换a[i]与a[j]
- 循环结束后交换a[lo]与a[j].
- 返回j
(b) 递归调用排序lo到j-1
(c) 递归调用排序j+1到hi
3-way快速排序是对快速排序的改进,因为快速排序算法的扫描方法在有多个与a[lo]相当的元素时,仍然需要交换元素(非必要交换),因此,可以引入lt和gt2个元素,来保证lt-gt之间的元素都等于v,lt左边不大于v,gt右边不小于v.具体实现:
(a): partition分割(同时设置lt与gt)
lt = lo, gt = hi, i = lo, v = a[lo]
选择v作为partitioning元素a[lo](可与快速排序选择方法相同)
i从左往右开始扫描:
- a[i]<v: 交换a[lt]与a[i], lt++, i++
- a[i]>v: 交换a[gt]与a[i], gt--
- a[i]==v: i++
(b) 递归调用排序lo到lt-1
(c) 递归调用gt+1到hi
python实现如下(包含
上次写过的希尔排序,插入排序与选择排序):
