快速排序法是一种高效的排序法，算法的最终性能取决于选取的中间值，直接实现的快速排序法如下：
#include#include static int partition( int* array, int start, int end){ int key = array[start]; int l = start; int r = end; while(l < r){ while(l < r && key < array[r]){ -- r; } std:: swap (array[l], array[r]); while(l < r && key > array[l]){ ++ l; } std:: swap (array[l], array[r]); } return l; } static void qsort (int * array, int start, int end){ if(start < end){ int p = partition(array, start, end); qsort(array, start, p-1); qsort(array, p+1, end); } } void quick_sort( int* array, int length){ qsort(array, 0, length-1); } int main(){ int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; quick_sort(array, 10); for(int i = 0; i != 10; ++i){ std::cout << array[i] << " "; } std::cout << std:: endl; return 0; }
为了解决选取值的问题，可以做如下优化，取第一个元素、中间一个元素和最后一个元素三个值的中间值作为选取值，这样，所选的值为最大或最小值得可能性就比较小了，具体的代码如下：
#include#include static int partition( int* array, int start, int end){ //int key = array[start]; int key; int m = (start+end)/2; if(array[start] > array[end]){ std:: swap (array[start], array[end]); } if(array[m] > array[end]){ std:: swap (array[m], array[end]); } if(array[m] > array[start]){ std:: swap (array[start], array[m]); } key = array[start]; int l = start; int r = end; while(l < r){ while(l < r && key < array[r]){ -- r; } std:: swap (array[l], array[r]); while(l < r && key > array[l]){ ++ l; } std:: swap (array[l], array[r]); } return l; } static void qsort( int* array, int start, int end){ if(start < end){ int p = partition(array, start, end); qsort(array, start, p-1); qsort(array, p+1, end); } } void quick_sort( int* array, int length){ qsort(array, 0, length-1); } int main(){ int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; quick_sort(array, 10); for(int i = 0; i != 10; ++i){ std::cout << array[i] << " "; } std::cout << std:: endl; return 0; }
快速排序在最好情况下的时间复杂度为：O(nlogn)，最差情况下为O(n2)，为了进一步提高快速排序法的性能，还可以减少快速排序法中不必要的交换，优化后的代码为：
#include#include static int partition( int* array, int start, int end){ //int key = array[start]; int key; int m = (start+end)/2; if(array[start] > array[end]){ std:: swap (array[start], array[end]); } if(array[m] > array[end]){ std:: swap (array[m], array[end]); } if(array[m] > array[start]){ std:: swap (array[start], array[m]); } key = array[start]; int l = start; int r = end; while(l < r){ while(l < r && key < array[r]){ -- r; } //std ::swap (array[l], array[r]); array[l] = array[r]; while(l < r && key > array[l]){ ++ l; } //std ::swap (array[l], array[r]); array[r] = array[l]; } array[l] = key; return l; } static void qsort( int* array, int start, int end){ if(start < end){ int p = partition(array, start, end); qsort(array, start, p-1); qsort(array, p+1, end); } } void quick_sort( int* array, int length){ qsort(array, 0, length-1); } int main(){ int array[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; quick_sort(array, 10); for(int i = 0; i != 10; ++i){ std::cout << array[i] << " "; } std::cout << std:: endl; return 0; }
到这里，常用的排序算法基本就讲述完了，但是相比来讲，归并排序是最稳定的算法，有任何问题欢迎留言讨论。
本文链接：http://blog.csdn.net/girlkoo/article/details/17606639
本文作者：girlkoo