算法分析

快速排序算法的时间复杂度为nlog(n)。

基本思想：选择一个元素作为标志，比如下标为k的元素，经过排序使，arr[0,1,2....k-1]的元素小于arr[k]，arr[k+1,k+2...n]的元素大于arr[k]，然后对arr[0,1,2...k-1]和arr[k+1,k+2...n]两部分元素进行之前类似的操作。

算法代码示例如下：

template
     
      int _partition(T arr[], int l, int r){    int v = arr[l];    int j = l;      //arr[l+1...j] < v ; arr[j+1...r] > v    for(int i = l + 1; i <= r; i++)        if(v > arr[i])            swap(arr[++j], arr[i]);       swap(arr[l], arr[j]);    return j;}template
      
       void _quickSort(T arr[], int l, int r){    if(l >= r)        return ;    int p = _partition(arr, l, r);    _quickSort(arr, l, p-1);    _quickSort(arr, p+1, r);}template
       
        void quickSort(T arr[], int n){    _quickSort(arr, 0, n-1);}
       
      
     

快速排序算法与插入排序、归并排序性能更好，但是对于几乎有序的数据，以上的快速排序性能会很差，时间复杂度可能会接近O(n^2)。

 算法优化

针对以上的快速排序算法，对于有序的数据再进行排序，由于每次都选择第一个元素作为标志后，出现数据量一边倒的情况，导致快速排序的性能很差，时间复杂度为O(n^2)，以下通过随机选择标志元素的方式避免这种情况，以下为优化过后的代码：

template
     
      int _partition(T arr[], int l, int r){    //优化点2：通过随机选择元素标志，防止对几乎有序的数据排序慢的问题    srand(time(NULL));    swap(arr[l], arr[rand()%(r-l+1)+l]);        int v = arr[l];    int j = l;      //arr[l+1...j] < v ; arr[j+1...r] > v    for(int i = l + 1; i <= r; i++)        if(v > arr[i])            swap(arr[++j], arr[i]);       swap(arr[l], arr[j]);    return j;}template
      
       void _quickSort(T arr[], int l, int r){    //if(l >= r)    //    return ;    //优化点1：小规模数据使用插入排序    if(r-l <= 15)    {        insertionSort(arr, l, r);        return;    }    int p = _partition(arr, l, r);    _quickSort(arr, l, p-1);    _quickSort(arr, p+1, r);}template
       
        void quickSort(T arr[], int n){    _quickSort(arr, 0, n-1);}
       
      
     

 经过优化以后，对于几乎有序的数据进行排序性能得到了提升，但是对于具有大量重复的数据排序，选择标志数据为v后，可能会出现大量等于v的数据，如下图所示，会出现排序的数据一边倒的情况，排序性能会很差。接下来我们继续对快速排序算法进行优化，以下优化过后的排序算法会有个新的名字，叫。