【DS】9.常用排序算法大总结【上】！！！

ゝ一纸荒年。 2024-04-01 09:39 50阅读 0赞

> 内容概览
> 
> ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-79JNlLn5-1666445339373)(F:\\typora插图\\image-20221022205128136.png)\]][img-79JNlLn5-1666445339373_F_typora_image-20221022205128136.png]
> 
> 由于篇幅原因，排序算法的总结分成了上下两篇
> 
> 上篇对排序算法进行综述，同时详解比较类排序算法；
> 
> 下篇详解非比较类排序算法，同时再次总结排序算法。
> 
> 对于简单的、易于理解的，我直接放了动图，有点绕的我就把画的步骤分解图和动图全放上了，方便使用。【当然如果后序发现哪个容易错会再进行补充】
> 
> 注：所有排序思想描述均以升序为例

#### 文章目录 ####

*   *  一、概览
     *   *  排序算法相关概念
         *  排序算法分类
     *  第一类：交换排序
     *   *  冒泡排序（BubbleSort）
         *   *  思想描述
             *  优化思路描述
             *  动图演示
             *  代码实现
             *  算法效率分析
         *  快速排序（QuickSort）
         *   *  思想描述
             *  静图分析&动图演示
             *  代码实现
             *  算法效率分析
     *  第二类：选择排序
     *   *  直接选择排序（SelectSort）
         *   *  思想描述
             *  动图演示
             *  代码实现
             *  算法效率分析
         *  堆排序（HeapSort）
         *   *  思路分析
             *  动图演示
             *  代码实现
             *  算法效率分析
     *  第三类：插入排序
     *   *  直接插入排序(InsertSort)
         *   *  思想描述
             *  动图演示
             *  代码实现
             *  算法效率分析
         *  希尔排序（ShellSort）
         *   *  思想描述
             *  静图分析&动图演示
             *  代码实现
             *  算法效率分析
     *  第四类：归并排序(MergeSort)
     *   *   *  思想描述
             *  静图分析&动图演示
             *  代码实现
         *  算法效率分析
     *  参考

### 一、概览 ###

#### 排序算法相关概念 ####

排序：排序就是使一串记录按照某个规则排列起来的操作。

稳定性：在待排序的记录序列内，存在多个具有相同关键字的记录，如果经过排序，他们的相对次序不变，那么这个算法就具有稳定性。

内排序&外排序：数据记录在内存中进行排序叫做内部排序。对外存存储的数据记录进行排序的排序叫做外排序。

> 关于稳定与不稳定的判断
> 
> 对于不稳定的[排序算法][Link 1]，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
> 
> 算法思想的本身是独立于编程语言的,所以你写代码去实现算法的时候很多细节可以做不同的处理.采用不稳定算法不管你具体实现时怎么写代码,最终相同元素位置总是不确定的(可能位置没变也可能变了).而稳定排序算法是你在具体实现时如果细节方面处理的好就会是稳定的,但有些细节没处理得到的结果仍然是不稳定的.
> 
> 例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a\[j\].key>=a\[j+1\].key，则两个相等的记录就会交换位置。
> 
> 但是我们一般不会`a[j].key>=a[j+1].key`实现，而是`a[j].key>a[j+1].key`，所以我们一般认为冒泡排序是稳定的。

> 外部排序的步骤：  
> 例如：对10G的数据进行排序
> 
> 1.现将文件切分成200份，每份512M
> 
> 2.分别对512M排序，因为内存可以放的下了，使用内部排序
> 
> 3.进行二路归并，同时对200份有序文件进行处理

#### 排序算法分类 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MB1mc00U-1666445339374)(F:\\typora插图\\image-20221015182632819.png)\]][img-MB1mc00U-1666445339374_F_typora_image-20221015182632819.png]

> 比较类算法需要待排序的元素两两比较，满足一定条件时交换位置，直到排序完成为止，时间复杂度相对来讲比较难计算。一般时间复杂度下限是O(nlogn),以非线性时间运行，所以也叫作非线性排序。
> 
> 非比较类算法只需要遍历数组一遍就可以对元素进行分类，且不超过常数k组，所以时间复杂度也就是O(k+n)=O(n)，突破比较类排序算法下限，以线性时间运行，因此也叫作线性排序。

说明：这里比较类排序又分为了四小类，不过不理解可以略过不影响。

> 希尔排序是直接插入排序的优化，所以两者均属于插入类。
> 
> 选择排序和堆排序都是找最大最小，所以两者都归进选择类。
> 
> 冒泡排序和快速排序都是两个数【很多对，这个操作比较普遍，没有最大最小的限制】进行比较，合适就交换，所以都归进了交换类。
> 
> 归并排序自己属于归并类

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

### 第一类：交换排序 ###

#### 冒泡排序（BubbleSort） ####

##### 思想描述 #####

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。②对每一对相邻的元素做同样的工作，从开始的第一对到最后一对，使得最后一个元素是最大的元素③对所有的元素重复上边的步骤，除了最后一个④持续堆每次越来越少的元素重复上述操作，直至没有数字需要比较。

也就是说，冒泡排序是从后往前依次有序的。

##### 优化思路描述 #####

1.  在原来的基础上增加一个变量flag，使得在元素有序的时候，能够直接停止循环。
2.  使得bubbleSort最好情况下的时间复杂度达到O(n)

##### 动图演示 #####

![在这里插入图片描述][d287184fd8c9476bbd639f5b127edca4.gif_pic_center]

##### 代码实现 #####

//经典版
    public static void bubbleSort(int[]array){
        
        for (int i = 0; i < array.length-1; i++) {
        
            for (int j = 0; j < array.length-1-i; j++) {
        
                if(array[j]>array[j+1]){
        
                    swap(array,j,j+1);
                }
            }
        }
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }
    //优化版
    public static void bubbleSort(int[]array){
        
        for (int i = 0; i < array.length-1; i++) {
        
            boolean flag=false;
            for (int j = 0; j < array.length-1-i; j++) {
        
                if(array[j]>array[j+1]){
        
                    swap(array,j,j+1);
                    flag=true;
                }
            }
            if(flag==false){
        
                break;
            }
        }
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

##### 算法效率分析 #####

> 时间复杂度:最坏：O（n2）；最好：O(n)【优化后】；平均：O(n2)
> 
> 空间复杂度：O(1)
> 
> 稳定性:稳定

#### 快速排序（QuickSort） ####

##### 思想描述 #####

①首先设定一个分界值，我们把它叫做基准，通过这个基准将数组分为左右两部分。②将大于等于基准的值移动到数组右边，小于基准的值移动到数组左边，完成此操作后，基准左边数据全部小于基准，右边数据全部大于等于基准。③之后，左边和右边数据和独立排序。对于左边数据也可以取一个分界值，左边的小于基准，右边的大于等于基准。右边数据同理。④重复上述操作，每个小组左右两边都排好的时候，整个数组也就有序了。

可以看出，快速排序的这个思想是**递归定义**的。

> 但是这个只是一个基本思想，具体基准值的**找寻其实有很多种方法，常见的一般有Hoare法、挖坑法、前后指针法**，同时快排的核心思路就是如何划分，也就是我们的partition如何实现。此处的代码实现是Hoare版的。由于篇幅原因，此处不能展开讲，所以我又将快速排序单独写成了一篇总结，包括快速排序三种partition的实现、快排递归的优化以及非递归实现，需要的可以自行查看。

##### 静图分析&动图演示 #####

![在这里插入图片描述][35344057935b48239f359fac013cd81d.png]

![在这里插入图片描述][3d7e8eaafe524b9fb7db82a12bfc4de3.gif_pic_center]

##### 代码实现 #####

//“基本款”
    public static void quickSort(int[]array){
        
        quick(array,0,array.length-1);
    }
    private static void quick(int[]array,int start,int end){
        
        if(start>=end){
        
            return ;
        }
        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partition(int[]array,int left,int right){
        
        int tmp=left;
        int pivot=array[left];
        while(left<right){
        
            while(left<right&&array[right]>=pivot){
        
                right--;
            }
            while(left<right&&array[left]<=pivot){
        
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmp);
        pivot=array[left];
        return left;
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

##### 算法效率分析 #####

> 时间复杂度：最坏：O（n^2）；最好：O(nlogn)；平均：O(nlogn)
> 
> 空间复杂度：O(logn)
> 
> 稳定性：不稳定

### 第二类：选择排序 ###

#### 直接选择排序（SelectSort） ####

##### 思想描述 #####

①在未排序的序列中，找到最小的元素，存到每轮排序的起始位置。②然后，从未排序的元素中继续找最小的元素放到已排序的序列后边。③以此类推，直至所有元素遍历完成。

##### 动图演示 #####

![在这里插入图片描述][e12d980e9c824f23969041e47673cf57.gif_pic_center]

##### 代码实现 #####

public static void selectSort(int[] array) {
        
        for (int i = 0; i < array.length; i++) {
        
            int minIndex=i;
            for (int j = i+1; j < array.length ; j++) {
        
                if(array[j]<array[minIndex]){
        
                    minIndex=j;
                }
            }
            if(i!=minIndex){
        
    			swap(array,minIndex,i);
            }
        }
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

##### 算法效率分析 #####

> 时间复杂度：
> 
> 最坏：O（n2）；最好：O(n2)；平均：O(n^2)
> 
> 空间复杂度：O(1)
> 
> 稳定性：不稳定

#### 堆排序（HeapSort） ####

> Q：要升序，可以直接创建小根堆吗？
> 
> A：不可以，小根堆只能知道根节点大于左孩子节点和右孩子节点，不能确定左孩子节点和右孩子节点的大小关系。
> 
> 那到底应该怎么做呢？

##### 思路分析 #####

1.  创建大根堆，根节点一定是最大的
2.  “删除堆顶”：每次交换堆顶和堆的最后一个元素
3.  结合堆的删除操作，我们知道这样是元素是从往前依次有序的
4.  最后的一定是最大的，按照数组下标遍历数组得到升序序列。

##### 动图演示 #####

![在这里插入图片描述][ec4d44f76b4444639aeda46a87bc1e53.gif_pic_center]

##### 代码实现 #####

public static void heapSort(int[]array){
        
        creatBigHeap(array);
        int end= array.length-1;
        while(end>0){
        
            swap(array,0,end);
            shitDown(array,0,end);
            end--;
        }
    }
    
    public static  void creatBigHeap(int[]array){
        
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
        
            shitDown(array,parent,array.length);
        }
    }
    //向下调整
    private static void shitDown(int[]array,int parent,int len){
        //结束位置
        int child=2*parent+1;
        while(child<len){
        
            if(child+1<len&&array[child]<array[child+1]){
        
                child++;
            }
            if (array[child]>array[parent]){
        
                swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }
        }
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

##### 算法效率分析 #####

> 时间复杂度：最坏：O（n^2）【单分支的情况】；最好：O(nlogn)；平均：O(nlogn)
> 
> 空间复杂度：O（logn）
> 
> 稳定性：不稳定

### 第三类：插入排序 ###

#### 直接插入排序(InsertSort) ####

##### 思想描述 #####

1.  在待排序的元素中，假设前边n-1个元素都是有序的
2.  将第n个数插入到前边已经排好序的元素中，找到合适的位置，使得插入后n个元素是有序的
3.  按照此方法对所有的元素进行插入，直至整个序列都是有序的。

##### 动图演示 #####

![在这里插入图片描述][ae90ae5b81ca4942ba73a897347860df.gif_pic_center]

##### 代码实现 #####

public static void insertSort(int[]array){
        
        for (int i = 1; i < array.length; i++) {
        
            int tmp=array[i];
            int j=i-1;
            for (; j>=0; j--) {
        
                if(array[j]>tmp){
        
                    array[j+1]=array[j];
                }else{
        
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

##### 算法效率分析 #####

> 时间复杂度：最坏：O（n2）；最好：O(n2)；平均：O(n^2)
> 
> 空间复杂度：O（1）
> 
> 稳定性：稳定

#### 希尔排序（ShellSort） ####

##### 思想描述 #####

先取一个小于n的整数d1作为第一个[增量][Link 2]，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行[直接插入排序][Link 3]；然后，取第二个增量d2 ……直至增量为负数

##### 静图分析&动图演示 #####

![在这里插入图片描述][6b5c4f820e7844ccb5c9fec944fb2cab.png]

![在这里插入图片描述][b64b8b0fabed4fa299017d43ac0976d0.gif_pic_center]

##### 代码实现 #####

public static  void shellSort(int[]array){
        
        int gap= array.length;
        while(gap>1){
        
            gap/=2;
            shell(array,gap);
        }
    }
    private static  void shell(int[]array,int gap){
        
        for (int i = gap; i < array.length; i++) {
        
            int tmp=array[i];
            int j=i-gap;
            for (; j>=0; j-=gap) {
        
                if(array[j]>tmp){
        
                    array[j+gap]=array[j];
                }else{
        
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

##### 算法效率分析 #####

> 时间复杂度：平均：O(n^1.3)
> 
> 空间复杂度：O（1）
> 
> 稳定性：不稳定

### 第四类：归并排序(MergeSort) ###

##### 思想描述 #####

①申请空间，使其大小为两个已经[排序][Link 4]序列之和，该空间用来存放合并后的序列②设定两个[指针][Link 5]，最初位置分别为两个已经排序序列的起始位置③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置④重复步骤3直到某一指针超出序列尾⑤将另一序列剩下的所有元素直接复制到合并序列尾

##### 静图分析&动图演示 #####

![在这里插入图片描述][3eac9a1a3b29438a94b362eae567e678.gif_pic_center]

##### 代码实现 #####

//归并排序代码实现
    public static void mergeSort(int[] array){
        
        mergeSortChild(array,0,array.length-1);
    }
    public static void mergeSortChild(int[] array, int left, int right){
        
        if(left>=right){
        
            return ;
        }
        int mid=(left+right)/2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid+1,right);
        merge(array,left,mid,right);
    }
    public static void merge(int[]array,int left,int mid,int right){
        
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] tmpArr=new int[right-left+1];
        int k=0;
        while(s1<=e1&&s2<=e2){
        
            if(array[s1]<=array[s2]){
        
                tmpArr[k++]=array[s1++];
            }else{
        
                tmpArr[k++]=array[s2++];
            }
        }
        while(s1<=e1){
        
            tmpArr[k++]=array[s1++];
        }
        while(s2<=e2){
        
            tmpArr[k++]=array[s2++];
        }
        //array= Arrays.copyOf(tmpArr);//怎么返回指定范围？
        for (int i = left; i <=right ; i++) {
        
            array[i]=tmpArr[i-left];//或者i从0开始，array[i+left]=tmpArr[i];
        }
    }
    public static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

#### 算法效率分析 ####

> 时间复杂度：最坏：O（nlogn）；最好：O(nlogn)；平均：O(nlogn)
> 
> 空间复杂度：O(n)
> 
> 稳定性：稳定

### 参考 ###

> [稳定性问题][Link 6]

[img-79JNlLn5-1666445339373_F_typora_image-20221022205128136.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ab258d7589c84e3e8801bb459f2a5917.png
[Link 1]: https://link.zhihu.com/?target=http%3A//baike.baidu.com/view/297739.htm
[img-MB1mc00U-1666445339374_F_typora_image-20221015182632819.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ae533a7037f74a27bbb6fb8e3b1ac7e6.png
[d287184fd8c9476bbd639f5b127edca4.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/75c383c2fed241288e72f2d36602903d.gif
[35344057935b48239f359fac013cd81d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5fae03b1bbca4f2f8a69d2bcdc0bb3ab.png
[3d7e8eaafe524b9fb7db82a12bfc4de3.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/38774d2c94b944caaf4bea16c7c2997a.gif
[e12d980e9c824f23969041e47673cf57.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c407af0b12c642a8a2bb6bc98097b365.gif
[ec4d44f76b4444639aeda46a87bc1e53.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0d18607ca3994785a93a3787c80924ca.gif
[ae90ae5b81ca4942ba73a897347860df.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/87d279af04344c9a93f43daa6836e21f.gif
[Link 2]: https://baike.baidu.com/item/%E5%A2%9E%E9%87%8F?fromModule=lemma_inlink
[Link 3]: https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F?fromModule=lemma_inlink
[6b5c4f820e7844ccb5c9fec944fb2cab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/111500041eb543318d01b760484a7ad4.png
[b64b8b0fabed4fa299017d43ac0976d0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9634e21dc8d0456886d9b838440d62af.gif
[Link 4]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F?fromModule=lemma_inlink
[Link 5]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88?fromModule=lemma_inlink
[3eac9a1a3b29438a94b362eae567e678.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bcd5735a322b4fc783dc5da16a369e02.gif
[Link 6]: https://zhuanlan.zhihu.com/p/116046849