/*
快速排序
基本思想
对于每个选定排序的基准数据，在其馀位置，将小于基准值的数据定位在基准值的左侧，将大于基准值的数据定位在基准值的右侧
如果分割一次后，此基准值左右有两个以上的数据，则继续分割排序，直到每个数字按顺序排列为止
递归实现quick_sort1(int*arr，int len ) :的高速一次分割的时间复杂度为o(logn )最坏情况下的有序条件下的时间复杂度为o ) n^2)
总的时间复杂度为o(n*logn )
非递归实现quick_sort2(int*arr，int len )
快摆三种实现方式
第一，选择第一个元素或最后一个元素作为基准代码。 Quick_Sort1和Quick_Sort2
这样的缺点是，如果给定的序列有很多时间复杂度过大，是被选择的基准点的话就失去了意义，就不能称为基准值了
第二种随机值法
在大多数情况下，o(logn )最好的情况下才能保证时间复杂度，但在最坏的情况下，当数组整体的数字相等时，时间复杂度达到o ) n^2
第三种三数取得中
找到lowhighmid=low((high-low )1)//计算数组中间元素的下标
取得与这三个下标相对应的最小值，就可以确保arr[low]为这三个数之间的第二大的值，与通常的分割函数相同
*/
voidswap(int*a，int *b ) ) {int tmp=*a； *a=*b； *b=tmp； //第一类划分函数：将最初数字作为基准值进行一次划分，最后将基准的下标intpartion(int*arr，int low，int high ) if ) arr==null ) return -1； int tmp=arr[low]； while(lowhigh ) while () lowhigh ) arr[high]=tmp ) high----； (if ) low==high )//如果有小于标准值的东西，放在low的位置) {break； }else{arr[low]=arr[high]； }while () lowhigh ) arr[low]=tmp ) low； }if(low==high ) ) {break； }else{arr[high]=arr[low]； }}arr[low]=tmp； 返回低； //第二类型划分函数：随机地划分基准划分intpart(int*arr，int low，int high ) srand ) (unsigned ) time ) null ) )； //随机位置int pivotPos=rand () % ) %(high - low ) low； //将该随机位置的值更换为low位置的值后，又和通常的分割函数一样，使用swap(arr[pivotpos]，arr[low] )； int tmp=arr[low]； while(lowhigh ) while () lowhigh ) arr[high]=tmp ) high----； (if ) low==high )//如果有小于标准值的东西，放在low的位置) {break； }else{arr[low]=arr[high]； }while () lowhigh ) arr[low]=tmp ) low； }if(low==high ) ) {break； }else{arr[high]=arr[low]； }}arr[low]=tmp； 返回低； (/)第三分区函数intselect_mid(int*ARR，int low，int high ) )/intmid=low ) (high-low )1)； //计算数组中间元素的下标intmid=low () ) (high-low )1)//使用三数计算中法选择枢轴if(arr[mid]arr[high] ) /目标： arr [ mmid ] ) (if ) arr[low]arr[high] ) /目标：arr[low]=arr[high] ) swap(arr[low]，arr[high] )； (if ) arr[mid]arr[low](/目标：arr[low]=arr[mid] ) swap ) arr[mid]，arr[low] )； } return arr[low]； (/三角剖分中的一次划分intpart1(int*arr，int low，int high ) inttmp=select_mid ) arr，low，high )； {while(lowhigh ) while
((low < high) && arr[high] >= tmp ){high--;}if(low == high)//如果遇到比基准值小的 放到low的位置{break;}else{arr[low] = arr[high];}while((low < high) && arr[low] <= tmp){low++;}if(low == high){break;}else{arr[high] = arr[low];}}arr[low] = tmp;return low;}static void Quick(int *arr,int start,int end){int par = part1(arr,start,end);if(par > start + 1){Quick(arr,start,par-1);}if(par < end -1){Quick(arr,par+1,end);}}void Quick_Sort1(int *arr,int len){if(arr == NULL ||len < 0)return;for(int i = 0 ;i < len - 1 ;++i){Quick(arr,0,len-1);}}快排非递归实现
//用栈保存每一次的一对low和high区间 空间复杂度为O(n*logn)void Quick_Sort2(int *arr,int len){if( arr == NULL ||len < 0)return ;int low = 0;int high = len - 1;int par = partion(arr,low,high);stack<int> st;if(par > low + 1){st.push(low);st.push(par-1);}if(par < high - 1){st.push(par+1);st.push(high);}while(!st.empty()){int high = st.top();st.pop();int low = st.top();st.pop();int par = partion(arr,low,high);if(par > low + 1){st.push(low);st.push(par-1);}if(par < high - 1){st.push(par+1);st.push(high);}}}/*
快排优化一
在low和high之间的举例为10以内时，可以选择直接插入排序 节省时间
*/
//快排优化一 在划分到适合的长度进行直接插入排序void insert_sort(int *arr,int low,int high){if(arr == NULL || low < 0 || high < 0)return ;int tmp = 0;int j;for(int i = low+1;i < high; i++){tmp = arr[i];for(j = i-1;j >= 0;j--){if(arr[j] > tmp){arr[j+1] = arr[j];}else{break;}}arr[j+1] = tmp;}}static void Quick1(int *arr,int start,int end){int par = part1(arr,start,end);if(end - start + 1 < 10){insert_sort(arr,start,end);}else{if(par > start + 1){Quick(arr,start,par-1);}if(par < end -1){Quick(arr,par+1,end);}}}void Quick_Sort3(int *arr,int len){if(arr == NULL ||len < 0)return;for(int i = 0 ;i < len - 1 ;++i){Quick(arr,0,len-1);}}/*
快排优化二
在一次划分之后 将与基准值相等的元素聚集在一起不再进行下一次的划分操作 可以减少迭代查找次数
具体操作将与基准值相等的数放到数组的两端 一次划分完成后 将这些数字挪回基准值得范围 具体过程如下图所示
*/
//快排优化二 一次划分后将基准值调至靠近基准值周围 与基准值相等的数字不再参加下一次划分void QuickSort(int *arr,int low,int high){int first = low; int last = high; int left = low; int right = high; int leftLen = 0; int rightLen = 0; //一次分割 int key = Select_Mid(arr,low,high);//使用三数取中法选择枢轴 while(low < high) { while(high > low && arr[high] >= key) { if (arr[high] == key)//处理相等元素 { swap(&arr[right],&arr[high]); right--; rightLen++; } high--; } arr[low] = arr[high]; while(high > low && arr[low] <= key) { if (arr[low] == key) { swap(&arr[left],&arr[low]); left++; leftLen++; } low++; } arr[high] = arr[low]; } arr[low] = key; //一次快排结束 //把与枢轴key相同的元素移到枢轴最终位置周围 int i = low - 1; int j = first; while(j < left && arr[i] != key) { swap(&arr[i],&arr[j]); i--; j++; } i = low + 1; j = last; while(j > right && arr[i] != key) { swap(&arr[i],&arr[j]); i++; j--; }//如果左右两端都还有超过两个数据 那么就需要进行划分排序if(low-1 > first+1){QuickSort(arr,first,low - 1 - leftLen);}if(low+1 < last-1){QuickSort(arr,low + 1 + rightLen,last);}}