并不是很懂wikipedia上面说快排的空间复杂度最坏情况是O(NlogN)啊,难道不是空间复杂度平均O(logN),最坏O(N)么……原地快排难道不是只要算递归栈深度就好了么……有谁给我解释一下啊(评论区orz)。
快排的核心思想我感觉就是选一个pivot,然后将待排序数列通过与pivot比较分为两个部分A和B(A部分的数均小于或等于pivot,B部分均大于或等于pivot),这样划分好的数列中的数就处于A <= pivot <= B的状态,接着对划分好的两个部分A和B分别递归调用快排函数,最后一定能出现划分好的部分中只剩下一个元素或没有元素的情况,而对于只有一个元素的数列或空列,我们认为它已经是有序的,这样就把数列排好了。
所以在快排中怎样对数组进行划分是关键,不同版本的快速排序大体结构都差不多,不同之处就在于划分函数的不同,这里就暂时称它为Partition函数吧,下面首先介绍四种不同的实现,再介绍它们的优化。
第一个版本
其实快排一开始不是我们现在看到的这样的,一开始Hoare发明的版本在《算法导论》这本书的思考题7-1上有提及。这个版本相当于是以开头元素为pivot,然后两个index分别从头和尾开始遍历,暂时把这两个index变量称为i和j吧,i从头开始,j从尾开始,其过程如下:
第一步——j往前遍历,遇到小于或等于pivot的数就停止
第二步——i往后遍历,遇到大于或等于pivot的数就停止
第三步——比较i和j大小,j > i则交换i和j位置上的数并在此基础上继续第一步,否则函数返回j
函数返回后,经过Partition函数的调用,数组中下标为j之前(包括j)的元素都小于或等于pivot,j之后的元素都大于或等于pivot,然后对这两部分进行快速排序。
例子:
代码如下:
int Hoare_Partition(int A[ ], int begin, int end){ int pivot = A[begin]; ;; ; ){ do{ j--; }while(A[j] > pivot); do{ i++; }while(A[i] < pivot); if(j > i){ Swap(A, i, j); } else{ return j; } } } void Quick_Sort_1(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = Hoare_Partition(A, begin, end); Quick_Sort_1(A, begin, pivot_position); Quick_Sort_1(A, pivot_position + , end); }
第二个版本
这个版本是对Hoare原版本的一个改进,Hoare原版本中Partition函数调用结束后pivot会存在于划分好的两个部分中的某一个中,因此第二个版本对此进行了改进,同样选取第一个元素作为pivot,如果数列的下标从begin开始,end结束的话,那么用Hoare的处理思想去处理从begin + 1到end部分的数列(Hoare的版本是处理从begin到end部分的数列的),这样处理完成后下标为begin + 1到j的数都是小于或等于pivot的,而下标为j + 1到end的数都是大于或等于pivot的,最后再将pivot和下标为j的数进行交换并返回j,这样一来下标为j之前(不包括j)的数均小于或等于pivot,下标为j之后的数均大于或等于pivot,pivot也就不在两个划分好的部分中,而独立存在了,因此只要对两个部分继续快排就好了,而不需要再将pivot包括进去。
例子:
代码如下:
int New_Partition_1(int A[ ], int begin, int end){ int pivot = A[begin]; int i = begin; ; ){ do{ j--; }while(A[j] > pivot); do{ i++; }while(A[i] < pivot); if(j > i){ Swap(A, i, j); } else{ A[begin] = A[j]; A[j] = pivot; return j; } } } void Quick_Sort_2(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_1(A, begin, end); Quick_Sort_2(A, begin, pivot_position - ); Quick_Sort_2(A, pivot_position + , end); }
第三个版本
这个版本是现在比较常见的版本之一,将pivot所在位置挖成一个坑,i从begin + 1开始,j从end开始,然后:
第一步——j往前遍历,找到小于或等于pivot的数
如果此时j > i,将下标为j的数填入现在的坑中,并在下标为j的位置产生一个新坑,进行第二步
否则就将pivot填入现在的坑中,并返回j
第二步——i往后遍历,找到大于或等于pivot的数
如果此时j > i,将下标为i的数填入现在的坑中,并在下标为i的位置产生一个新坑,进行第一步
否则就将pivot填入现在的坑中,并返回i
例子:
代码如下:
int New_Partition_2(int A[ ], int begin, int end){ int pivot = A[begin]; int i = begin; ; ){ do{ j--; }while(A[j] > pivot); if(j > i){ A[i] = A[j]; } else{ A[i] = pivot; return i; } do{ i++; }while(A[i] < pivot&&i < j); if(j > i){ A[j] = A[i]; } else{ A[j] = pivot; return j; } } } void Quick_Sort_3(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_2(A, begin, end); Quick_Sort_3(A, begin, pivot_position - ); Quick_Sort_3(A, pivot_position + , end); }
第四个版本
这个版本也很常见,就是把最后一个数作为pivot,i一开始等于begin,用j从begin开始往end - 1遍历,找到小于或等于pivot的数,与i所在位置的数交换,并将i++,最后将pivot和下标为i的数交换,返回i。
例子:
代码如下:
int New_Partition_3(int A[ ], int begin, int end){ int pivot = A[end]; int i, j = begin; for(i = begin; i < end; i++){ if(A[i] <= pivot){ Swap(A, i, j); j++; } } A[end] = A[j]; A[j] = pivot; return j; } void Quick_Sort_4(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_3(A, begin, end); Quick_Sort_4(A, begin, pivot_position - ); Quick_Sort_4(A, pivot_position + , end); }
通过三数取中来优化快排
这种优化就是每次选择pivot时,选择首元素,尾元素,和中点处元素中第二大的元素来作为pivot,这样就可以尽量避免快排中最坏情况的出现(这样能尽可能让两个划分大小均匀,毕竟是选取大小较为中间的数作为pivot,减少选取到的pivot是极大值或极小值的概率),同时也可以避免某些partition函数的版本(如第三个版本)中出现数组访问越界的情况(因为选取的pivot尽可能是中间值,不会出现一次遍历结束全都大于或全都小于pivot的情况,遍历也就可以停住而不会继续下去导致越界访问),代码如下:
int Choose_Pivot(int A[], int begin, int end){ ; if((A[pivot_position] >= A[end]&&A[pivot_position] >= A[begin])){ if(A[begin] >= A[end]){ pivot_position = begin; } else{ pivot_position = end; } } else if((A[pivot_position] <= A[end]&&A[pivot_position] <= A[begin])){ if(A[begin] >= A[end]){ pivot_position = end; } else{ pivot_position = begin; } } return pivot_position; } int Optimal_Partition_1(int A[], int begin, int end){ int pivot_position = Choose_Pivot(A, begin, end), pivot; int i = begin, j; Swap(A, pivot_position, end); pivot = A[end]; for(j = begin; j < end; j++){ if(A[j] <= pivot){ Swap(A, i, j); i++; } } A[end] = A[i]; A[i] = pivot; return i; } void Quick_Sort_5(int A[], int begin, int end){ int pivot_position; while(begin < end){ pivot_position = Optimal_Partition_1(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } }
通过优先排序较小划分来优化快排
快排是通过递归实现的,而在快排函数中会递归调用两次,第二次调用是尾递归,我们知道尾递归都是可以转换为循环来进行优化的。函数调用是很浪费时间的,并且递归又很占用内存空间,所以可以优先递归调用快排去排序较小的划分子列,这样可以节约空间,然后通过循环来实现原先对较大的划分子列进行快排的尾递归,节约时间和空间,上面通过三数取中法来优化快排的函数中就采用了这一方法。(实际上很多聪明的编译器都会自动优化这一点)
通过随机数来优化快排
因为pivot如果选取的不恰当就很可能出现最坏情况,所以可以生成随机数来决定选取数组中某个位置的数作为pivot,这样就会减小选到极大的或极小的pivot的情况的概率,从而使划分尽可能均匀。想一想,假设一个数列包含以下的数{1, 2, 3, 4, 5, 6, 7, 8},这个数列中{3, 4, 5, 6}这几个数都至少大于或小于数列中25%的数,选择它们为pivot的话就可以让划分变得更加均匀(相比较选择{1, 2, 7, 8}而言),每次都选择{3, 4, 5, 6}的话,在O(Nlog4N)即O(2NlogN)时间就可以完成排序,而选取随机数有50%的概率选中{3, 4, 5, 6}中的数,也就是最多需要O(4NlogN)时间即可完成排序,这个结果是远远比最坏情况O(N^2)要好的,当然注意用rand函数要加括号,代码如下:
int Optimal_Partition_2(int A[], int begin, int end){ ) + begin); int pivot; int i = begin, j; pivot = A[pivot_position]; Swap(A, pivot_position, end); for(j = begin; j < end; j++){ if(A[j] <= pivot){ Swap(A, i, j); i++; } } A[end] = A[i]; A[i] = pivot; return i; } void Quick_Sort_6(int A[], int begin, int end){ int pivot_position; while(begin < end){ pivot_position = Optimal_Partition_2(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } }
用插入排序来优化快排
快排在小规模数组方面的表现不如插入排序和堆排序好,而且一般递归到规模较小的数组时,数组已经处于一种较为有序,或者说局部有序的状态,这时用插入排序可以节省时间,代码如下:
void Insert_Sort(int A[], int begin, int end){ int i, j, tmp; for(i = begin; i <= end; i++){ tmp = A[i]; ; j >= begin; j--){ if(tmp > A[j]){ break; } else{ A[j + ] = A[j]; } } A[j + ] = tmp; } } int Optimal_Partition_2(int A[], int begin, int end){ ) + begin); int pivot; int i = begin, j; pivot = A[pivot_position]; Swop(A, pivot_position, end); for(j = begin; j < end; j++){ if(A[j] <= pivot){ Swap(A, i, j); i++; } } A[end] = A[i]; A[i] = pivot; return i; } void Quick_Sort_7(int A[], int begin, int end){ int pivot_position; while(begin < end){ ){ Insert_Sort(A, begin, end); return; } pivot_position = Optimal_Partition_2(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } }
完整代码:
// // main.c // Quick Sort // // Created by 余南龙 on 2016/11/29. // Copyright © 2016年 余南龙. All rights reserved. // #include <stdio.h> #include <time.h> #include <stdlib.h> void Swap(int A[], int i, int j){ int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } int Choose_Pivot(int A[], int begin, int end){ ; if((A[pivot_position] >= A[end]&&A[pivot_position] >= A[begin])){ if(A[begin] >= A[end]){ pivot_position = begin; } else{ pivot_position = end; } } else if((A[pivot_position] <= A[end]&&A[pivot_position] <= A[begin])){ if(A[begin] >= A[end]){ pivot_position = end; } else{ pivot_position = begin; } } return pivot_position; } void Insert_Sort(int A[], int begin, int end){ int i, j, tmp; for(i = begin; i <= end; i++){ tmp = A[i]; ; j >= begin; j--){ if(tmp > A[j]){ break; } else{ A[j + ] = A[j]; } } A[j + ] = tmp; } } int Hoare_Partition(int A[ ], int begin, int end){ int pivot = A[begin]; ;; ; ){ do{ j--; }while(A[j] > pivot); do{ i++; }while(A[i] < pivot); if(j > i){ Swap(A, i, j); } else{ return j; } } } int New_Partition_1(int A[ ], int begin, int end){ int pivot = A[begin]; int i = begin; ; ){ do{ j--; }while(A[j] > pivot); do{ i++; }while(A[i] < pivot); if(j > i){ Swap(A, i, j); } else{ A[begin] = A[j]; A[j] = pivot; return j; } } } int New_Partition_2(int A[ ], int begin, int end){ int pivot = A[begin]; int i = begin; ; ){ do{ j--; }while(A[j] > pivot); if(j > i){ A[i] = A[j]; } else{ A[i] = pivot; return i; } do{ i++; }while(A[i] < pivot&&i < j); if(j > i){ A[j] = A[i]; } else{ A[j] = pivot; return j; } } } int New_Partition_3(int A[ ], int begin, int end){ int pivot = A[end]; int i, j = begin; for(i = begin; i < end; i++){ if(A[i] <= pivot){ Swap(A, i, j); j++; } } A[end] = A[j]; A[j] = pivot; return j; } int Optimal_Partition_1(int A[], int begin, int end){ int pivot_position = Choose_Pivot(A, begin, end), pivot; int i = begin, j; Swap(A, pivot_position, end); pivot = A[end]; for(j = begin; j < end; j++){ if(A[j] <= pivot){ Swap(A, i, j); i++; } } A[end] = A[i]; A[i] = pivot; return i; } int Optimal_Partition_2(int A[], int begin, int end){ ) + begin); int pivot; int i = begin, j; pivot = A[pivot_position]; Swap(A, pivot_position, end); for(j = begin; j < end; j++){ if(A[j] <= pivot){ Swap(A, i, j); i++; } } A[end] = A[i]; A[i] = pivot; return i; } void Quick_Sort_1(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = Hoare_Partition(A, begin, end); Quick_Sort_1(A, begin, pivot_position); Quick_Sort_1(A, pivot_position + , end); } void Quick_Sort_2(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_1(A, begin, end); Quick_Sort_2(A, begin, pivot_position - ); Quick_Sort_2(A, pivot_position + , end); } void Quick_Sort_3(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_2(A, begin, end); Quick_Sort_3(A, begin, pivot_position - ); Quick_Sort_3(A, pivot_position + , end); } void Quick_Sort_4(int A[ ], int begin, int end){ int pivot_position; if(begin >= end) return; pivot_position = New_Partition_3(A, begin, end); Quick_Sort_4(A, begin, pivot_position - ); Quick_Sort_4(A, pivot_position + , end); } void Quick_Sort_5(int A[], int begin, int end){ int pivot_position; while(begin < end){ pivot_position = Optimal_Partition_1(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } } void Quick_Sort_6(int A[], int begin, int end){ int pivot_position; while(begin < end){ pivot_position = Optimal_Partition_2(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } } void Quick_Sort_7(int A[], int begin, int end){ int pivot_position; while(begin < end){ ){ Insert_Sort(A, begin, end); return; } pivot_position = Optimal_Partition_2(A, begin, end); if(end - pivot_position >= pivot_position - begin){ Quick_Sort_5(A, begin, pivot_position - ); begin = pivot_position + ; } else{ Quick_Sort_5(A, pivot_position + , end); end = pivot_position - ; } } } int main(int argc, const char * argv[]) { ] = {, , , , , , , , , }; ] = {, , , , , , , , , }; ] = {, , , , , , , , , }; ] = {, , , , , , , , , }; ] = {, , , , , , , , , }; ] = {, , , , , , , , , }; ]; int i; srand((unsigned)time()); ; i < ; i++){ A_7[i] = (rand() % ); } Quick_Sort_1(A_1, , ); ; i < ; i++){ printf("%d ", A_1[i]); } putchar('\n'); Quick_Sort_2(A_2, , ); ; i < ; i++){ printf("%d ", A_2[i]); } putchar('\n'); Quick_Sort_3(A_3, , ); ; i < ; i++){ printf("%d ", A_3[i]); } putchar('\n'); Quick_Sort_4(A_4, , ); ; i < ; i++){ printf("%d ", A_4[i]); } putchar('\n'); Quick_Sort_5(A_5, , ); ; i < ; i++){ printf("%d ", A_5[i]); } putchar('\n'); Quick_Sort_6(A_6, , ); ; i < ; i++){ printf("%d ", A_6[i]); } putchar('\n'); Quick_Sort_7(A_7, , ); ; i < ; i++){ printf("%d ", A_7[i]); } putchar('\n'); }