几种常见的排序算法

逃离我推掉我的手 2022-11-21 14:59 192阅读 0赞

# 排序的基本知识点 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70_pic_center]

## 术语说明 ##

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；  
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序：所有排序操作都在内存中完成；  
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度： 一个算法执行所耗费的时间。  
空间复杂度：运行完一个程序所需内存的大小

## 算法总结 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70]  
[图片来源][Link 1]

**快速记忆**  
不稳定：选择、堆、希尔、快排（记：选择一堆希尔快跑~~~23333）  
时间复杂度相同：堆、归并 都是O(nlogn) 。  
需要额外空间的：快排、归并

### 使用场景 ###

1.  若序列的初始状态基本有序(**正序**)，则**插入、冒泡、快排**
2.  若**n较小**(如n≤50)，则**插入、选择**  
    　插入排序是稳定的——可以明显减少交换次数和数据移动次数  
    　选择排序是不稳定的——若选择排序的移动次数<插入排序，则选择排序较好
3.  若**n较大**，则应采用时间复杂度为\*\*O(nlgn)\*\*的排序方法：**快排、堆、归并**
    
    **堆排序**所需的辅助空间<快排，并且不会出现快排可能出现的最坏情况。但是堆和快排不稳定  
    　**快速排序**是目前基于比较的内部排序中被认为是最好的方法，当待排序的元素是`随机分布`时，快速排序的平均时间最短；  
    　**归并**：若要求排序稳定，则可选用归并排序
4.  要求数据分布均匀，数据偏差不会太大时采用非比较排序算法分别为：**基数排序，桶排序和计数排序**。这些算法均是针对特殊数据的，如要求数据分布均匀，数据偏差不会太大。采用的思想均是内存换时间，因而全是非原地排序。

## 一、冒泡排序 ##

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。

### 原理 ###

> 1.  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
> 2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
> 3.  针对所有的元素重复以上的步骤，除了最后一个；
> 4.  重复步骤1~3，直到排序完成。

### 时间复杂度 ###

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

### 优缺点 ###

优点：稳定

缺点：慢，每次只能移动两个相邻的数据；

### bubbleSort\_demo ###

@Test
        public void bubbleSort() {
            int[] arr = {8, 3, 2, 6, 7, 1, 5, 4};
            if (arr.length == 0) {
                return;
            }
            for (int i = 0; i < arr.length-1; i++) {//外层循环，控制趟数
                for (int j = 0; j < arr.length - 1 - i; j++) { //内层循环，控制每一趟的比较次数
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }

## 二、选择排序 ##

### 原理 ###

> 1.  在未排序序列中找到最小元素，存放到排序序列的起始位置
> 2.  再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
> 3.  以此类推，直到所有元素均排序完毕

### 时间复杂度 ###

T(n) = O(n2)

### selectSort\_demo ###

@Test
        public void selectSort() {
            int[] arr = {8, 3, 2, 6, 7, 1, 5, 4};
            if (arr.length == 0) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                //设当前的数为最小值
                int minVal = arr[i];
                int minPosition = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] < minVal) {
                        minVal = arr[j];
                        minPosition = j;
                    }
                }
                arr[minPosition] = arr[i];
                arr[i] = minVal;
            }
            System.out.println(Arrays.toString(arr));
        }

## 三、插入排序 ##

### 原理 ###

通过构建有序序列，对于未排序的序列，在已排序的序列中刚从后向前进行扫描，找到相应的位置插入。

### 时间复杂度 ###

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

### insertSort\_demo ###

@Test
        public void insertSort() {
            int[] arr = {8, 3, 2, 6, 7, 1, 5, 4};
            if (arr.length == 0) {
                return;
            }
            //假定第一个元素被放到了正确的位置上
            //这样，仅需遍历1 ~ length-1
            for (int i = 1; i < arr.length; i++) {
                int currentVal = arr[i];
                int j = i;
                while (j - 1 >= 0 && currentVal < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = currentVal;
            }
            System.out.println(Arrays.toString(arr));
        }

## 四、希尔排序 ##

### 原理 ###

shell排序是插入排序的升级版

> 1.  先确定步长进行分段，然后运用了插入排序法。当增量减至1时，整个文件恰被分成一组，算法便终止。
> 2.  其中步长 gap=length/2，缩小步长继续以gap = gap/2的方式

### 时间复杂度 ###

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n^2) 平均情况：T(n) = O(n^1.5)

### shellSort\_demo ###

@Test
        public void shellSort() {
            int[] arr = {8, 3, 2, 6, 7, 1, 5, 4};
            if (arr.length == 0) {
                return;
            }
            // gap为步长，每次减为原来的一半。
            for (int gap = arr.length / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < arr.length; i++) {
                    // 遍历各组中的所有元素（共gap组每组2个元素）步长gap
                    int j = i;
                    int currentVal = arr[i];
                    while (j - gap >= 0 && currentVal < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = currentVal;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

## 五、归并排序 ##

### 原理 ###

**要点**：采用分治法的策略，将已有的有序子序列合并为完全有序的序列，首先要让子序列有序，然后再使子序列间有序，最后等到完全有序的序列。

**思想**：将待排序序列R\[0,…n-1\]分为n个长度为1的子序列，讲相邻的子序列进行归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

首先要做两步：

1.分解 　——将序列每次折半划分。

2.合并　——将划分后的序列段两两合并后排序。

> 1.  把长度为n的输入序列分割成两个长度为n/2的子序列
> 2.  对这两个子序列分别采用归并排序； -------递进
> 3.  将两个排序好的子序列合并成一个最终的排序序列。 -------回归

### 时间复杂度 ###

T(n) = O(nlogn)

### mergeSort\_demo ###

@Test
        public void main() {
            int[] arr = {8, 3, 2, 6, 7, 1, 5, 4};
            if (arr.length == 0) {
                return;
            }
            mergeSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    
        private void mergeSort(int[] arr, int low, int high) {
            //递归过程是：在递进的过程中拆分数组，在回归的过程合并数组
            if (low < high) {
                int mid = (low + high) / 2;
                System.out.println("递进左边:" + "low = " + arr[low] + "," + "mid =" + arr[mid]);
                //左边归并排序，使得左子序列有序
                mergeSort(arr, low, mid);
                //右边归并排序，使得右子序列有序
                System.out.println("递进右边:" + "mid+1 = " + arr[(mid + 1)] + "," + "high =" + arr[high]);
                mergeSort(arr, mid + 1, high);
                //将两个有序子数组合并操作
                merge(arr, low, mid, high);
                System.out.println("回归:" + "low = " + arr[low] + "," + "mid =" + arr[(mid)] + "," + "high =" + arr[high]);
            }
        }
    
        /**
         * 1.开辟一块空间，用于存放合并后的序列
         * 2.设定两个指针，起始位置分别位于两个已排序序列的起始位置
         * 3.比较两个指针所代表的元素，将更小的元素放入合并空间，并将指针后移
         * 4.重复步骤3，直至有一个指针到达尾部
         * 5.将另一个序列的剩余元素复制到合并序列尾部
         */
        private void merge(int[] arr, int low, int mid, int high) {
            int i = low;//左序列指针
            int j = mid + 1;//右序列指针
            int k = 0;//临时数组指针
            int[] temp = new int[high - low + 1];
            while (i <= mid && j <= high) {
                if (arr[i] < arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            //将左边剩余元素填充进temp中
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            //将右序列剩余元素填充进temp中
            while (j <= high) {
                temp[k++] = arr[j++];
            }
            //将temp中的元素全部拷贝到原数组中
            k = 0;
            while (low <= high) {
                arr[low++] = temp[k++];
            }
        }

## 六、快排 ##

从数组中选取一个元素作为基准P（通常是第一个元素），从后往前吧所有<P的元素放到他之前，>P的放置后，然后递归将P左边和右边的数按照第一步操作，直至不能递归

### 原理 ###

> 1.  在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准，称为基准记录；
> 2.  定义两个索引 i 和 j 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
> 3.  首先，尾索引向前扫描，直到找到比基准值小的记录(i != j)，并替换首索引对应的值；
> 4.  然后，首索引向后扫描，直到找到比基准值大于的记录(i != j)，并替换尾索引对应的值；
> 5.  若在扫描过程中首索引等于尾索引(i = j),则一趟排序结束；将基准值(key)替换首索引所对应的值；
> 6.  再进行下一趟排序时，待排序列被分成两个区:\[low,j-1\],\[j+1,high\]
> 7.  对每一个分区重复步骤2~6，直到所有分区中的记录都有序，排序成功

### 时间复杂度 ###

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

### quickSort\_demo ###

@Test
        public void QuickSortMain() {
            int[] arr = {5, 3, 2, 6, 7, 1, 8, 4};
            if (arr.length == 0) {
                return;
            }
            QuickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    
        private void QuickSort(int[] arr, int low, int high) {
            if (low > high) {
                return;
            }
            int i = low;
            int j = high;
            int key = arr[low];
            while (i < j) {
                while (i < j && arr[j] >= key) {
                    j--;
                }
                while (i < j && arr[i] <= key) {
                    i++;
                }
                if (i < j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
    
            }
            arr[low] = arr[i];
            arr[i] = key;
            QuickSort(arr, low, j - 1);
            QuickSort(arr, j + 1, high);
        }

## 七、堆排序 ##

特点：  
1、堆排序是一种树形选择排序方法，在排序过程中将数组看成一棵完全二叉树  
2、对于数组中索引位置为 i 的元素，`左儿子 = 2*i+1，右儿子 = 2*i+2，父节点 i == 0? null : (i-1)/2`  
3、完全二叉树的`第一个非叶子节点索引位置 = （length - 1-1）/2`。其中length-1是最后一个元素的索引位置

### 原理 ###

> 1.  构建初始堆，将待排序列构成一个大顶堆(或者小顶堆)，升序大顶堆，降序小顶堆；
> 2.  将根节点元素与最后一个元素交换，并断开最后一个元素。
> 3.  重新构建堆。
> 4.  重复2~3，直到所有节点断开。

### 时间复杂度 ###

T(n) = O(nlogn)

### heapSort\_demo ###

@Test
        public void HeapSort() {
            int[] arr = {5, 3, 2, 6, 7, 1, 8, 4};
            if (arr.length == 0) {
                return;
            }
            //对整个数组建立大根堆————从最后一个非叶子节点开始遍历至根节点！
            for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
                adjustDownToUp(arr, i, arr.length);
            }
    
            for (int j = arr.length - 1; j > 0; j--) {
                //将堆顶元素与末尾元素进行交换
                int maxVal = arr[0];
                arr[0] = arr[j];
                arr[j] = maxVal;
                //除了根节点外，其余都是大根堆，因此在此仅针对根节点进行堆调整
                adjustDownToUp(arr, 0, j);
            }
            System.out.println(Arrays.toString(arr));
        }
    
    
    
        //调整堆结构
        private void adjustDownToUp(int[] arr, int parent, int length) {
            int temp = arr[parent];
            for (int i = 2 * parent + 1; i < length; i = 2 * i + 1) {
                // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
                if (i + 1 < length && arr[i] < arr[i + 1]) {
                    i++;
                }
                // 如果父结点的值已经大于孩子结点的值，则直接结束
                if (temp > arr[i]) {
                    break;
                } else {
                    arr[parent] = arr[i];
                    arr[i] = temp;
                    //将已交换的子节点的值作为根节点继续
                    parent = i;
                }
    
            }
        }

## 八、基数排序 ##

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。

算法思想：基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

### 原理 ###

1.  取得数组中最大数值及其位数，将所有待比较数值统一为同样的数位长度，数位较短的数前面补零
2.  将最低位的值放到相应的编号为0~9的桶中。等到**最低位**排完得到一个**子序列**，再将这个序列按照**次低位**的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 时间复杂度 ###

T(n) = O(n \* k) ， k为数组中的数的最大的位数

## 九、计数排序 ##

### 原理 ###

1.  找出待排序的数组中最大和最小的元素；
2.  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3.  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4.  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

### 时间复杂度 ###

T(n) = O(n + k) ， k为数组中的数的最大的位数

[参考链接][Link 2]

### 两大局限性 ###

1.**当数列最大最小值差距过大时，并不适用于计数排序**

比如给定20个随机整数，范围在0到1亿之间，此时如果使用计数排序的话，就需要创建长度为1亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2.**当数列元素不是整数时，并不适用于计数排序**

如果数列中的元素都是小数，比如3.1415，或是0.00000001这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。

## 十、桶排序 ##

计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。

### 桶排序过程中存在两个关键环节： ###

元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。  
排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。

### 原理 ###

> 1.  根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数
> 2.  遍历待排序集合，将每一个元素移动到对应的桶中
> 3.  对每一个桶中元素进行排序，并移动到已排序集合中

算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知，当待排序集合中存在元素值相差较大时，对映射规则的选择是一个挑战，可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象，对算法的时间复杂度或空间复杂度有较大影响，所以同计数排序一样，桶排序适用于元素值分布较为集中的序列。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/cb9532fcf18c4c7fa1402acedaa6aa1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/b2e9d8dbc67c46c48d82bb82cd418234.png
[Link 1]: https://www.cnblogs.com/onepixel/articles/7674659.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODQ0Njg5MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/061fcfde13b1476792dcbe730b9085b5.png
[Link 2]: https://www.cnblogs.com/kyoner/p/10604781.html