交换排序之快排

快排是一种时间复杂度为O(N*longN)的不稳定排序算法，其最差情况下算法的时间复杂度为O(N^2)。

一.快排的实现思想的基本框架

思想： 在队列中选取key,作为划分标准，将其划分为俩段，然后通过交换使得序列的左边的数小于key，右边的数大于key。 通过递归对序列不断划分，直至序列中只有一个元素时停止，通过对其子序列的数采用交换的手段达到排序的目的。 实现：

void QuickSort(int* arr,int begin,int end) { if(begin<=end) return; //将数组划分为([begin,keyindex-1] keyindex [keyindex+1,end])三段 int keyindex=PartSort1(arr,begin,end); //int keyindex=PartSort2(arr,begin,end); //int keyindex=PartSort3(arr,begin,end); //走俩边 QuickSort(arr,begin,keyindex-1)；//前面的一段 QuickSort(arr,keyindex+1,end); //后边的一段 }

下边分别介绍快排的三种对子序列排序的思路：

1.左右指针法实现

算法思想： 在队列中任选一个数key，将序列画分为俩段，通过定义序列头部和尾部俩个指针，进行交换，将序列的左边换为小于key的数，右边换为大于key的数。 具体代码实现

void Swap(int* p1,int*p2) { int temp=*p1; *p1=*p2; *p2=temp; } int PartSort1(int *arr,int begin,int end)//所传参数为下标 { int key=arr[end];//key为划分的标准 int keyindex=end; while(begin<end) { //从左向右找比key大或相等的数，并且记录其下标 while(begin<end && arr[begin]<=key) ++begin; //从右向左找比key小或相等的数，并且记录其下标 while(begin<end && arr[end]>=key) --end; //对找到的数进行交换 Swap(&arr[begin],&arr[end]); } //待循环完毕之后将最后一个大于key的数与key交换 Swap(&arr[begin],&arr[index]); retrun begin; }

2.挖坑法

算法思想： 在队列中选取一个key做为坑的位置并且保存其值（一般选取序列最后一个或者第一个值），并以key为划分标准来将序列划分为俩段，使得key前面的值都小于等于key，后边的值都大于等于key。 具体实现：

int PartSort2(int* arr,int begin,int end) { int key=arr[end];//end为第一个坑的位置 while(begin<end) { //找大于key的数 while(begin<end && arr(begin)<=key) ++begin; //找到之后，将其放至挖好的坑中，同时end的位置形成新的坑位 arr[end]=arr[begin]; //找小于key的数 while(begin<end && arr[end]>=key) --end; //与上同理 arr[begin]=arr[end] } //用开始保存的key填补最后一个坑位 arr[begin]=key; return begin; }

3.前后指针法

算法思想： 在序列中选取一个key，将序列画分为俩段，定义一前一后俩个指针，让前一个指针找小于key的值，找到之后与后一个指针对应的值进行交换(把大的值换到后边)，以此将序列达到key前面的值都小于等于key，后边的值都大于等于key的目的。 具体实现：

int PartSort(int* arr,int begin,int end) { int key=arr[end]; int cur=begin; int prev=begin-1; while（cur<end) { //找到小于key的值，并将其换到前边//让prev向前走 if(arr[cur]<key &&++prev!=cur) Swap(&arr[cur],&arr[prev]); ++cur; } //循环走完后，最后一步交换之后prev停留位置的值(arr[prev])是要比key小的， //因此需要向前再走一步，走到大于key的值的位置，然后再将将大的换到后边去 ++prev; Swap(&arr[prrev],&arr[end]); return prev; }

二.对快排的优化

原因： 假设数组已然有序，那么根据前面的算法，依旧要对数组进行划分，直至不可划分为止，然后在对其进行排序，而且每次排序时仍然要一步一步走下去。那么我们是否可以在key这个值的选取上做点文章呢，且看下边代码 三数取中法：

//让key的值直接取数组中间的值 //这样就可以达到提高效率的目的 int GetMidIndex(int* arr,int begin,int end) { int mid=(begin+end)>>1; if (arr[begin] < arr[mid]) { if (arr[mid] < arr[end]) return mid; else if (arr[begin] < arr[end]) return end; else return begin; } else { if (arr[mid] < arr[end]) return mid; else if (arr[begin] < arr[end]) return begin; else return end; } }

在以上的三种对子序列进行排序的算法中只需加上以下俩句代码，便可达到优化的目的。

int midindex=GetMidIndex(arr,begin,end); Swap(&arr[midindex],&arr[end]);