排序（五）【数据结构】

快速排序核心思想将待排序序列围绕着基本值分成两部分左边部分都小于基准值右边部分都大于基准值第一种方法递归优点:简单 缺点:需要单独开辟辅助空间brr数组第二种方法挖空法很重要快速排序的单次划分函数 PartitionintPartition(intarr[],intleft,intright){//挖空法步骤:核心函数(単吹划分函数 Partition)//1.默认将第一个值(arr[left])当做基准值拷贝给tmpinttmparr[left];//2.进入到while循环(循环条件是两个指针没有相遇)while(leftright){//3.先从右至左找比基准值小的值找到后扔到左边空位上|()while(leftrightarr[right]tmp)right--;//while循环退出有两种情况//情况1left和right相遇了说明划分可以结束了基准值要放回去了//情况2left和right没有相遇但是找到了一个小于或等于tmp的值if(leftright){break;}arr[left]arr[right];//4.再从左至右找比基准值大的值找到后扔到右边空位上|()while(leftrightarr[left]tmp)left;//while循环退出有两种情况//情况1left和right相遇了说明划分可以结束了基准值要放回去了//情况2left和right没有相遇但是找到了一个大于tmp的值if(leftright){break;}arr[right]arr[left];}//5.重复345过程直到两个指针相遇while循环退出//6.while循环退出后则两个指针相遇的位置就是基准值所该在的位置(把tmp拷贝回去)//7.将最后基准值所在下标返回arr[left]tmp;//arr[right] tmp;returnleft;//return right;}快排的递归函数voidQuick(intarr[],intleft,intright){if(leftright){return;}intparPartition(arr,left,right);//以基准值所在下标par可以将原本的范围[LEFTRIGHT]分成两个部分//左边部分的有效范围[LEFT, par-1]//右边部分的有效范围[par1, RIGHT]Quick(arr,left,par-1);Quick(arr,par1,right);/*if (left par - 1) { Quick(arr, left, par - 1); } if (par 1 right) { Quick(arr, par 1, right); } */}快速排序主体voidQuick_Sort(intarr[],intlen){Quick(arr,0,len-1);}快速排序的非递归实现#includestack//快速排序非递归实现voidQuick_No_Recursion(intarr[],intlen){//0.断言assert(arr!NULL);//1.申请一个栈并将初始状态下的0,len-1入到栈里std::stackintst;st.push(0);st.push(len-1);//2.进入while循环循环条件是栈不空即可while(!st.empty()){//3.进来之后取出一组数据用来表示当前partition函数要单次划分的数据的左右边界intrightst.top();st.pop();intleftst.top();st.pop();//4.调用单次划分函数partition并将其返回值返回的是其基准值所在下标用变量par接收下intparPartition(arr,left,right);//5.再对当前基准值两侧的数据个数进行判定如果数据量在2个及以上则将其左右边界一起压到栈里if(leftpar-1){st.push(left);st.push(par-1);}if(par1right){st.push(par1);st.push(right);}}//6.当while循环结束代表所有要处理的数据块都被partition函数处理掉了}快速排序的特点数据越乱反而效率越高优化方案方案1数据量如果少的话直接转头去调用直接插入排序//快速排序voidQuick_Sort(intarr[],intlen){//优化方法1数据量如果小的话直接去调用直接插入排序if(len100){Insert_Sort2(arr,len);return;}Quick(arr,0,len-1);}方案2三数取中法//三数取中法voidThree_Nums_GetMid(intarr[],intleft,intright){intmid(rightleft)/2;//1.先对左端值和中间值进行比较如果左端值大于中间位置值则交换if(arr[left]arr[mid]){inttmparr[mid];arr[mid]arr[left];arr[left]tmp;}//此时一定左端和中间位置的那个较大值一定在中间//2。再对此时中间位置和右端值进行比较如果中间位置值大于右端值则交换if(arr[mid]arr[right]){inttmparr[mid];arr[mid]arr[right];arr[right]tmp;}//此时一定三个位置中的那个最大值在此时的右端位置而我们要找的那个不大不小的值在中间//3.对此事左端值和中间位置值进行比较如果左端值小于中间位置值则交换if(arr[mid]arr[left]){inttmparr[mid];arr[mid]arr[left];arr[left]tmp;}}方案3随机数法