希尔、归并、堆、快速排序

下面我们介绍一下时间复杂度为O(nlogn)的时间复杂度:希尔排序、归并排序、堆排序、快速排序

堆排序

  1. 将0~(n-1)的无序列表,映射为大根堆,根据大根堆的特性,堆顶为最大值;

  2. 将堆顶与堆的最后一个元素交换位置,并将其脱离堆结构,放在数组n-1位置上;

  3. 重新调整大根堆,重复步骤2,得到第n-2的数

  4. 直到堆元素个数为1,即整个堆排序完成。

图解流程访问下面链接中的 Data Structure Visualizations

希尔排序

希尔排序是插入排序的进化版,插入排序的每次迁移步长为1,而希尔排序则通过动态调整步长,进而提高排序效率。假如选定步长为3下面说一下排序过程

  1. 在0~(N-1)的无序序列中,数组中位置0、1、2三个数将被直接跳过。取3位置的数(a)和0位置上的数(b)比较。如果b>a,则结束比较;如果b<a,则交换b和a的位置,继续使用b和-3位置上的数比较,发现-3数组越界,结束比较;

  2. 取位置4上的数和位置1上的数比较,重复上面过程;

  3. 一直到最后一个位置n与n-3比较后结束步长为3的排序过程;

  4. 让步长减1继续完成上面1、2、3的步骤,知道步长=0,结束整个希尔排序过程;

图解流程访问下面链接中的Shell Sort Data Structure Visualizations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void sort(Comparable[] a) {

// 希尔排序其实是插入排序的一种优化
int len = a.length;
int w = 1;

// 自定义w的规则
while(w < len / 3) {
w = 3*w + 1;
}

//开始进行排序
while(w >= 1){
for(int i = w ; i < len ; i ++){
// 将a[i]插入到a[i-w]、a[i-2*w]、a[i-3*w]....
for (int j = i ; j >= w && less(a[j],a[j-w]) ; j -=w ){
exch(a,j,j-w);
}
}
w = w / 3;
}
}

归并排序

  1. 在0~(n-1)的无序列表中,将大小为1的有序区间,合并为大小为2的有序区间;

  2. 将大小为2的有序区间合并为大小为4的有序区间;

  3. 直到有序区间大小容纳所有的数,归并排序完成;

图解流程访问下面链接中的Merge Sort Data Structure Visualizations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static Comparable[] aux;

public void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a,0,a.length-1);
}

// 自上而下的归并排序
public void sort(Comparable[] a,int lo,int hi) {

if(hi <= lo) {
return;
}
// a[lo...mid] 和 a[mid+1....hi]
int mid = lo + (hi - lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);

}

// 合并 a[lo...mid] 和 a[mid+1....hi]
public void merge(Comparable[] a, int lo, int mid, int hi) {

// 初始化两个指针
int i = lo;
int j = mid + 1;

// 将a复制到辅助数组aux
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// 开始拿两个指针对应的数进行比较
for (int k = lo; k <= hi; k++) {
// j对应的数 比i小,将比较小的放在第k位置
if(j > hi){
a[k] = aux[i++];
}else if(i > mid){// 如果左边用完了,直接将右序列中的数放在k位置
a[k] = aux[j++];
}else if(less(aux[j],aux[i])){ // 如果右边用完了,直接将左序列中的数放在k位置
a[k] = aux[j++];
}else{
a[k] = aux[i++];
}
}
}

快速排序

利用分治的思想,要对大小为N的无序序列排序,将其分为a[lo]-a[j-1],a[j],a[j+1]-a[hi]三部分,保证a[lo]-a[j-1]中的数永远小于等于a[j];a[j+1]-a[hi]中的数永远大于a[j];

在分别递归的对a[lo]-a[j-1]和a[j+1]-a[hi]重复上面的步骤。

下面我们说一下什么叫划分过程,划分过程就是怎么将小于等于a[j]的数放到a[j]的左边,大于a[j]的数放在了a[j]的右边:

  1. 选择一个数a[lo],初始化左指针 i = lo ,右指针 j = hi;

  2. i指针往右移,找到大于等于a[lo]的数(a);j指针往左移,找到小于a[lo]的数b。交换a和b的位置,然后i继续往右移,j继续往左移,直到两者交汇。

  3. 将a[lo]与a[j]交换位置

图解流程访问下面链接中的Quick Sort Data Structure Visualizations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public void sort(Comparable[] a) {
sort(a,0,a.length-1);
}

// 快速排序
public void sort(Comparable[] a,int lo ,int hi) {

if(hi <= lo) {
return;
}
// 找到j,分别对a[lo..j-1]和a[j+1...hi]进行递归快速的排序
int j = partition(a,lo,hi);
// sort左序列\ sort右序列
sort(a,lo,j-1);
sort(a,j+1,hi);
}

// 对a[lo...hi] 进行划分排序
public int partition(Comparable[] a, int lo, int hi) {
// 定义两个指针
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while(true){
// 从左边往右边一直找到第一个比v大的数
while(less(a[++i],v))if(i == hi)break;
// 从右边往左边一直找到第一个比v小的数
while(less(v,a[--j]) )if(j == lo)break;
if(i >= j) break;
exch(a,i,j);
}
// 比较完成后将j和lo位置上的数互换
exch(a,lo,j);
return j;
}