快速排序简介

╰+哭是因爲堅強的太久メ 2022-11-20 12:56 121阅读 0赞

**一：快速排序思想：**  
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，已达到整个序列有序的目的

**首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分  
为“比基准值小的数”和“比基准值大的数”这两个类别**  
\[ 比基准值小的数 \] 基准值 \[ 比基准值大的数 \]  
**动图解释：**  
![在这里插入图片描述][20201028220002466.gif_pic_center]

**二：代码：**

void quickSort(int arr[],int low,int high)
        {
        
                int temp;
                int i=low,j=high;
                if(low< high){
        
                     temp=arr[low];//中间轴的值
                     while（i<j）
                        {
        
                         while(j>i &&arr[j]>=temp) --j;
                          if(i<j)
                           {
        
                             arr[i]=arr[j];//如果 比中间轴的值小  不满足上面的while  则 将arr[j]的值 移到arr[i]
                                 ++i;
                            }
                          while(i<j &&arr[i]<temp) ++i;
                          if(i<j)
                           {
        
                             arr[j]=arr[i];//如果 比中间轴的值小  不满足上面的while  则 将arr[j]的值 移到arr[i]
                                 --j;
                            }
                            }
                    arr[i]=temp;//将中间轴的值 放入中间
                     quickSort(arr,low,i-1);//分别递归排序其左边
                     quickSort(arr,i+1,high);//递归排序其右边
                 }
     }

**三：分析性能**

**可优化的点：**  
1.优化选取枢轴  
2.优化不必要的交换  
3.优化小数组时的排序方案  
4.优化递归操作

时间复杂度  
最优情况下：时间复杂度为O(nlongn)  
最坏情况下：时间复杂度为O(n2)  
空间复杂度：  
最好 ：log2N  
最坏：O(n)  
平均：O(logn)  
分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度  
为原本的一半，那么快速排序的运行时间和归并排序的一样，都为 O(nlogn)。和归并排  
序类似，将序列对半分割 log 2 n 次之后，子序列里便只剩下一个数据，这时子序列的排  
序也就完成了。

每行中每个数字都需要和基准值比较大小，因此每行所需的运行时间为 O(n)。由此  
可知，整体的时间复杂度为 O(nlogn)。  
如果运气不好，每次都选择最小值作为基准值，那么每次都需要把其他数据移到基  
准值的右边，递归执行 n 行，运行时间也就成了 O(n 2 )。这就相当于每次都选出最小值  
并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字  
被选为基准值的概率都相等，那么需要的平均运行时间为 O(nlogn)。

[20201028220002466.gif_pic_center]: /images/20221120/cde77989ec624e68a48ebd648ed7418d.png