高效排序算法-快速排序

快速排序

原理： 快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

1.挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）；
2.分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；
3.递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。因此快速排序属于不稳定排序。

对基准值选择对排序带来的影响，大家可以参考我自己写的一套OC代码实现，这个Demo中对比了三大基本排序和快速排序的效率，快速排序也支持选取第一个或最后一个或中间位为基准值。同学们可以手动设置数据源，对比一下这几种排序的效率，也可以观察不同基准值的快速排序效率上的差异。

GitHub地址

快速排序的实现代码：
在前面我们知道，选取正确的基准值对排序的性能有着决定性的影响，在这里我们选择序列中间的值作为基准值。

代码主要分为两个部分：进行切分的代码和进行递归调用的代码

第一部分 进行切分
/**
 * 进行切分，并进行交换
 * @param a 数组
 * @param lo 切分开始的位置
 * @param h 切分结束的位置
 * @return 返回分界点的位置
 */
public static int partition(int[] a,int lo,int h){
    // 选取中间的值为基准值
    int middle = (lo+h+1)/2;
    int v = a[middle];
    // 将基准值和a[lo]交换位置
    exc(a, lo, middle);
    
    int i = lo;
    int j = h+1;
    while(true){

        // 假如左边的小于基准值，则一直进行循环
        while(a[++i] < v){
            // 防止越界
            if(i == h){
                break;
            }
        }
        // 假如右边的大于基准值，则一直进行循环
        while(a[--j]>v){
            if(j == lo){
                break;
            }
        }
        
        // 一旦i>=j则代表i前面的除第一个外都比基准值小，j后面的都比基准值大，这时候就可以跳出循环了
        if(i>=j){
            break;
        }
        
        // 进行交换(因为a[lo]>v,a[h]<v，所以将两者进行交换)
        exc(a, i,j);   
    }
    // 将基准放到分界点
    exc(a, lo, j);
    return j;
}

第二部分 进行递归调用
/**
 * 调用quickSort函数
 * @param a 数组
 */
public static void quickSort(int[] a){
        quickSort(a,0,a.length-1);
}

/**
 * 进行递归的快排
 * @param a
 * @param lo
 * @param h
 */
public static void quickSort(int[] a,int lo,int h){
    if(h <= lo) {
        return ;
    }
    // j为基准值的位置
    int j = partition(a, lo, h);
    // 进行递归调用，将j前面的进行快排
    quickSort(a,lo,j-1);
    // 进行递归调用，将j后面的进行快排
    quickSort(a,j+1,h);
}

特点：
快速排序在最坏的情况下时间复杂度是O(n**2),平均时间复杂度是O(nlogn)。快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。

出处：https://www.cnblogs.com/xiaohuiduan/p/11188304.html

GitHub代码为原创