【数据结构与算法】快速排序详解（含代码）

布满荆棘的人生 2023-07-17 06:19 5阅读 0赞

## 快速排序原理： ##

*  每一趟**选择**当前所有子序列中的一个**关键字作为枢纽**（一般情况下选数组第一个值），**将子序列中比枢纽小的移动到枢纽前面，比枢纽大的移动到枢纽后面**。
 *  当本趟所有子序列都被枢纽以上述规则划分完毕后会得到**新的两组更短的子序列**（位于枢纽的左右），他们将成为下一趟划分的初始序列集。
 *  利用**递归的思想**，可最终完成排序。。

## 快速排序示例： ##

**原始序列: 3， 1 ，6 ，2 ，5 ，8**  
**位置：**  **i**         **j**

*  下面进行第一趟排序，**将第一个元素3作为枢纽**：

1.  使用 **j** ，从序列最右端开始向前扫描，直到遇到比枢纽3小的数2，停下。  
    原始序列： 3， 1 ，6 ，2 ，5 ，8  
    位置：   i     j
2.  将2**移动**到序列前端i的位置。  
    原始序列： 2， 1 ，6 ，2 ，5 ，8  
    位置：   i     j
3.  使用 **i**，变换扫描方向，从前往后扫描，直到遇到比枢纽3大的数6，**i** 停下。  
    原始序列： 2， 1 ，6 ，2 ，5 ，8  
    位置：      i  j
4.  将6**移动**到 **j** 的位置。  
    原始序列： 2， 1 ，6 ，6 ，5 ，8  
    位置：      i  j
5.  使用 **j** ,从序列右端开始向前扫描，遇到 **i**，停下。  
    原始序列： 2， 1 ，6，6 ，5 ，8  
    位置：      ij
6.  将枢纽3**移动**到 **ij** 的位置。  
    原始序列： 2， 1 ，3 ，6 ，5 ，8  
    位置：      ij

*  至此第一趟排序结束，**此时3左边的元素都比它小，右边的元素都比它大**。接下来按照同样的方法对 \{2， 1\} 和\{ 6 ，5 ，8\} 进行排序，直到得到一个有序的序列。

## 代码： ##

/**
     * Created by xu on 2020/4/12.
     */
    public class 快速排序 {
    
        public static void main(String[] args) {
            int[] nums = {16,7,3,20,17,8};
            sortArray(nums,0,5);
            for (int num : nums) {
                System.out.print(num + " ");
            }
        }
    
        public static void sortArray(int[] nums,int low ,int hight) {
            int temp;
            int i=low,j=hight;
            if(low<hight){
                temp=nums[low];
                while(i!=j)
                {
                    while(j>i&&nums[j]>=temp){
                        j--;
                    }
                    if(i<j){
                        nums[i]=nums[j];
                        i++;
                    }
                    while(j>i&&nums[i]<temp){
                        i++;
                    }
                    if(i<j){
                        nums[j]=nums[i];
                        j--;
                    }
                }
                nums[i]=temp;
                sortArray(nums,low ,i-1);
                sortArray(nums,j+1,hight);
            }
        }
    }

## 快速排序如何改进？ ##

快速排序法是应用最广泛的排序算法之一，最佳情况下时间复杂度是 O(nlogn)。但是最坏情况下可能达到O(n^2)。说明快速排序达到最坏情况的原因。并提出改善方案并实现之。

改进方案：改进选取枢轴的方法  
1、选取随机数作为枢轴。  
但是随机数的生成本身是一种代价，根本减少不了算法其余部分的平均运行时间。  
2、使用左端，右端和中心的中值做为枢轴元。  
经验得知，选取左端，右端，中心元素的中值会减少了快排大约 14%的比较。  
3、每次选取数据集中的中位数做枢轴。  
选取中位数的可以在 O(n)时间内完成。（证明见《算法导论（第二版） 》） P111 第九章中位数  
和顺序统计学：在平均情况下，任何顺序统计量（特别是中位数）都可以在线性时间内得到。  
————————————————  
原文链接：https://blog.csdn.net/lingfengtengfei/article/details/12376889

## 利用快速排序查找第k大的数字： ##

1.  快速排序中确定基准值后，将数组分为两部分，基准元素前面的一定小于基准元素。后面的大于基准元素。
2.  如果基准元素前面的元素个数大于K个，则第K小的数一定在基准元素的前面，没必要进行后面的排序。否则就在后面，没必要前面的排序
3.  直到这个基准元素的位置刚好是K-1

/**
    * Created by xu on 2020/4/12.
    */
    public class 快速排序找第k个大的数 {
    
       public static void main(String[] args) {
           int[] nums = {16,7,3,20,17,8,145,158,45,45,47,65,4,5,6,7};
           int k=14;
           sortArray(nums,0,nums.length-1,k-1);
       }
       public static void sortArray(int[] nums,int low ,int hight, int k) {
           int temp;
           int i=low,j=hight;
           /*
           此处需要格外注意，由于递归函数中进行了运算导致hight == low，且不会进入if中，所以要额外判断
            */
           if(hight == low ) {
               System.out.print(nums[low]);
               return;
           }
           if(low<hight){
               temp=nums[low];
               while(i!=j)
               {
                   while(j>i&&nums[j]>=temp){
                       j--;
                   }
                   if(i<j){
                       nums[i]=nums[j];
                       i++;
                   }
                   while(j>i&&nums[i]<temp){
                       i++;
                   }
                   if(i<j){
                       nums[j]=nums[i];
                       j--;
                   }
               }
               nums[i]=temp;
                /*
           由于此时i==j，基准nums[j]位置已经固定不会再动。并且将数组分为左、右两部分，左部分数小于nums[j],右部分数大于nums[j]，
           1. 如果j==k，那么说明枢纽j所在位置的值就为第k大的值
           2. 如果j>k，那么要求的位置一定在左部分，递归排序左部分即可
           3. 如果j<k，那么要求的位置一定在右部分，递归排序右部分即可
            */
               if(j==k){
               System.out.print(nums[j]);
               return;
               }
               else if(j>k){
                   sortArray(nums,low ,j-1,k);
               }
               else{
                   sortArray(nums,j+1,hight,k);
               }
           }
       }
    }