算法导论笔记(4)

快速排序

思想

快排是分治的思想。

分解： A[p…r]分成A[p…q-1]和A[q+1…r]两个数组，q的位置固定，每趟排序会有一个元素固定

解决： 递归调用，对A[p…q-1]和A[q+1…r]排序

合并： 原址排序，无需合并操作

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int partitions(int *A,int p,int r){
    if(p<r){
        int x=A[r];//选择主元，划分数组
        int i=p-1;
        for (int j = p; j < r ; ++j)
        {
            if (A[j]<=x)
            {
                i+=1;
                swap(A[i],A[j]);
            }
        }
        swap(A[++i],A[r]);
        return i;
    }
}
void quickSort(int *A,int p,int r){
    if (p<r)
    {
        int q=partitions(A,p,r);
        quickSort(A,p,q-1);
        quickSort(A,q+1,r);
    }
}
int main(int argc, char const *argv[])
{
    int a[10]={12,43,64,11,87,99,123,4534,66,2345};
    quickSort(a,0,9);
    for(int i=0;i<10;i++){
        printf("%d ",a[i]);
    }
    return 0;
}

总结

平均时间复杂度O(N*logN)，
最坏的情况下，主元一直是当前数组最大或最小，时间复杂度O(N*N).
当已经有序时，还是O(N*N),而插入排序是O(N)

优化

根据分区大小调整算法

快速排序对于小规模的数据集性能不是很好。
Introsort就是这样的一种算法，它开始采用快速排序算法进行排序，当递归达到一定深度时就改为堆排序来处理。
另一种优化改进是当分区的规模达到一定小时，便停止快速排序算法。也即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。可以对这种“几乎”完成排序的数列使用插入排序算法进行排序以最终完成整个排序过程。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。

三平均分区法

关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：
　　（1） 首先，它使得最坏情况发生的几率减小了。
　　（2） 其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。

随机化版本

随机选取一个元素作为主元.随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度.随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度