快速排序

      快排的整体思想是找出一个key值，比key的值小的都在它的左边，比key大的值都在它的右边。这样就划分了左右两个区域，分别找左右两个区域的key值继续划分左右区间。

 

找中间值的位置有三种方法

（1）左右指针法

         思想：在序列的左右各定义begin,和end这两个指针。begin++往右走，当遇到比key大的值停下。end--往左走，遇

到比key小的值后停下。此时交换begin和end下标所代表的值。（使得比key大的数在右边，比key小的数在左边）。当

begin和end相遇时，把这个值和key值交换。此时序列中比key大的数都在key右边，比key小的数都在key左边（分成了

左右两个区间）。把key的下标返回，继续找区间的key。

int PartSort1(int* a, int left, int right)//6---1左右指针法 { int mid = GetMidIndex(a, left, right); swap(a[mid], a[right]); //优化1 三数取中法，避免KEY值是最大值或最小值。 int begin = left; int end = right; int key = a[right]; while (begin < end) { while (begin < end&&a[begin] <= key) { ++begin; } while (begin < end&&a[end] >= key) { --end; } if (begin < end) { swap(a[begin], a[end]); } } swap(a[begin], a[right]); return begin; }

(2)挖坑法

思想：1  选择最右的值为key值，并把key值得位置当做第一个坑，找到合适的数来填坑。依旧定义begin和end两个最左

最右的指针。2   让begin++，先往左走，当遇到比key大的数停下，此时拿begin位置上的数去填第一个坑，此时坑的位

置在begin的位置上。3  再让end--,往右走，当遇到比key小的数停下，拿end位置上的数去填坑（坑此时在begin的置）。

当填完后，坑现在在end的位置上。4  重复上述动作，直到end和begin相遇，此时坑在begin和end位置上，拿key值来填

这个坑。

int PartSort2(int* a, int left, int right)//6--2 挖坑法，先把key的值得位置当成坑 { int mid = GetMidIndex(a, left, right); swap(a[mid], a[right]); //优化三数取中法 int begin = left; //定义begin int end = right; //定义end int key = a[right]; //定义key while (begin < end) //循环 当begin<end时继续 { while (begin < end&&a[begin] <= key) //a[begin]<key，begin继续往左走 { ++begin; } a[end] = a[begin]; //填坑-->赋值 while (begin < end&&a[end] >= key) { --end; } a[begin] = a[end]; } a[begin] = a[end] = key; //循环出来，begin=end ，把key值给到这个位置上填坑 return begin; //任意返回begin或者end }

（3）前后指针法：

         思想：1定义一个下标cur，刚开始赋值为序列的最左。再定义一个prev，赋值为cur-1，意思是cur的前面一个数的下标。2  用cur下标代表的数与key比较，若比key值大，则cur++往右走。若比key值小，先让prev++往右走，在比较prev和cur是不是在同一个位置上，若不在同一个位置，则，交换prev和cur所代表的数值。cur继续往前走。

int PartSort3(int* a, int left, int right)// 6---3前后指针法 { int mid = GetMidIndex(a, left, right); swap(a[mid], a[right]); int cur = left; int prev =cur-1; int key = a[right]; while (cur < right) { if (a[cur] < key&&++prev != cur) { swap(a[prev], a[cur]); } ++cur; } ++prev; swap(a[prev], a[right]); return prev; }

2种优化方案

1 三数取中法

思想：避免key值取到最大值或者最小值。在right，left，mid三个代表的下标中选取中间数。这样是为了划分左右区间时左右尽量平衡。 //优化快排 三数取中。避免a[div]是最大值或最小值 int GetMidIndex(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) return mid; else if (a[right] > a[left]) return left; else return right; } else//a[left]<a[mid] { if (a[mid] < a[right]) return mid; else if (a[right] < a[left]) return left; else return right; } } 2 小区间优化

思想：在区间范围较小时，不选择快排算法。而选择插入算法。这样是算法的优化。

void QuickSort(int*a, int left, int right) //6 快速排序 { if (left < right) { int div = PartSort1(a, left, right); if (right - left < 5) //小区间优化 { InsertSort(a,right-left+1); } else //若左右区间大的话直接还是用快排方法。 { QuickSort(a, left, div - 1);//左 QuickSort(a, div + 1, right);//右 } } }

快排非递归：借助栈结构

void QuickSortNR(int *arr, int begin, int end) { assert(arr); stack<int> s; s.push(begin); s.push(end); while (!s.empty()) { int left = s.top(); s.pop(); int right = s.top(); s.pop; int div = PartSort3(arr, left, right); if (div - 1 > left) { s.push(div - 1); s.push(left); } if (div + 1 < right) { s.push(right); s.push(div + 1); } } }

总结：

快速排序对于小规模的数据集性能不是很好。没有插入性能高。

快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。

当数据集较小时，不必继续递归调用快速排序算法，使用插入排序代替快速排序。（小区间优化）

快速排序是时间复杂度是O(N*LogN).

                  最好情况：O(N*LogN).

                  最坏情况：O(N^2)   :当序列中的数值都相等时，快排是最坏的情况。

空间复杂度：O(lgN)

快排是一种不稳定的排序算法。