数据结构——快速排序的优化

缺乏、安全感 2023-10-10 15:17 102阅读 0赞

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolih
> 
> [Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率。][Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]

**文章目录**

1.快速排序的特性

2.寻找基准的方法

2.1 Hoare法

2.2挖坑法

2.3前后指针法

3.快速排序优化

3.1划分不均匀

3.2 对后几层使用插入排序

--------------------

## 1.快速排序的特性 ##

时间复杂度：O（N\*log（N））  
空间复杂度：O（log（N））  
稳定性:不稳定 当数据有序时，时间复杂度O（N^2）空间复杂度O（N）

##    2.寻找基准的方法 ##

### 2.1 Hoare法 ###

public static void quickSort(int[] array){
            sort(array,0, array.length-1);
        }
        private static void sort(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
                return;
            }
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        private static int partion(int[] array,int left,int right){
            //记录原始位置下标，方便后面和povit位置交换
            int i = left;
            //寻找参考值
            int povit = array[i];
            while(left<right){
             
    
                while(left < right && array[left] <= povit){ //单独的循环，防止循环内一直到left>right，要加条件
                    right--;
                }
                while(left < right && array[left] >= povit){
                    left++;
                }
                //交换
                swap(array,left,right);
            }
            //交换povit到相遇的位置
            swap(array,left,i);
            return left;
        }

\* 问题1：为什么先从right 向左找？  
\* 从右边开始找基准位置，是因为从左边开始找，左边先找到一个比array\[left\]大的数，然后右边  
\* 向左找，左右肯定相遇，这时候交换，会把比基准值大的数交换到基准位置左边，达不到二分的目的了  
\*  
\* 问题2：为什么左右数组值比较时要带等于号？  
\* 如果出现两边开始时值相同的情况，即左值不小于也不大于右值，两个循环都不会进去  
\* 只会完成左右值一直交换，死循环了

### 2.2挖坑法 ###

private static int paration1(int[] array,int left,int right){
            int povit = array[left];
            while(left<right){
                while (left < right && array[right] >= povit) {
                    right--;
                }
                array[left] = array[right];
                while(left < right && array[left] <= povit){
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = povit;
            return left;
        }

### 2.3前后指针法 ###

private static int paration2(int[] array,int left,int right){
            int prev = left;
            int cur = left+1;
            while(cur <= right){
                if(array[cur] < array[left] && array[++prev] != array[cur]){
                    swap(array,prev,cur);
                }
                cur++;
            }
            swap(array,prev,left);
            return prev;
        }

## 3.快速排序优化 ##

### 3.1划分不均匀 ###

当遇到单分支树的情况，会出现划分不均匀的问题，就会导致递归次数太多

三数取中法

private static void sort1(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
                return;
            }
            //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
            int index = findMidValOfIndex(array,start,end);
            swap(array,start,index);
    
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        /*
        找到中位数
         */
        private static int findMidValOfIndex(int[] array,int start,int end){
            int midIndex = (start+end)/2;
    
            if(array[start] < array[end]){
                if(array[midIndex] < array[start]) {
                    return start;
                } else if (array[end] < array[midIndex]) {
                    return end;
                }
                else {
                    return midIndex;
                }
            }
            else {
                if (array[midIndex] > array[start]){
                    return start;
                } else if (array[midIndex] < array[end]) {
                    return end;
                }
                else {
                    return midIndex;
                }
            }
        }

### 3.2 对后几层使用插入排序 ###

当递归的区间很小的时候我们可以用插入排序，二叉树后几层节点数占总体节点数的大部分，  
递归次数最多也发生在后几层，往后也越来越有序，就不递归了。用插入排序

private static void sort2(int[] array,int start,int end){
            //防止只有左子树或者右子树的情况
            if(start >= end){
               return;
            }
            if(( end-start+1) <= 15){
            //插入排序减少后几层 的递归
                insertSort1(array,start,end);
            }
            //在找基准之前，解决划分不均匀的问题,将关键值改变为中间大小的值后，能解决单分支的情况
            int index = findMidValOfIndex(array,start,end);
            swap(array,start,index);
    
            int povit = partion(array,start,end);
            sort(array,start,povit-1);
            sort(array,povit+1,end);
        }
        public static void insertSort1(int[] array,int left,int right){
            for (int i = left+1; i <= right ; i++) {
                int j = i-1;
                int tmp = array[i];
                for (; j >= left ; j--) {
                    if(array[j] > array[i]){
                        array[j+1] = array[j];
                    }
                    else{
                        break;
                    }
                }
                array[j+1] = tmp;
            }
        }

[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]: http://apifox.cn/a103liucf