排序算法

算法笔记
排序, 源码, 算法

JDK中的排序算法

Java 数组方法中的Sort方法(1.7开始多了基于TimSort的parallelSort，是一种优化过的归并排序，适合多核对大数组切分然后归并）其实包含三种排序算法，当待排序数组长度小于47时，采用插入排序，小于286时采用快速排序，大于286则采用归并排序，由此可见三种排序在不同数据规模下的效率。下面以升序为例介绍三种算法。

插入排序

描述 :从前往后，当后数小于前数时，即开始把后数往前挪动，直至放入正确位置。
代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertSort(int[] a, int left, int right) {
    for (int i = left+1; i <=right; i++) {
        if(a[i]<a[i-1]){
            int j= i,t = a[j];
            while(j>left && a[j-1]>t){
            //这里不用swap直接前数后移即可
                a[j]=a[j-1];
                j--;
            }
            //将记录下的后数放入正确位置
            a[j]=t;
        }
    }
}

官方实现如下 :

1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(int[] a, int left, int right)  {
    for (int i = left, j = i; i < right; j = ++i) {
        int ai = a[i + 1];
        while (ai < a[j]) {
            a[j + 1] = a[j];
            if (j-- == left) {
                break;
            }
        }
        a[j + 1] = ai;
    }
}

插入排序

描述 : 关于插入排序的解释，觉得最清楚的一篇博客是快速搞定快速排序。快速排序思想是①选取基准数（一般取left、right、middle的中位数）②分区，将比基准大的数放到基准右边，小于等于的数放在左边③对基准左右两个区间重复第二步，直至各区间只剩一个数。

快排过程可以理解成挖坑填数：
1．i = L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比基准小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比基准大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

实现 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//以l为基准
//按照partition函数和sort函数分开的思想：
int quickSort(int[] s, int l, int r){
    // 基准x(pivot)选取s[l]，实际可以用middle，计算middle技巧 (l+r)>>>1
    // >>为算术右移，>>>为无符号右移
    int i =l,j=r,x=s[i];
    while(i<j){
        while(i<j && s[j]>=x)
            j--;
        s[i]=s[j];
        while(i<j && s[i]<=x)
            i++;
        s[j]=s[i];
    }
    s[i]=x;//回填基准，此时基准左右分区。
    return i;//即返回基准分割的位置
}
void quickSort(int[] s, int l, int r) {
    if(l<r){
        int i = quickSort(int[] s, int l, int r);
        quickSort(s,l,i-1);
        quickSort(s,i+1,r);
    }
}

官方实现 :

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
/*官方实现采用了双基准的实现方法，而且有很多优化，面对包含大量重复元素的数组效率更高，这里只写出快排示例
*选择两个枢纽元p1,p2，一般选择起始元素a[left]和末尾元素a[right]。
*假设p1<p2，如果不是就交换。
*基于p1,p2将整个数组分成三部分，小于p1的，大于p1 且 小于p2的，大于p2的。
*递归排序这三个部分。
*/
void dual_qsort(int low,int high,int[] a){
    if(low>high)
        swap(low,high);
    int pivotL=low,pivotR=high;
    int tmpL=low,tmpR=high;
    int index=low+1;
    while(index<=tmpR){
     if(a[index]<pivotL)
        swap(a[index++],a[tmpL++]);
     else if(a[index]>pivotR)
        swap(a[index],a[tmpR--]);
     else 
        index++;
    }
    swap(a[--tmpL],a[low]);
    swap(a[++tmpR],a[high]);
    dual_qsort(low,tmpL-,a);
    dual_qsort(tmpL+，tmpR-,a);
    dual_qsort(tmpR+,high,a);
}

归并排序

描述 : 递归分解数组，在合并已排序的子数组。
先介绍合并两个已排序数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//n为a[]的长度
void mergeArray(int[] a, int[] b, int[] c)  
{
    int i, j, k;
    i = j = k = 0;
    int n = a.length,m = b.length;
    while (i < n && j < m)
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++]; 
    }
    while (i < n)
        c[k++] = a[i++];
    while (j < m)
        c[k++] = b[j++];  
}

直接上代码:

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
//合并的两个数组一定相邻，所以用low-mid,mid+1-high区分
void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low,j = mid + 1;//左右待合并数组起始点
    int k = 0;
    while (i <= mid && j <= high) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = a[j++];
    }
    //覆盖回写原数组
    for (int l = 0; l < temp.length; l++) {
        a[l + low] = temp[l];
    }
}
void mergeSort(int[] a, int low, int high) {
    int mid = (low + high)>>>1;
    if (low < high) {
        //归
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        //并
        merge(a, low, mid, high);
    }
}

最后贴一下排序复杂度与稳定性

不稳定：

选择排序（selection sort）— O(n2)
快速排序（quicksort）— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序
堆排序 （heapsort）— O(nlogn)
希尔排序 （shell sort）— O(nlogn)
基数排序（radix sort）— O(n·k); 需要 O(n) 额外存储空间 （K为特征个数）

稳定：

插入排序（insertion sort）— O(n2)
冒泡排序（bubble sort） — O(n2)
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外存储空间
二叉树排序（Binary tree sort） — O(nlogn); 需要 O(n) 额外存储空间
计数排序>>(counting sort) — O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1
桶排序 （bucket sort）— O(n); 需要 O(k) 额外存储空间

分享到