排序

排序

Posted by ZhengYang on 2016-08-29

排序算法

id 排序算法 最好情况 平均情况 最坏情况 空间 稳定性 方法 原地排序 备注
1 选择排序 $n^2$ $n^2$ $n^2$ $1$ 不稳定 选择 是 每次选最小的与第i个元素交换，是数据移动次数最少的算法，注意，但不是比较次数最少的算法
2 冒泡排序 $n$ $n^2$ $n^2$ $1$ 稳定 交换 是 从头开始每次确定一个最大的，冒泡到尾，然后数组量减一，继续冒泡
3 直接插入排序 $n$ $n^2$ $n^2$ $1$ 稳定 插入 是 像整理扑克牌
4 折半插入排序 $nlogn$ $n^2$ $n^2$ $1$ 稳定 插入 是 平均情况下比直接插入排序比较次数少，但元素移动次数不变；但在最好情况下，直接插入只比较一次，而折半比较logn次
5 希尔排序 $nlogn$ $nlogn$ or $n^{5/4}$ depands on gap, best known is $nlogn$ 1 不稳定 插入 是 时间复杂度需要通过gap确定
6 快速排序 $nlogn$ $nlog$ $n^2$ $logn$ 不稳定 切分 是 递归空间$logn$;头只移动一次，交换前后两个指针；头常移动，和两个指针来回交换；三向切分，用于重复多的数组
7 堆排序 $nlogn$ $nlogn$ $nlogn$ $1$ 不稳定 选择 是 从小到大排序，用大根堆
8 归并排序 $nlogn$ $nlogn$ $nlogn$ $n$ 稳定 归并 否 递归，自顶向下；慢慢合并，自底向上
9 基数排序 $d(n+k)$ $d(n+k)$ $d(n+k)$ $n+k$ 稳定 - 否 d表示位数，比如2，k表示进制，比如10。基数排序属于非比较算法，适用于整数，不适用于字符串

算法的选择

id 排序算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性 方法
n较小，无稳定型要求
1 选择排序 $n^2$ $n^2$ $n^2$ $1$ 不稳定 选择
n较小，有稳定性要求；整体有序
2 冒泡排序 $\mathbf n$ $n^2$ $n^2$ $1$ 稳定 交换
3 直接插入排序 $\mathbf n$ $n^2$ $n^2$ $1$ 稳定 插入
n较大，无稳定性要求，比较随机
6 快速排序 $nlogn$ $nlog$ $n^2$ $logn$ 不稳定 切分
n较大，无稳定性要求，比较有序
7 堆排序 $nlogn$ $nlogn$ $nlogn$ $1$ 不稳定 选择
n较大，有稳定性要求，比较有序，空间允许的情况下
8 归并排序 $nlogn$ $nlogn$ $nlogn$ $n$ 稳定 归并

原地排序：在排序输入数组时，只有常数个元素被存放到数组以外的空间中去。

1.选择排序

  1. 找到数组中最小的那个元素
  2. 将它和数组中的第一个元素交换
  3. 在剩下的元素中找到最小的元素，与第二个元素交换
  4. 如此往复。
1
2
3
4
5
6
7
8
9
10
11
public static void selectSort(Comparable<?>[] a){
    int N = a.length;
    for(int i=0; i<N; ++i){
        int min=i; // 最小元素的索引
        for(int j=i+1; j<N; ++j){
            if(less(a[j],a[min]))
                min = j;
        }
        exch(a, i, min);
    }
}

运行时间和输入无关，即不会因为初始有序而提高效率
如果已经是有序，那么是时间复杂度还是平方级的。
数据移动是最少的

2.冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 冒泡
// 一次冒泡，使得最大的元素跑到最后面
public static void bubbleSort(Comparable<?>[] a){
    int N = a.length;
    int flag = 1; // 标志，在排序中 0未排好
    for(int i=1; i<N; ++i){ // 排N-1次
        flag = 1; // 先默认已排好
        for(int j=0; j<N-i; ++j){// 第一次比较N-1次，第二次比较N-2次，第N-1次比较1次
            if(more(a[j],a[j+1])){
                exch(a, j, j+1);
                flag = 0;  // 如果交换了，则说明没排好
            }
        }
        if(flag == 1)
            break ;
    }
}

3.直接插入排序

下一个元素倒序与前面的元素一个个比较，插入到前面的合适位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 交换多次
public static void insertSort(Comparable<?>[] a){
    int N = a.length;
    for(int i=0; i<N; ++i){
        for(int j=i; j>0 && less(a[j],a[j-1]); --j){
            exch(a, j, j-1);
        }
    }
}
// 不交换元素，而是使较大元素向右移，设置一个index,最后插入到相对的合适位置
public static void insertSort2(Comparable<?>[] a){
    int N = a.length;
    for(int i=0; i<N; ++i){
        Comparable<?> t = a[i];
        int j = i;
        for(; j>0 && less(t,a[j-1]); --j){  // t 错写成 a[i]，a[i]变了
            a[j] = a[j-1];
        }
        a[j]=t;
    }
}

取决于初始的状态，如果已经是有序，那么是时间复杂度线性的。
插入排序对于部分有序的数组十分高效。

4.折半插入

下一个元素折半与前面的元素比较，插入到前面的合适位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void binsertSort(Comparable<?>[] a){
    int N=a.length;
    for(int i=1; i<N; ++i){
        Comparable<?> t = a[i];
        // 找出合适位置为m, 但最后的插值位置不是m，而是low或者high+1
        int low = 0;
        int high = i-1;
        int m = 0;
        while(low<=high){
            m = (low+high)/2;
            if(less(a[i],a[m])){
                high = m-1;
            }else{
                low = m+1;
            }
        }            
        // low到i-1向后移
        for(int j=i; j>low; --j){
            a[j] = a[j-1];
        }
        a[low] = t;
    }
}

5.希尔排序

缩小增量法排序

  1. 设置间隔值h，分成h个组，在组内排序，得到h个有序子数组
  2. 缩小h值，分成h个组，在组内排序，得到h个有序子数组
  3. 直到h<1，停止，得到有序数组

间隔的取法

General term(k>=1) Concrete gaps Worst-case time complexity
$\lfloor \frac{N}{2^k} \rfloor$ $\lfloor \frac{N}{2} \rfloor,\lfloor \frac{N}{4} \rfloor,…,1$ $O(N^2)$
$2^k-1$ 1,3,7,15,31,63,… $O(N^{3/2})$
$\frac{3^k-1}{2}$，且$\leqslant\lceil \frac{N}{3}\rceil$ 1,,4,13,40,121,… $O(N^{3/2})$
… … … 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void shellSort(Comparable<?>[] a){
    int N = a.length;
    int h = 0;
    while(h<N/3){
        h = 3*h+1;
    }
    while(h>=1){
        for(int i=h; i<N; ++i){
            // a[i] a[i-h] a[i-2h] ... 一组
            for(int j=i; j>=h && less(a[j], a[j-h]); j=j-h){
                exch(a, j, j-h);
            }
        }
        h=h/3;
    }
}

6.快速排序

v为头元素
从左边向右，发现第一个大于等于v的元素，
从右边向左，发现第一个小于等于v的元素
交换这两个元素，然后重复
直到左指针向右，指到右指针，右指针再向左一格
现在右指针<=左指针，右指针比v小，右指针与v交换

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 切分1
private static int partition1(Comparable<?>[] a, int low, int high){
    int i = low, j = high+1;
    Comparable<?> v = a[low];
    while(true){
        while(less(a[++i], v)){
            // i指向第一个大于等于v的索引  
            // 或者如果后面全都比v小，则指向high
            if(i==high)
                break;
        }
        while(less(v, a[--j])){
            // j指向第一个小于等于v的索引
            // 或者比后面的比v都大，指向low
            if(j==low)
                break;
        }
        if(i>=j) // 大于号必须存在
            break;
        exch(a, i, j);
    }
    exch(a, low, j);
    return j;
}
// 快排1
// 递归
public static void quickSort1(Comparable<?>[] a, int low, int high){
    if(high <= low)
        return;
    int j = partition1(a, low, high);
    quickSort1(a, low, j-1);
    quickSort1(a, j+1, high);
}
// 切分2
// 交换次数是切分1的两倍
private static int partition2(Comparable<?>[] a, int low, int high){
    int i=low, j=high;
    int res = 0;
    while(i<=j){
        while(less(a[i], a[j]))
            j--;
        exch(a, i, j);
        i++;
        if(i>=j){
            res = j;
            break;
        }
        while(less(a[i], a[j]))
            i++;
        exch(a, i, j);
        j--;
        if(i>=j){
            res = i;
            break;
        }
    }
    return res;
}
// 快排2
// 递归
public static void quickSort2(Comparable<?>[] a, int low, int high){
    if(high<=low)
        return;
    int j = partition2(a, low, high);
    quickSort2(a, low, j-1);
    quickSort2(a, j+1, high);
}
// 快排3
// 三向切分 快排
// 递归
public static void quickSort3(Comparable<?>[] a, int low, int high){
    if(high<=low)
        return;
    // 接下来找分解点，其实是分阶段
    int lt=low; // lt指向的是第一个与v相等元素
    int i=low+1; // i指向的是第一个与v不相等的元素
    int gt=high;
    Comparable<?> v = a[low];
    while(i<=gt){
        if(less(a[i],v)) // 如果a[i]小于v，那么交换i，lt，同时两个都++
            exch(a, lt++, i++);  
        else if(more(a[i],v))  // 如果a[i]比v大，那么交换i，gt，并且gt--，i不变
            // 从尾部重新换个元素，看看大于v否
            exch(a, i, gt--);
        else
            i++;
    } // 此时 [low,lt-1] < [lt,gt]=v < [gt+1,high]
    quickSort3(a, low, lt-1);
    quickSort3(a, gt+1, high);
}

7.堆排序

从小到大排序

  1. 构建大根堆。从最后一个非叶节点(k=N/2)开始sink(1,k)，直到根节点(k=1)
  2. 交换大根与最后一个节点，然后sink(1,–N)，直到 N=1
    本来堆排序，从1开始比较方便索引的比较，但为了和别的排序一致，所以也改从0开始。
    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
    // 堆排序 0开始
    // sink 部分
    private static void sink(Comparable<?>[] a, int k, int N){
        // k的子节点大于N终止，或k大于子节点终止
        // k 表示要下沉的索引
        // N 表示树的最后一个节点
        while(2*k+1<=N){   // 如果根为0，那它的左子节点为2*k+1
            int j = 2*k+1;
            if(j<N && less(a[j],a[j+1]))
                j++;
            if(!less(a[k],a[j])) // 只要不满足条件，终止下沉
                break;
            exch(a,k,j);
            k=j;
        }
    }
    // 堆排序 0开始
    // 从小到大排序，大根堆
    // 1. 构建大根堆。从最后一个非叶节点(k=N/2)开始sink(1,k)，直到根节点(k=1)
    // 2. 交换大根与最后一个节点，然后sink(1,--N)，直到 N=1
    public static void heapSort(Comparable<?>[] a){
        int N = a.length-1;  // 表示最后一个索引
        for(int k=(N-1)/2; k>=0; --k){
            sink(a,k,N);
        }
        while(N>0){
            exch(a,0,N--);
            sink(a,0,N);
        }
    }

8.归并排序 插入

两个子数组的归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static Comparable<?>[] aux; //辅助空间
public static void merge(Comparable<?>[] a, int low, int mid, int high){
    int i = low, j= mid+1;
    for(int k = low; k<=high; ++k){
        aux[k] = a[k];
    }
    for(int k=low; k<=high; ++k){
        if(i>mid)
            a[k] = aux[j++];
        else if(j>high)
            a[k] = aux[i++];
        else if(less(aux[i],aux[j]))
            a[k] = aux[i++];
        else
            a[k] = aux[j++];
    }
}

8.1自顶向下归并排序

递归归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 自顶向下归并
public static void topDownMergeSort(Comparable<?>[] a){
    aux = new Comparable[a.length];
    tdsort(a, 0, a.length-1);
}
// 自顶向下归并递归
public static void tdsort(Comparable<?>[] a, int low, int high){
    if(high<=low)
        return;
    int mid = (low+high)/2;
    tdsort(a,low, mid);
    tdsort(a,mid+1, high);
    merge(a,low, mid, high);
}

8.2自底向上归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 自底向上归并
public static void downTopMergeSort(Comparable<?>[] a){
    int N = a.length;
    aux = new Comparable[a.length];
    for(int sz = 1; sz < N; sz=sz+sz){
        for(int low = 0; low<N-sz; low=low+sz+sz){
            // 需要保证至少还有sz+1个
            merge(a, low, low+sz-1, Math.min(low+sz+sz-1, N-1));
            // 假如low为N-sz-1,那么low+sz-1=N-sz-1+sz-1=N-2,
            // 说明mid是倒数第二个元素，还有一个元素
        }
    }
}

9. 基数排序

前面的算法都是利用比较和交换，而基数排序则是利用分配和收集。
这种排序一般仅适用于整数类型的排序，对于字符串不适合。
LDS（least significant digit）低位优先
比如，15,13(a),7,13(b)。按个位排，13(a),13(b),15,7，接下来按十位排7,13(a),13(b),15 正确
MDS（most significant digit）高位优先
不能完全按照LDS的方式进行，比如，15,13(a),7,13(b)。按十位排，7,15,13(a),13(b)，接下来按个位排13(a),13(b),15,7 错误

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
47
48
49
50
51
52
53
54
55
// 基数排序
// 获取x这个数的d位数上的数字
// 比如获取123的1位数，结果返回3
// d为第几位
private static int getDigit(int x, int d) {
    int tmp = 1;
    while(d>0){
        tmp = tmp*10;
        d--;
    }
    return (x%tmp)/(tmp/10);
}
// 基数排序 LSD  先排个位  再排十位
public static void radixSortLSD(Comparable<?>[] a, int d){
    // d 表示位数，比如99，则k=2
    // k 表示进制，比如k=10 ，k个桶
    int N = a.length;
    final int k = 10;
    int[] count = new int[k];
    Comparable<?>[] bucket = new Comparable<?>[N];
    int i = 0;
    int j = 0;
    // LSD 从低位到高位
    for(int id=1; id<=d; ++id){
        // 置空每个桶
        for(i=0; i<k; ++i){
            count[i] = 0;
        }
        // 统计每个桶将要装入的数据个数
        for(i=0; i<N; ++i){
            j = getDigit((int)a[i], id);
            count[j]++;
        }
        // 每个桶的左起始边界
        count[k-1] = N - count[k-1];
        for(i = k-2; i>=0; --i){
            count[i] = count[i+1] - count[i];
        }
        // 将数据一次装入桶中
        for(i = 0; i<N; ++i){
            j = getDigit((int)a[i], id);
            bucket[count[j]++] = a[i];
        }
        // 将bucket倒入a中
        for(i = 0; i<N; ++i){
            a[i] = bucket[i];
        }
    }
}

Reference

https://en.wikipedia.org/wiki/Sorting_algorithm
https://www.douban.com/note/250011027/?type=like
http://blog.csdn.net/CJF_iceKing/article/details/7953637
http://www.cnblogs.com/jingmoxukong/p/4311237.html