七种基于比较的排序，基于Java实现，收藏一下？

た入场券 2023-10-01 22:27 97阅读 0赞

## 一.总览 ##

![0b98d6c08da8cb08afe4d5af31f3b5a1.png][]

## 二.基于比较的排序算法 ##

## 1.简单插入排序（重点） ##

注意：区间较小时，最快  
**原理：**  
一组数据array\[\]，认为以下标i为分界，\[0，i+1)认为有序，\[i+1,array.length)无序，从无序数据中每次取出一个数据，插入有序数据中

![f81a1decae9c8b487cb86d68937322a8.gif][]

**代码实现：**

public static void insertSort(long []array){
            //数据一共有array.length个
            //所以，子操作需要执行array.length次
            //减不减一都可以，减一认为第一个数已经有序
            for (int i = 0; i <array.length-1 ; i++) {
                //有序[0,i+1)  例如刚开始[0,1)有序
                //无序[i+1,array.length)
                //抓取出来的数是[i+1]
    
                long key=array[i+1];
                int j=0;
                //依次在有序区间进行比较
                for ( j = i; j>=0 ; j--) {
                    //[j]就是需要和key比较的数
                    /**
                     * key<array[j]   把array[j]往后移 继续往前比较
                     * key==array[j]  把key放入array[j]的后边
                     * key>array[j]   把key放入array[j]的后边
                     */
                    if(key<array[j]){
                        array[j+1]=array[j];
                    }else {
                        break;
                    }
                }
                array[j+1]=key;
    
            }
        }

**性能分析：**

![088b32fe2af4e6f243ec4a953314d3be.png][]

## 2.冒泡排序（重点） ##

原理：

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序

无序区间：\[0,array,length-i)

有序区间：\[array.length-i,array.length)

从下标j开始，将其与下标j+1依次比较，如果大于，交换。

![939723da4364538eeeb56b047049d818.gif][]

**代码实现：**

public static void bubblingSort(long []array){
        //外层循环，需要多少次冒泡的过程
            for (int i = 0; i <array.length ; i++) {
                //无序区间：[0,array,length-i)
                //有序区间[array.length-i,array.length)
    
                //假设数组已经有序
                boolean isSorted=true;
    
                //冒泡过程
                //只在无序区间中进行
                //循环到无序区间的倒数第二个数，然后倒数第二会和倒数第一再比较
                for (int j  = 0; j  <array.length-i-1 ; j ++) {
                    if(array[j]>array[j+1]){
                      swap(array, j, j+1);
                      //交换过，说明数组无序
                        isSorted=false;
                    }
                }
    
                //如果数组有序，退出循环
                if(isSorted){
                    break;
                }
            }
        }
    
        public static void swap(long []array,int i,int j){
         long t=array[i];
         array[i]=array[j];
         array[j]=t;
        }

**性能分析：**

![6262153b8670c070222b34239facf842.png][]

## 3.简单选择排序 ##

\*\*原理：

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。

以选取最大为例：

无序区间\[0,array.length-i)

有序区间\[array.length-i,array.length)

动态图为选取最小为例：

![e64e58313770b250e6d7e79db6939b49.gif][]

**代码实现：**

//选择排序
    
        /**
         *选择大的数
         * 前面为有序区间，后面为无序区间
         * 再无序区间中遍历，找到最大的数，和无序区间的最后一个数进行交换
         */
        public static void selectSort(long[]array){
            //一共多少次选择的过程
            for (int i = 0; i <array.length ; i++) {
                //无序区间：[0,array.length-i)
                //有序区间：[array.length-i,array.length)
                //记录无序区间最后一个值的下标和值
                int maxindex=array.length-i-1;
                long key=array[array.length-i-1];
                for (int j = 0; j <array.length-i ; j++) {
                    if(array[j]>key){
                        maxindex=j;
                        key=array[j];
                    }
                }
                //期望maxIndex指向无序区间的最大值的下标
                //交换最大数所在下标和无序区间最后一个数的下标
                swap(array, maxindex, array.length-i-1);
            }
        }
    
        public static void swap(long[]array,int i,int j){
            long t=array[i];
            array[i]=array[j];
            array[j]=t;
        }

**性能分析：**

![ef96e60c9ee17bbe1beae8f7b93f1e31.png][]

## 4.堆排序 ##

**原理：**  
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。  
注意：排升序要建大堆，排降序要建小堆，否则不行

![127bce22e52fedb402d5f5c20e7b8928.gif][]

**代码实现：**

public class HeapSort {
        public static void heapSort(long[]array,int size){
           //1.建大堆
              bulidHeap(array,size);
            //2.进行选择的过程，一共需要array.length-1组
            for (int i = 0; i <array.length-1 ; i++) {
                //无序区间：[0,array.length-i)
                //有序区间：[array.length-i,array.length)
                swap(array,0,array.length-i-1);
                //此时无序区间：[0,array.length-i-1)
                //无序区间的个数为array.length-i-1
                adjustDown(array,array.length-i-1,0);
            }
        }
        //交换
        public static void swap(long[]array,int i,int j){
            long t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
        //建大堆
        public static void bulidHeap(long []array,int size){
            int lastNodeIndex=size-1;
            int lastParentIndex=(lastNodeIndex-1)/2;
            for (int i = lastParentIndex; i >=0 ; i--) {
                adjustDown(array,size,i);
            }
    
    
        }
        //向下调整
        public static void adjustDown(long[]array,int size,int index){
            while (true){
                //堆是完全二叉树，一定有左孩子
                int leftIndex=index*2+1;
                //如果没有左孩子，则为叶子结点,直接return
                //等于size也超出了数组下标范围
                if(leftIndex>=size){
                    return;
                }
                //找最大的孩子
                int maxIndex=leftIndex;
                int rightIndex=leftIndex+1;
                //如果右孩子存在且右孩子的值大于左孩子，则将最大值的下标改为右孩子
                if(rightIndex<size&&array[rightIndex]>array[leftIndex]){
                   maxIndex=rightIndex;
                }
                //比较maxIndex和index位置的值，如果maxIndex大，则交换，否则retrun
                if(array[maxIndex]<=array[index]){
                    return;
                }
                swap(array, maxIndex, index);
                index=maxIndex;
            }
        }
    }

**性能分析：**

![cfc1815f289002b6d2543e992983ccac.png][]

## 5.希尔排序 ##

原理：

分组插入排序

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有

距离为的记录分在同一组内，并对每一组内的记录进行插入排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

步骤：

1.分为gap组，认为gap之前的都是有序的（每组一个数）

2.对分好的每一个组，在组内进行插入排序

![7688b9dae64c965fb5848497af932f34.gif][]

**代码实现：**

//希尔排序(带间隔的插入排序）
    public class ShellSort {
        public static void shellSort(long[]array){
            int gap=array.length/2;
    
            while (true){
                insertSortWithGap(array, gap);
                if(gap==1){
                    break;
                }
                gap=gap/2;
            }
        }
    
    
        public static void insertSortWithGap(long[]array,int gap){
            //分为gap组，认为gap之前的都是有序的（每组一个数）
            for (int i =gap; i <array.length ; i++) {
                //记录需要比较的值
              long key=array[i];
              int j=0;
              //对每组的值进行插入排序，每组间隔为gap个
                for (j =i-gap; j >=0 ; j=j-gap) {
                    if(key<=array[j]){
                        array[j+gap]=array[j];
                    }else {
                        break;
                    }
                }
                array[j+gap]=key;
            }
        }
    }

**性能分析：**

![e9b0302774f6f879653bed5256c05883.png][]

## 6.快速排序（重点） ##

**原理：**  
快速排序原理：

![7cee3a5be4999eb2b04515c2c3b08c71.png][]

partition分割原理：Hover法

![714c51816b0d8f74c3f515ef183d2473.png][]

![7a6745e50eff06251b00479051241836.gif][]

**步骤：**  
1.选择一个数key（一般选最左边）  
2.做partition分隔（小的放左边，大的放右边）  
3.分别做左右两个小区间按相同的方式处理（递归）  
4.知道（小区间有序：区间数的个数size<=1)

**代码实现：**

public class QuickSort {
        public static void quickSort(long[]array){
            //排序的区间为lowIndex到highIndex
            quickSortInteral(array,0,array.length-1);
        }
    
        private static void quickSortInteral(long[]array,int lowIndex,int highIndex){
            //记录区间内数的个数
            //区间是[lowIndex,highIndex]
            int size=highIndex-lowIndex+1;
            //当区间内个数小于等于一时，区间有序
            if(size<=1){
                return;
            }
    
            //1.选择其中一个数出来（最左边）->array[lowIndex]
            //2.执行partition（分隔），小的数放左，大的数放右
    
            //keyIndex是经过partition后，选出来的数的最终下标
            int keyIndex=partitionHover(array,lowIndex,highIndex);
    
            //keyIndex左边： 左边的lowIndex=lowIndex，highIndex=keyIndex-1
            //keyIndex右边： 右边的lowIndex=keyIndex+1，highIndex=highIndex
    
            //分别左左右区间相同处理->递归
            quickSortInteral(array, lowIndex, keyIndex-1);
            quickSortInteral(array, keyIndex+1, highIndex);
    
        }
        //区间为array[lowIndex,highIndex]
        //1.选择array[lowIndex]作为特殊的数
        //2.需要遍历整个区间（不能遗漏任何数），与选择出来的数进行比较
        //3.保证小于等于的在最左边，大于等于的数在最右边（但没有顺序要求）
        private static int partitionHover(long []array,int lowIndex,int highIndex){
           int leftIndex=lowIndex;
           int rightIndex=highIndex;
           //选择的数是最左边的
            //注意：选择最左边的数key，要让rightIndex先动起来，不然右边全小于key的情况不好考虑
            long key=array[lowIndex];
            while (leftIndex<rightIndex){
                while (leftIndex<rightIndex&&array[rightIndex]>=key){
                    //当右边的值大于key，rightIndex继续往左走
                    rightIndex--;
                }
                while (leftIndex<rightIndex&&array[leftIndex]<=key){
                    //当左边的值小于key，leftIndex继续往右走
                    leftIndex++;
                }
                //当leftIndex和rightIndex都停下来时，交换
                swap(array, leftIndex, rightIndex);
    
                //当leftIndex和rightIndex相遇时，循环结束
            }
            //交换开始选中的值leftIndex和上述停止相遇的值lowIndex
            swap(array, leftIndex, lowIndex);
    
            //返回选中的key值当前的位置
            return leftIndex;
    
        }
    
        private static void swap(long[]array,int i,int j){
            long t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
    }

**性能分析：**

![b4d429290288678a1e1f1b1c540c0f43.png][]

时间复杂度：每次partition的时间为O（n），然后乘以二叉树的高度

## 7.归并排序（二路归并）（重点） ##

**原理：**  
归并思想：

![c04d43ac29d61d5dfe1a213267a29334.png][]

数组合并思想：  
创建一个新数组，数组大小个原数组大小相等  
遍历将左边和右边两个有序区间，并比较。如同打擂台，小的数放入新数组  
最后将新创建的数组复制到原数组即可

**整体思想：**

![7c1785f3d576f8a257f6b73d326ad070.png][]

![d30e1e973097b045be36fa8e67083ffc.gif][]

**代码实现：**

//归并排序
    public class MergeSort {
        public static void mergeSort(long[]array){
            mergeSortInternal(array,0,array.length);
    
        }
    
        //区间范围是左闭右开
        //array[lowIndex,highIndex)
        private static void mergeSortInternal(long[] array, int lowIndex, int highIndex) {
    
            int size=highIndex-lowIndex;
            if(size<=1){
                return;
            }
            int middleIndex=(highIndex+lowIndex)/2;
            //区间被分成左右两份
            //左区间：[lowIndex,middleIndex)
            //右区间: [middleIndex,highIndex)
    
    
            //递归
            mergeSortInternal(array, lowIndex, middleIndex);
            mergeSortInternal(array, middleIndex, highIndex);
    
    
             //左右两个区间都有序
            mergeLeftAndRight(array,lowIndex,middleIndex,highIndex);
    
    
        }
    
        //合并两个有序区间
        private static void mergeLeftAndRight(long[] array, int lowIndex, int middleIndex, int highIndex) {
            //两个区间数的总数
            int size=highIndex-lowIndex;
            long[]extraArray=new long[size];
    
            //遍历（三个下标，一个数组一个）
            int leftIndex=lowIndex;
            int rightIndex=middleIndex;
            int extraIndex=0;
    
            //两个队伍都有人
            while (leftIndex<middleIndex&&rightIndex<highIndex){
                //加等于保证稳定性
                if(array[leftIndex]<=array[rightIndex]){
                    extraArray[extraIndex]=array[leftIndex];
                    leftIndex++;
                }else {
                    extraArray[extraIndex]=array[rightIndex];
                    rightIndex++;
                }
                extraIndex++;
            }
    
            //直到有个队伍没有人
            if(leftIndex<middleIndex){
                //左边队伍有人
                while (leftIndex<middleIndex){
                    extraArray[extraIndex++]=array[leftIndex++];
                }
            }else {
                //右边队伍有人
                while (rightIndex<highIndex){
                    extraArray[extraIndex++]=array[rightIndex++];
                }
            }
    
            //最后把数据从extraArray新数组搬回去
            //新数组extraArray[0,size)
            //搬回去的下标范围[lowIndex,highIndex)
            for (int i = 0; i <size; i++) {
                array[i+lowIndex]=extraArray[i];
            }
        }
      
    }

**性能分析：**

![a7ac4fdcb133f32a6d630bb10b384196.png][]

## 三.性能总结 ##

![ffea5069ffcb139d9af89af8198b15c4.png][]

![a7bb6311263fc3cbfa1480b390e82a89.png][]

## 四.jdk中提供的排序方法 ##

![826fe208b934945ecacb2a02caccb0c7.png][]

## 五.海量数据的排序 ##

![7369f116feb39349c22ea70ba8f93b09.png][]

![8805e7db8dfb4631a59ad07e8b1c57b3.jpeg][]

[0b98d6c08da8cb08afe4d5af31f3b5a1.png]: https://img-blog.csdnimg.cn/img_convert/0b98d6c08da8cb08afe4d5af31f3b5a1.png
[f81a1decae9c8b487cb86d68937322a8.gif]: https://img-blog.csdnimg.cn/img_convert/f81a1decae9c8b487cb86d68937322a8.gif
[088b32fe2af4e6f243ec4a953314d3be.png]: https://img-blog.csdnimg.cn/img_convert/088b32fe2af4e6f243ec4a953314d3be.png
[939723da4364538eeeb56b047049d818.gif]: https://img-blog.csdnimg.cn/img_convert/939723da4364538eeeb56b047049d818.gif
[6262153b8670c070222b34239facf842.png]: https://img-blog.csdnimg.cn/img_convert/6262153b8670c070222b34239facf842.png
[e64e58313770b250e6d7e79db6939b49.gif]: https://img-blog.csdnimg.cn/img_convert/e64e58313770b250e6d7e79db6939b49.gif
[ef96e60c9ee17bbe1beae8f7b93f1e31.png]: https://img-blog.csdnimg.cn/img_convert/ef96e60c9ee17bbe1beae8f7b93f1e31.png
[127bce22e52fedb402d5f5c20e7b8928.gif]: https://img-blog.csdnimg.cn/img_convert/127bce22e52fedb402d5f5c20e7b8928.gif
[cfc1815f289002b6d2543e992983ccac.png]: https://img-blog.csdnimg.cn/img_convert/cfc1815f289002b6d2543e992983ccac.png
[7688b9dae64c965fb5848497af932f34.gif]: https://img-blog.csdnimg.cn/img_convert/7688b9dae64c965fb5848497af932f34.gif
[e9b0302774f6f879653bed5256c05883.png]: https://img-blog.csdnimg.cn/img_convert/e9b0302774f6f879653bed5256c05883.png
[7cee3a5be4999eb2b04515c2c3b08c71.png]: https://img-blog.csdnimg.cn/img_convert/7cee3a5be4999eb2b04515c2c3b08c71.png
[714c51816b0d8f74c3f515ef183d2473.png]: https://img-blog.csdnimg.cn/img_convert/714c51816b0d8f74c3f515ef183d2473.png
[7a6745e50eff06251b00479051241836.gif]: https://img-blog.csdnimg.cn/img_convert/7a6745e50eff06251b00479051241836.gif
[b4d429290288678a1e1f1b1c540c0f43.png]: https://img-blog.csdnimg.cn/img_convert/b4d429290288678a1e1f1b1c540c0f43.png
[c04d43ac29d61d5dfe1a213267a29334.png]: https://img-blog.csdnimg.cn/img_convert/c04d43ac29d61d5dfe1a213267a29334.png
[7c1785f3d576f8a257f6b73d326ad070.png]: https://img-blog.csdnimg.cn/img_convert/7c1785f3d576f8a257f6b73d326ad070.png
[d30e1e973097b045be36fa8e67083ffc.gif]: https://img-blog.csdnimg.cn/img_convert/d30e1e973097b045be36fa8e67083ffc.gif
[a7ac4fdcb133f32a6d630bb10b384196.png]: https://img-blog.csdnimg.cn/img_convert/a7ac4fdcb133f32a6d630bb10b384196.png
[ffea5069ffcb139d9af89af8198b15c4.png]: https://img-blog.csdnimg.cn/img_convert/ffea5069ffcb139d9af89af8198b15c4.png
[a7bb6311263fc3cbfa1480b390e82a89.png]: https://img-blog.csdnimg.cn/img_convert/a7bb6311263fc3cbfa1480b390e82a89.png
[826fe208b934945ecacb2a02caccb0c7.png]: https://img-blog.csdnimg.cn/img_convert/826fe208b934945ecacb2a02caccb0c7.png
[7369f116feb39349c22ea70ba8f93b09.png]: https://img-blog.csdnimg.cn/img_convert/7369f116feb39349c22ea70ba8f93b09.png
[8805e7db8dfb4631a59ad07e8b1c57b3.jpeg]: https://img-blog.csdnimg.cn/8805e7db8dfb4631a59ad07e8b1c57b3.jpeg