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

下面我们介绍一下时间复杂度为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

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

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

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;
}