排序是面试常考的的题，对于快速排序是对冒泡排序的一种改进。

对于快排：我在这写了几种实现方法：

//1、快速排序一般

//排序思想：

//1.从数列中挑出一个元素，称为 “基准”（pivot），

//2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

//3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

intPartSort(int*a,intleft,intright){intkey=a[right];//找最右边一个为基准intbegin=left;intend=right-1;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]);}}if(a[begin]>a[right]){swap(a[begin],a[right]);returnbegin;}else{returnright;}}voidQuickSort(int*a,intleft,intright){assert(a);if(left>=right)return;intdiv=PartSort(a,left,right);//快排挖坑法QuickSort(a,left,div-1);QuickSort(a,div+1,right);}

//2、挖坑法

//该方法的基本思想是：

//1．先从数列中取出一个数作为基准数。

//2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

//3．再对左右区间重复第二步，直到各区间只有一个数。

intPartSort1(int*a,intleft,intright){assert(a);intkey=a[right];while(left<right){while(left<right&&a[left]<=key)//从左向右找比key大的值left++;if(left<right){a[right]=a[left];right--;}while(left<right&&a[right]>key)//从右向左找比key小的值right--;if(left<right){a[left]=a[right];left++;}}a[left]=key;returnleft;}voidQuickSort1(int*a,intleft,intright){assert(a);if(left>=right)return;intdiv=PartSort1(a,left,right);//快排挖坑法QuickSort1(a,left,div-1);QuickSort1(a,div+1,right);}

//3、三数取中

//引入的原因：

//虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n ^ 2），要缓解这种情况，就引入了三数取中选取枢轴

//分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N / 2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。

//事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数

intMidfind(int*a,intleft,intright){intmid=left-(left-right)/2;if(a[left]>=a[right]){if(a[right]>a[mid]){returnright;}else{returnmid;}}elseif(a[left]<a[mid]){returnmid;}else{returnleft;}}voidQuickSort2(int*a,intleft,intright)//三数取中{assert(a);if(left>right)return;intmid=Midfind(a,left,right);swap(a[mid],a[right]);intdiv=PartSort(a,left,right);QuickSort2(a,left,div-1);QuickSort2(a,div+1,right);}

//4、单向

//设计思想：

//1.先从数列中取出一个数作为基准数key

//2.设计两个指针，cur，prev，cur开始指向首元素，next开始指向（即cur后一位）。

//3.若next大于key就与往最后交换 end左移

//4.若next小于key就交换cur。next

//5.等于key next就往后移

voidQuickSort3(int*a,intleft,intright)//单向（排序）{assert(a);if(left>right){return;}intkey=a[left];intcur=left;intnext=left+1;intend=right;while(next<=end){if(a[next]>key){swap(a[next],a[end]);end--;}elseif(a[next]<key){swap(a[cur],a[next]);//一直交换，待cur左边都小于key，右边都大于key为止。cur++;next++;}else{next++;}}//此时next==end跳出循环QuickSort3(a,left,cur-1);QuickSort3(a,end+1,right);}

//5、非递归形式(借助栈)

//设计思想：

//1、先进行部分排序分成两部分

//2、先压小再压大

//3、判断栈是否为空

//4、不为空，取栈顶（就是先取出一部分重复步骤2）；

//5、直到栈为空

intPartSort4(int*a,intleft,intright){intkey=a[right];//找最右边一个为基准intbegin=left;intend=right-1;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]);}}if(a[begin]>a[right]){swap(a[begin],a[right]);returnbegin;}else{returnright;}}voidQuickSort4(int*a,intleft,intright){stack<int>ch;if(left<right){intmid=PartSort4(a,left,right);if(left<mid-1){ch.push(left);ch.push(mid-1);}if(mid+1<right){ch.push(mid+1);ch.push(right);}while(!ch.empty()){inttmp=ch.top();ch.pop();intcur=ch.top();ch.pop();intmid=PartSort(a,cur,tmp);if(cur<mid-1){ch.push(cur);ch.push(mid-1);}if(mid+1<tmp){ch.push(mid+1);ch.push(tmp);}}}}