常用排序算法

阅读数: 次 2021-03-21

1 排序算法的介绍

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。

2 排序的分类：

1) 内部排序:

指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。

2) 外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。

3) 常见的排序算法分类

3 算法的时间复杂度

3.1度量一个程序(算法)执行时间的两种方法

1) 事后统计的方法

这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

2) 事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优.

3.2时间频度

基本介绍

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。 一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。
举例说明 -基本案例

比如计算 1-100 所有数字之和, 我们设计两种算法：
举例说明-忽略常数项

结论:

1) 2n+20 和 2n 随着 n 变大，执行曲线无限接近, 20 可以忽略
2) 3n+10 和 3n 随着 n 变大，执行曲线无限接近, 10 可以忽略
举例说明-忽略低次项

结论:

1) 2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10
2) n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+20
举例说明-忽略系数

结论:

1) 随着 n 值变大， 5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明这种情况下, 5 和 3 可以忽略。
2) 而 n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键

3.3时间复杂度

1) 一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时， T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=Ｏ ( f(n) )，称Ｏ ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

2) T(n) 不同，但时间复杂度可能相同。如： T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同，但时间复杂度相同，都为 O(n²)。

3) 计算时间复杂度的方法：

用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

3.4常见的时间复杂度

常数阶 O(1)
对数阶 O(log2n)
线性阶 O(n)
线性对数阶 O(nlog2n)
平方阶 O(n^2)
立方阶 O(n^3)
k 次方阶 O(n^k)
指数阶 O(2^n)

常见的时间复杂度对应的图:

说明：

1) 常见的算法时间复杂度由小到大依次为： Ο (1)＜Ο (log2n)＜Ο (n)＜Ο (nlog2n)＜Ο (n2)＜Ο (n3)＜ Ο (nk) ＜Ο (2n) ，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

2) 从图中可见，我们应该尽可能避免使用指数阶的算法

1) 常数阶 O(1)

2) 对数阶 O(log2n)

3) 线性阶 O(n)

4) 线性对数阶 O(nlogN)

5) 平方阶 O(n²)

6) 立方阶 O(n³)、 K 次方阶 O(n^k)

说明：参考上面的 O(n²) 去理解就好了， O(n³)相当于三层 n 循环，其它的类似

3.5平均时间复杂度和最坏时间复杂度

1) 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

2) 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

3) 平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:)。

4 算法的空间复杂度简介

4.1基本介绍

1) 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。

2) 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例如快速排序和归并排序算法, 基数排序就属于这种情况

3) 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

5 冒泡排序

5.1基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始） ,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

优化：

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。 (这里说的优化，可以在冒泡排序写好后，再进行)

5.2演示冒泡过程的例子(图解)

小结上面的图解过程:

(1) 一共进行数组的大小-1 次大的循环
(2)每一趟排序的次数在逐渐的减少
(3) 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化

5.3冒泡排序应用实例

我们举一个具体的案例来说明冒泡法。我们将五个无序的数： 3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                arr[j] ^= arr[j + 1];
                arr[j + 1] ^= arr[j];
                arr[j] ^= arr[j + 1];
            }
        }
        System.out.println("第" + (i + 1) + "趟排序后的数组");
        System.out.println(Arrays.toString(arr));
        if (!flag) break;
    }
}

6 选择排序

6.1基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

6.2选择排序思想:

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~~arr[n-1]中选取最小值，与 arr[0]交换，第二次从 arr[1]~~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~~arr[n-1]中选取最小值，与 arr[2]交换， …，第 i 次从 arr[i-1]~~arr[n-1]中选取最小值，与 arr[i-1]交换， …, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

6.3选择排序思路分析图:

对一个数组的选择排序再进行讲解

6.4选择排序应用实例:

有一群牛 , 颜值分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序 [101, 34, 119, 1]

代码实现

private static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i; j < arr.length - 1; j++) {
            if (arr[minIndex] > arr[j + 1]) {
                minIndex = j+1;
            }
        }
        if (minIndex != i) {
            arr[i] ^= arr[minIndex];
            arr[minIndex] ^= arr[i];
            arr[i] ^= arr[minIndex];
        }
    }
}

7 插入排序

7.1插入排序法介绍:

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

7.2插入排序法思想:

插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

7.3插入排序思路图:

7.4插入排序法应用实例:

private static void insertSort(int[] arr) {//668
    for (int i = 1; i < arr.length; i++) {
        int index = i;
        int num=arr[index];
        while (index >= 1 && num < arr[index - 1]) {
            arr[index]=arr[index-1];
            index--;
        }
//          if (index!=i) //可加可不加，没有大影响
        arr[index]=num;
    }
}

8 希尔排序

8.1简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：

{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响

8.2希尔排序法介绍

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

8.3希尔排序法基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含
的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

8.5希尔排序法应用实例

有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用

1) 希尔排序时，对有序序列在插入时采用交换法, 并测试排序速度.
2) 希尔排序时，对有序序列在插入时采用移动法, 并测试排序速度
3) 代码实现

public static void shellSort(int[] arr) { //17
    // 增量 gap, 并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第 gap 个元素， 逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    //移动
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                //当退出 while 后， 就给 temp 找到插入的位置
                arr[j] = temp;
            }
        }
    }
}

9 快速排序

9.1快速排序法介绍:

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

9.2快速排序法示意图:

9.3快速排序法应用实例:

private static void quickSort(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                if (i!=j){
                    arr[i] ^= arr[j];
                    arr[j] ^= arr[i];
                    arr[i] ^= arr[j];
                }
//                int temp = arr[i];
//                arr[i] = arr[j];
//                arr[j] = temp;
            }
        }
        if (i - 1 > start) quickSort(arr, start, i - 1);
        if (j + 1 < end) quickSort(arr, j + 1, end);
    }

这里发现一个用异或交换值的小坑当交换的两个值是同一个内存中的对象异或交换就会失效

原理：第一次异或两个值同时为0

10 归并排序

10.1 归并排序介绍:

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

10.2 归并排序思想示意图 1-基本思想:

10.3 归并排序思想示意图 2-合并相邻有序子序列:

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

10.4 归并排序的应用实例

package com.ming.sorting.algorithm;

import java.util.Arrays;

/*
归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
//        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        long l = System.currentTimeMillis();
        mergeSort(arr, 0, arr.length - 1, temp);
        long l1 = System.currentTimeMillis();
        System.out.println(l1-l);
        System.out.println(Arrays.toString(arr));
    }

    //分+合方法
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2; //中间索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 初始化 i, 左边有序序列的初始索引
        int j = mid + 1; //初始化 j, 右边有序序列的初始索引
        int t = 0; // 指向 temp 数组的当前索引

        //(一)
        //先把左右两边(有序)的数据按照规则填充到 temp 数组
        //直到左右两边的有序序列， 有一边处理完毕为止
        while (i <= mid && j <= right) {
            //如果左边的有序序列的当前元素， 小于等于右边有序序列的当前元素
            //即将左边的当前元素， 填充到 temp 数组
            //然后 t++, i++
            if (arr[i] < arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到 temp
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }

        //(三)
        //将 temp 数组的元素拷贝到 arr
        //注意， 并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }
}

11 基数排序

11.1 基数排序(桶排序)介绍:

1) 基数排序（radix sort）属于“分配式排序” （distribution sort），又称“桶子法” （bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶” 中，达到排序的作用

2) 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

3) 基数排序(Radix Sort)是桶排序的扩展

4) 基数排序是 1887 年赫尔曼· 何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

11.2 基数排序基本思想

1) 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

2) 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

11.3 基数排序图文说明

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

11.4 基数排序代码实现

package com.ming.sorting.algorithm;

import java.util.Arrays;

/*
基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
//                int[] arr = {9, 78, 0, 23, 567, 70};
        int[] arr = new int[8000000];

        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        long l = System.currentTimeMillis();
        radixSort(arr);
        long l1 = System.currentTimeMillis();
        System.out.println(l1 - l);

//        System.out.println(Arrays.toString(arr));
    }

    //基数排序方法
    public static void radixSort(int[] arr) {
        int max = arr[0]; //假设第一数就是最大数
        for(int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //定义一个二维数组， 表示 10 个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含 10 个一维数组
        //2. 为了防止在放入数的时候， 数据溢出， 则每个一维数组(桶)， 大小定为 arr.length
        //3. 名明确， 基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中， 实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如： bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]++]=arr[j];
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据， 放入原来数组)
            int index = 0;
            //遍历每一桶， 并将桶中是数据， 放入到原数组
            for(int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中， 有数据， 我们才放入到原数组
                if(bucketElementCounts[k] != 0) {
                    //循环该桶即第 k 个桶(即第 k 个一维数组), 放入
                    for(int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到 arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第 i+1 轮处理后， 需要将每个 bucketElementCounts[k] = 0 ！ ！ ！ ！
                bucketElementCounts[k] = 0;
            }
        }
    }
}

11.5 基数排序的说明:

1) 基数排序是对传统桶排序的扩展，速度很快.

2) 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。

3) 基数排序时稳定的。 [注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中， r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]

4) 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

12 常用排序算法总结和对比

12.1 一张排序算法的比较图

12.2 相关术语解释：

1) 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面；

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

3) 内排序：所有排序操作都在内存中完成；

4) 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

5) 时间复杂度：一个算法执行所耗费的时间。

6) 空间复杂度：运行完一个程序所需内存的大小。

7) n: 数据规模

8) k: “桶” 的个数

9) In-place: 不占用额外内存

10) Out-place: 占用额外内存