更多详情内容请访问:数据结构与算法系列文章导读

1、概述

1.1 相关术语

  • 稳定排序:如果 a 原本在 b 前面,而 a = b,排序之后 a 仍然在 b 的前面;

    非稳定排序:如果 a 原本在 b 的前面,而 a = b,排序之后 a 可能会出现在 b 的后面;

  • 内排序:所有排序操作都在内存中完成;

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

  • 时间复杂度:排序所耗费的时间;

    空间复杂度:排序所耗费的内存;

  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破 O(nlogn),因此也称为非线性时间比较类排序。

    非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

1.2 排序算法分类

1653571444226

1.3 不同算法的复杂度及稳定性

  • in-place:占用常数内存

    举例:在冒泡排序中,为了将 arr 排序,借用了一个 temp 的临时变量,开辟了一个临时空间,这个空间是常数量,这就是in-place

  • out-place:占用额外内存

    举例:拿上面的例子来说,假设你把排序时把数组中的数按顺序放入了一个新的数组,我就开了一个 n 规模大小的数组,这个就与数据规模有关

  • n:数据规模

  • k:“桶”的个数

1653572516933

1.4 如何计算时间复杂度

  1. 常数阶 O(1)

    表示该算法的执行时间(或执行时占用空间)总是为一个常量,不论输入的数据集是大是小,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)

    int i = 1;
    int j = 2;
    int k = i + j;

    上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用$O(1)$来表示它的时间复杂度

  2. 线性阶 O(n)

    表示一个算法的性能会随着输入数据的大小变化而线性变化

    for (int i = 0; i < n; i++) {
        sum += i;
    }

    这段代码,for 循环里面的代码会执行 n 遍,因此它消耗的时间是随着 n 的变化而变化的,因此这类代码都可以用 O(n)​ 来表示它的时间复杂度

  3. 平方阶 O(n²)

    表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话,算法的性能将会变为立方阶 O(n3),​O(n4),O(n^k)以此类推

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum += i+j;
        }
    }
  4. 指数阶 O(2^n)

    表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是裴波那契数列的递归计算实现

    int Fibonacci(int number) {
        if (number <= 1) {
            return number;
        }
        return Fibonacci(number - 2) + Fibonacci(number - 1);
    }
  5. 对数阶 O(logn)

    int i = 1;
    while (i < n) {
        i *= 2;
    }

    在 while 循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了,直到 i 不小于 n 退出。

    试着求解一下,假设循环次数为 x,也就是说 2 的 x 次方等于 n,则由 2^x=n 得出 x=logn。因此这个代码的时间复杂度为 O(logn)

  6. 线性对数阶 0(nlogn)

    将时间复杂度为对数阶 O(logn) 的代码循环 n 遍的话,那么它的时间复杂度就是 n * O(logN),也就是了 O(nlogn)

    for (int i = 1; i < n; i++) {
        j = 1;
        while (j < n) {
            j *= 2;
        }
    }

2、冒泡排序(Bubble Sort)

冒泡排序基本思想

通过对排序序列从前想后(从下标较小的元素),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部

冒泡排序的动图演示:

小结上面的图解过程:

  1. 一共进行 数组.length - 1 次循环
  2. 每一趟排序的次数在逐渐减少
  3. 如果在某躺排序中发现没有发生过一次交换,就可以提前结束冒泡排序

public class Analysis {

    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};

        // 第一趟排序,就是将最大的数排在最后
        int temp  = 0;
        for (int i = 0; i < arr.length-1; i++) {
            // 如果前面的数大,则交换位置
            if (arr[i] > arr[i+1]) {
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        System.out.println("第一趟排序后的数组:" + Arrays.toString(arr));

        // 第二趟排序,就是将第二大的数组排在倒数第二位
        for(int j = 0; j < arr.length - 1 - 1; j++) {
            // 如果前面的数比后面的数大,则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第二趟排序后的数组:" + Arrays.toString(arr));

        // 第三趟排序,就是将第三大的数组排在倒数第三位
        for(int j = 0; j < arr.length - 1 - 2; j++) {
            // 如果前面的数比后面的数大,则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第三趟排序后的数组:" + Arrays.toString(arr));

        // 第四趟排序,就是将第四大的数组排在倒数第四位
        for(int j = 0; j < arr.length - 1 - 3; j++) {
            // 如果前面的数比后面的数大,则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第四趟排序后的数组:" + Arrays.toString(arr));
    }
}

public static int[] bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return arr;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSorted  = true;//有序标记,每一轮的初始是true
        for (int j = 0; j < arr.length -1 - i; j++) {
            if (arr[j + 1] < arr[j]) {
                isSorted  = false;//有元素交换,所以不是有序,标记变为false
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        //一趟下来是否发生位置交换,如果没有交换直接跳出大循环
        if(isSorted ) {
            break;
        }
    }
    return arr;
}

public static int[] bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return arr;
    }
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序数列的边界,每次比较只需要比到这里为止
    int sortBorder = arr.length - 1;

    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSorted  = true;//有序标记,每一轮的初始是true
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j + 1] < arr[j]) {
                isSorted  = false;//有元素交换,所以不是有序,标记变为false
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        //一趟下来是否发生位置交换,如果没有交换直接跳出大循环
        if(isSorted ) {
            break;
        }
    }
    return arr;
}

  1. 平均时间复杂度:O(n²),内外两重循环都与数据规模 n 相关
  2. 最好时间复杂度:O(n),当原本就有序,且在第一趟外循环结束时就判断出序列有序直接退出排序
  3. 最坏时间复杂度:O(n²),当原本逆序时
  4. 空间复杂度:O(1),代码执行所需空间与数据规模 n 无关
  5. 稳定性:稳定,因为 if(arr[j]>arr[j+1]){} ,相等元素其相对位置不会改变

3、快速排序(Quick Sort)

快速排序基本思想

是对冒泡排序的一种改进

  1. 首先设置一个分界值也就是基准值,通过该分界值将数据分割成两部分
  2. 大于或等于分界值的数据集中到右边小于分界值的数据集中到左边
  3. 然后,左边和右边的数据可以看成两组不同的部分,重复上述1和2步骤。当左右两部分都有序时,整个数据就完成了排序

大致步骤如下:

  1. 首先设置三个参数,begin 指向区间左端end 指向区间右端pivot 为当前的分解值
  2. 从待排序的数据元素中选取一个通常为第一个作为基准值 pivot = num[0],设置双指针 begin 指向区间左端,end 指向区间右端
  3. pivot 首先与 num[end] 进行比较,如果 num[end] < pivot,则 num[begin] = num[end] 将这个比 pivot 小的数放到左边去,如果 num[end] >= pivotend--,再拿 num[end]pivot 比较,直到 num[end]<pivot 交换了元素为止
  4. num[end]<pivot 交换元素后,转向左边部分,同时 begin++,再去用 num[begin]pivot 进行比较,如果 num[begin]<pivot,则再 begin++,然后继续进行比较,直至 num[begin]>=pivot,则将 num[end]=num[begin]
  5. 重复上述步骤……

下面给出一个具体的例子(第一轮):

/**
 * 快速排序算法
 * @param arr 要排序的数组
 * @param begin 要排序数组的第一个元素下标
 * @param end 要排序数组的长度
 */
public static int[] quickSort(int[] arr, int begin, int end){
    int first = begin;
    int last = end - 1;
    int pivot = arr[first];

    // 跳出循环的条件:first 和 last 指针位置重合,该位置应该赋值为 pivot
    while (first < last) {
        // 只要右边的值≥中轴值,右侧指针左移一位
        while (first < last && arr[last] >= pivot) {
            last--;
        }
        // 执行到此处说明右侧值小于分界值,交换
        arr[first] = arr[last];
        // 右侧移动完了,该左侧开始比较,只要左侧的值<中轴值,左指针就右移一位
        while (first < last && arr[first] < pivot) {
            first++;
        }
        // 执行到此处说明左侧值大于分界值,交换
        arr[last] = arr[first];
    }
    // 执行到此处 first 就是中轴线位置的下标了,给分界点赋值
    arr[first] = pivot;

    // 中轴线左侧继续递归
    if (first > begin) {
        arr = quickSort(arr, begin, first);
    }
    // 中轴线右侧继续递归
    if (first + 1 < end) {
        arr = quickSort(arr, first + 1, end);
    }
    return arr;
}

  1. 平均时间复杂度:O(nlogn),划分和递归的快排
  2. 最好时间复杂度:O(nlogn)
  3. 最坏时间复杂度:O(n²),当原本逆序时,退化成冒泡排序
  4. 空间复杂度:O(logn),就地排序,但每次递归要保持数据,故O(logn)
  5. 稳定性:不稳定,当序列中有等于选出的基准的元素时,划分时相对位置可能改变
  6. 注意:基准的选择决定着快排的效率,一般可随机选一个基准,推荐第一个数组元素为基准值

4、插入排序(Insertion Sort)

插入排序基本思想

也称“直接插入排序

  1. 初始时:有序区 arr[0],无序区 arr[1…len-1]。
  2. 取无序区的第一个元素,在有序区中从后往前的扫描。
  3. 若取出元素小于当前元素,则当前元素后移,一直往前扫描,直到不小于当前元素时,记录此下标。
  4. 将取出的元素插入到此下标指向的位置,一次插入结束。无序区减1。
  5. 重复上述步骤,直到无序区为空。

1653449832754

插入排序的动图演示:

public class Analysis {

    public static void main(String[] args) {
        int[] arr = {34, 11, 119, 16};

        // 第1轮:开始时有序表中只包含一个元素,无序表中包含 n-1 个元素
        int insertVal = arr[1]; // 取无序列表的第一个元素,也就是将要排序的元素
        int index = 0; // 此时有序列表中最大的元素下标就是原数组第一个元素的下标
        // 将将要排序的值去左侧有序列表中从右向左开始遍历比较
        while(index >= 0 && insertVal < arr[index] ) { // 如果将排序的值小于左侧列表的右侧值
            arr[index + 1] = arr[index]; // 那么原本左侧该值的位置右移一位
            index--; // 再去跟前面的比较
        }
        arr[index + 1] = insertVal;
        System.out.println("第1轮插入" + Arrays.toString(arr)); //[11, 34, 119, 16]

        //第2轮
        insertVal = arr[2];
        index = 2 - 1;

        while(index >= 0 && insertVal < arr[index] ) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = insertVal;
        System.out.println("第1轮插入" + Arrays.toString(arr)); //[11, 34, 119, 16]

        //第3轮
        insertVal = arr[3];
        index = 3 - 1;
        while (index >= 0 && insertVal < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = insertVal;
        System.out.println("第1轮插入" + Arrays.toString(arr)); //[11, 16, 34, 119]
    }
}

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insertVal = arr[i];
        int compareIndex = i - 1;
        while (compareIndex >= 0 && insertVal < arr[compareIndex]) {
            arr[compareIndex + 1] = arr[compareIndex];
            compareIndex--;
        }
        arr[compareIndex + 1] = insertVal;
    }
}

  1. 平均时间复杂度:O(n²),两层循环
  2. 最好时间复杂度:O(n)。当原本有序,则内循环不执行
  3. 最坏时间复杂度:O(n²),当原本逆序时
  4. 空间复杂度:O(1),就地排序
  5. 稳定性:稳定

5、希尔排序(Shell Sort)

希尔排序基本思想

也称“缩小增量排序”。插入排序的改进版。

它把序列按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的元素越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

在此选择增量 gap=length/2,缩小增量以 gap = gap/2 的方式,用序列 {n/2, (n/2)/2 ... 1} 来表示。

大致步骤如下:

  1. 初始化增量第一趟 gap = length / 2 = 4

    1653464760250

  2. 第二趟,增量缩小为 gap = (length / 2) / 2 = 2

    1653464830108

  3. 第三趟,增量缩小为1,并得到最终排序结果:

    1653464840435

public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        System.out.println("希尔排序0轮时=" + Arrays.toString(arr));
        int temp = 0;

        // 希尔排序的第1轮排序
        // 因为第1轮排序,是将10个数据分成了5组
        for (int i = 5; i < arr.length; i++) {
            // 遍历各组中所有的元素(共5组,每组有2个元素), 步长5
            for (int j = i - 5; j >= 0; j -= 5) {
                // 如果当前元素大于加上步长后的那个元素,则交换
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println("希尔排序1轮后=" + Arrays.toString(arr)); // [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

        // 希尔排序的第2轮排序
        // 因为第2轮排序,是将10个数据分成了 5/2 = 2组
        for (int i = 2; i < arr.length; i++) {
            // 遍历各组中所有的元素(共2组,每组有5个元素), 步长2
            for (int j = i - 2; j >= 0; j -= 2) {
                // 如果当前元素大于加上步长后的那个元素,说明交换
                if (arr[j] > arr[j + 2]) {
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }
        System.out.println("希尔排序2轮后=" + Arrays.toString(arr)); // [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

        // 希尔排序的第3轮排序
        // 因为第3轮排序,是将10个数据分成了 2/2 = 1组
        for (int i = 1; i < arr.length; i++) {
            // 遍历各组中所有的元素(共5组,每组有2个元素), 步长5
            for (int j = i - 1; j >= 0; j -= 1) {
                // 如果当前元素大于加上步长后的那个元素,说明交换
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("希尔排序3轮后=" + Arrays.toString(arr)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i - gap; j >= 0; j -= gap) {
                if (arr[j] > arr[j + gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
}

public static void shellSort(int arr[]){
    //和交换法一样,都需要增量去分组
    for(int gap = arr.length / 2; gap > 0; gap /= 2){
        //同样我们得找到分组后面的数据
        for(int i = gap; i < arr.length; i++){
            //设置指针指向i去操作分组前的数据
            int j = i;
            //存储当前的数据,因为数据后面会发生变化
            int temp = arr[j];
            if(arr[j] < arr[j - gap]){
                //要清楚j存储的是分组后面的数据
                while(j - gap >= 0 && temp < arr[j - gap]){
                    //将前面的值移位到j上,此时j与j-step都为arr[j - gap]的值
                    arr[j] = arr[j - gap];
                    //将指针在组内往前移动,继续寻找
                    j -= gap;
                }
                //当循环结束的时候,就是找到了位置,那么需要将temp赋值给分组前面的值
                arr[j] = temp;
            }
        }
    }
}

  1. 平均时间复杂度:O(n^(1.3—2)),找度娘
  2. 最好时间复杂度:O(n)。当原本有序,则内循环不执行
  3. 最坏时间复杂度:O(n²),当原本逆序时
  4. 空间复杂度:O(1),就地排序
  5. 稳定性:不稳定,插入排序是稳定,但希尔排序是有间隔的分组插入排序
  6. 注意:增量的选择决定希尔排序的效率

6、选择排序(Select Sort)

选择排序基本思想

未排序序列中找到最小(最大)元素,并存放到已排序序列的末尾

总共通过 数组.length - 1 次得到一个按排序码从小到大排序的有序序列,如下图:

1653409215477

  • 第一次:从 arr[0]~arr[n-1] 中选取最小值与 arr[0] 交换
  • 第二次:从 arr[1]~arr[n-1] 中选取最小值与 arr[1] 交换
  • 第三次:从 arr[2]~arr[n-1] 中选取最小值与 arr[2] 交换
  • ...
  • 第 n-1 次:从 arr[n-2]~arr[n-1] 中选取最小值与 arr[n-2] 交换

选择排序的动图演示:

public class Analysis {

    public static void main(String[] args) {
        int arr[] = new int[]{101, 34, 119, 1};

        // 第1轮
        int minIndex = 0; // 假定最小值元素的下标
        int min = arr[0]; // 假定该数组中第一个元素是最小值
        for (int j = 0 + 1; j < arr.length; j++) {
            if (min > arr[j]) { // 说明假定的最小值,并不是最小
                min = arr[j];
                minIndex = j;
            }
        }
        // 将最小值,放在arr[0], 即交换
        if (minIndex != 0) {
            arr[minIndex] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一轮交换后:" + Arrays.toString(arr));

        // 第2轮
        minIndex = 1; // 假定最小值元素的下标
        min = arr[1]; // 假定该数组中第一个元素是最小值
        for (int j = 0 + 1 + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (minIndex != 1) {
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮交换后:" + Arrays.toString(arr));

        //第3轮
        minIndex = 2; // 假定最小值元素的下标
        min = arr[2]; // 假定该数组中第一个元素是最小值
        for (int j = 2 + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (minIndex != 2) {
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮交换后:" + Arrays.toString(arr));
    }
}

public static void simpleSelectionSort(int[] arr) {
    // 最外层的循环次数是比较的次数(数组长度-1)
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i; // 假定当前最小值的下标
        int minValue = arr[i]; // 假定当前最小值
        // 从假定最小值下标下一位开始
        for(int j = 1 + i; j < arr.length; j++) {
            if (arr[j] < minValue) { // 如果成立,说明假定最小值不是最小的,当前的值才是最小
                minIndex = j;
                minValue = arr[j];
            }
        }
        // 只要 != 说明,有别的最小值,因此需要更换元素位置
        if (minIndex != i) {
            arr[minIndex] = minValue;
            arr[i] = minValue;
        }
    }
}

  1. 平均时间复杂度:O(n²),两重循环
  2. 最好时间复杂度:O(n²)。当原本有序,依旧要进行内循环的遍历才能确定最小元素
  3. 最坏时间复杂度:O(n²),当原本逆序时
  4. 空间复杂度:O(1),就地排序
  5. 稳定性:不稳定,相同元素的相对位置可能会发生改变

7、堆排序(Heap Sort)

堆排序基本思想

  1. 将待排序序列构造成一个大顶堆
  2. 此时,整个序列的最大值就是堆顶的根节点
  3. 将其与末尾元素进行交换,此时末尾就是最大值
  4. 然后将剩余 n -1 个元素重新构造一个堆,这样会得到 n 个元素的次小值
  5. 重复上述步骤,得到一个有序序列

/**
 * 堆排序
 */
public static void heapSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int len = arr.length;
    // 第一步:构建大顶堆,这里其实就是把待排序序列,变成一个大顶堆结构的数组
    buildMaxHeap(arr, len);

    // 第二步:将顶堆元素与末尾元素互换,使末尾元素最大,然后将剩余 n -1 个元素重新构造一个堆
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0, len);
    }
}

/**
 * 构建大顶堆
 * @param arr 构建大顶堆参考的数组
 * @param len 数组的长度
 */
private static void buildMaxHeap(int[] arr, int len) {
    // 从最后一个非叶节点开始向前遍历,调整节点性质,使之成为大顶堆
    for (int i = (int) Math.floor(len / 2) - 1; i >= 0; i--) {
        // 从第一个非叶子结点从下至上,从右至左调整结构
        heapify(arr, i, len);
    }
}

/**
 * 调整大顶堆
 * @param arr 构建大顶堆参考的数组
 * @param i   非叶子节点下标
 * @param len 数组长度
 */
private static void heapify(int[] arr, int i, int len) {
    // 先根据堆性质,找出它左右节点的索引
    int leftIndex = 2 * i + 1;
    int rightIndex = 2 * i + 2;

    // 默认当前节点(父节点)是最大值。
    int largestIndex = i;
    if (leftIndex < len && arr[leftIndex] > arr[largestIndex]) {
        // 如果有左节点,并且左节点的值更大,更新最大值的索引
        largestIndex = leftIndex;
    }
    if (rightIndex < len && arr[rightIndex] > arr[largestIndex]) {
        // 如果有右节点,并且右节点的值更大,更新最大值的索引
        largestIndex = rightIndex;
    }

    if (largestIndex != i) {
        // 如果最大值不是当前非叶子节点的值,那么就把当前节点和最大值的子节点值互换
        swap(arr, i, largestIndex);
        // 因为互换之后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整。
        heapify(arr, largestIndex, len);
    }
}

/**
 * 数组中交换数值
 */
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为 O(n),在交换并重建堆的过程中,需交换 n-1 次,而重建堆的过程中,根据完全二叉树的性质,[log2(n-1),log2(n-2)...1] 逐步递减,近似为 nlogn。所以堆排序时间复杂度一般认为就是 O(nlogn) 级

  1. 平均时间复杂度:O(nlogn)。每轮选择一个最大数,且进行堆化调整。
  2. 最好时间复杂度:O(nlogn)。
  3. 最坏时间复杂度:O(nlogn)。
  4. 空间复杂度:O(1),就地排序。
  5. 稳定性:不稳定。同选择排序。

8、归并排序(Merge Sort)

归并排序基本思想

利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并

1653533566068

  1. 把数组从中间划分成两个子数组;
  2. 一直递归地把子数组划分成更小的子数组,直到子数组里面只有一个元素
  3. 依次按照递归的返回顺序,不断地合并排好序的子数组,直到最后把整个数组的顺序排好。

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

归并排序的动图演示:

public static int[] mergeSort(int arr[]) {
    if (arr == null || arr.length < 2) {
        return arr;
    }
    int mid = arr.length / 2; // 获取中间分界线的索引
    int[] left = Arrays.copyOfRange(arr, 0, mid); // 获取中界线左边的数组
    int[] right = Arrays.copyOfRange(arr, mid, arr.length); // 获取中界线右边的数组

    left = mergeSort(left);
    right = mergeSort(right);
    //对子序列使用归并排序
    return merge(left, right);
}

//将两个有序的序列合并成一个有序的序列
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length]; // 创建一个用来存放合并序列的数组
    int resultIndex = 0;
    int leftIndex = 0;
    int rightIndex = 0;

    // 跳出循环条件:临时数组已经全部填充完成
    while (resultIndex != result.length) {
        if (leftIndex >= left.length) {
            // 说明左数组已经全部遍历完了,直接把右数组的剩余元素挨个填充就行
            result[resultIndex++] = right[rightIndex++];
        } else if (rightIndex >= right.length) {
            // 说明右数组已经全部遍历完了,直接把左数组的剩余元素挨个填充就行
            result[resultIndex++] = left[leftIndex++];
        } else if (left[leftIndex] <= right[rightIndex]) {
            // 如果左数组的值 < 右数组的值,则临时数组中放入左数组的值
            result[resultIndex++] = left[leftIndex++];
        } else {
            // 如果左数组的值 > 右数组的值,则临时数组中放入右数组的值
            result[resultIndex++] = right[rightIndex++];
        }
    }

    return result;
}

  1. 平均时间复杂度:O(nlogn),总时间 = 分解时间 + 解决问题时间 + 合并时间 = O(1) + 2O(n/2) + O(n)
  2. 最好时间复杂度:O(nlogn)
  3. 最坏时间复杂度:O(nlogn)
  4. 空间复杂度:O(n),临时的数组和递归时压入栈的数据占用的空间:n + logn
  5. 稳定性:稳定

9、计数排序(Countint Sort)

计数排序基本思想

核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

  1. 根据待排序集合中最大元素和最小元素的差值范围,申请额外空间;
  2. 遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;
  3. 对额外空间内数据进行计算,得出每一个元素的正确位置;
  4. 将待排序集合每一个元素移动到计算得出的正确位置上。

先假设 20 个数列为:{9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9}

先遍历这个无序的随机数组,找出最大值为 10 和最小值为 0。这样对应的计数范围将是 0 ~ 10。然后每一个整数按照其值对号入座,对应数组下标的元素进行加 1 操作

1653636204344

数组中的每一个值,代表了数列中对应整数的出现次数。

有了这个统计结果,排序就很简单了,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次。比如统计结果中的 1 为 2,就是数列中有 2 个 1 的意思。这样就得到最终排序好的结果。

计数排序的动图演示:

public static int[] countingSort(int[] arr) {
    int min = arr[0];
    int max = arr[0];
    int len = arr.length;

    if (arr == null || len <= 2) {
        return null;
    }

    //确定极差,优化额外开辟的数组
    for (int temp : arr) {
        if (temp < min)
            min = temp;
        if (temp > max)
            max = temp;
    }

    //额外开辟的空间,存储原数组的计数信息
    int k = max - min + 1;
    int[] count = new int[k];

    //遍历原数组,填充用于计数的数组
    for (int i = 0; i < len; i++) {
        count[arr[i] - min]++;
    }

    //遍历计数的数组,填充排好序的数组
    int[] res = new int[len];
    int resIndex = 0;
    for (int i = 0; i < k; i++) {
        while (count[i] > 0) {
            res[resIndex] = i + min;
            resIndex++;
            count[i]--;
        }
    }

    return res;
}

  1. 平均时间复杂度:O(n+k)。数据规模 n,数据间极差 k
  2. 最好时间复杂度:O(n+k)
  3. 最坏时间复杂度:O(n+k)
  4. 空间复杂度:O(n+k),返回的结果数据组 n,用于计数的数组k
  5. 稳定性:稳定。反向填充结果数组保证其稳定性

10、桶排序(Bucket Sort)

桶排序基本思想

桶排序是计数排序的升级版,简单来说就是将待排序序列,按照序列值的大小划分成几个桶,分别对每组进行排序,排完序之后再按照一定的顺序合并所有的桶,即排序完成

  1. 首先,根据待排序序列的大小,设定一个桶值,即划分为多少个桶
  2. 遍历待排序序列,将每个元素,按照桶的范围,分别放入不同的桶中
  3. 在向桶中添加元素的时候,使用插入排序或者其他排序方法,对该桶中的元素进行排序
  4. 当所有元素都放入各自所属的桶中的之后,按照桶的顺序合并所有的桶,排序完成

另外需要注意:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要

1653637716429

public static void bucketSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int len = arr.length;
    // 根据原始序列的长度,设置桶的数量。这里假设每个桶放最多放4个元素
    int bucketCount = len / 4;
    // 遍历原始序列,找出最大值和最小值
    int min = 0, max = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        } else if (arr[i] < min) {
            min = arr[i];
        }
    }

    // 每个桶的数值范围
    int range = (max - min + 1) / bucketCount;
    int[][] buckets = new int[bucketCount][];
    // 遍历原始序列
    for (int i = 0; i < len; i++) {
        int val = arr[i];
        // 计算当前值属于哪个桶
        int bucketIndex = (int) Math.floor((val - min) / range);
        // 向桶中添加元素
        buckets[bucketIndex] = appendItem(buckets[bucketIndex], val);
    }

    // 最后合并所有的桶
    int k = 0;
    for (int[] b : buckets) {
        if (b != null) {
            for (int i = 0; i < b.length; i++) {
                arr[k++] = b[i];
            }
        }
    }
}

private static int[] appendItem(int[] bucketArr, int val) {
    if (bucketArr == null || bucketArr.length == 0) {
        return new int[]{val};
    }
    // 拷贝一下原来桶的序列,并增加一位
    int[] arr = Arrays.copyOf(bucketArr, bucketArr.length + 1);

    // 这里使用插入排序,将新的值val插入到序列中
    for (int i = bucketArr.length - 1; i >= 0; i--) {
        // 从新序列arr的倒数第二位开始向前遍历(倒数第一位是新增加的空位,还没有值)
        // 如果当前序列值大于val,那么向后移位
        if (arr[i] > val) {
            arr[i + 1] = arr[i];
        } else {
            arr[i + 1] = val;
            break;
        }
    }
    return arr;
}

  1. 平均时间复杂度:O(n+k)。数据规模 n,桶的数量 k
  2. 最好时间复杂度:O(n),每个桶只有一个数据
  3. 最坏时间复杂度:O(n^2^),数据都在一个桶
  4. 空间复杂度:O(n+k),返回的结果数据组 n,桶数组 k
  5. 稳定性:稳定。

11、基数排序(Radix Sort)

基数排序基本思想

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

基数排序的动图演示:

public class Analysis {

    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};

        // 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
        /*
        1.二维数组包含10个一维数组
        2.为了防止在放入数的时候,数据溢出,则每个一维数组(桶)的大小定为 arr.length
        3.基数排序是使用空间换时间的经典算法
         */
        int[][] bucket = new int[10][arr.length];

        // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        // bucketElementCounts[0] 记录的就是 bucket[0] 这个桶放入数据的个数
        int[] bucketElementCounts = new int[10];

        // 第1轮排序,针对每个元素的个位进行排序处理
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的个位数
            int digitOfElement = arr[j] % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        // 按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)
        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];
                }
            }
            // 第l轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!
            bucketElementCounts[k] = 0;
        }
        System.out.println("第1轮,对个位的排序处理:" + Arrays.toString(arr));

        // ----------第2轮
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的个数
            int digitOfElement = arr[j] / 10 % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        // 按照这个桶的顺序(一维数组的下标一次取出数据,放入原来数组)
        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];
                }
            }
            //第l轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!
            bucketElementCounts[k] = 0;
        }
        System.out.println("第2轮,对十位的排序处理:" + Arrays.toString(arr));

        // ----------第3轮
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的个数
            int digitOfElement = arr[j] / 100 % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        // 按照这个桶的顺序(一维数组的下标一次取出数据,放入原来数组)
        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];
                }
            }
            //第l轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!!
            bucketElementCounts[k] = 0;
        }
        System.out.println("第3轮,对百位的排序处理:" + Arrays.toString(arr));
    }
}

public static void radixSort(int[] arr) {
    // 定义一个二维数组,表示10个桶,每个桶就是一个一维数组
    /*
    1.二维数组包含10个一维数组
    2.为了防止在放入数的时候,数据溢出,则每个一维数组(桶)的大小定为 arr.length
     */
    int[][] bucket = new int[10][arr.length];

    // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
    // bucketElementCounts[0] 记录的就是 bucket[0] 这个桶放入数据的个数
    int[] bucketElementCounts = new int[10];

    // 得到数组中最大的数的位数
    int max = arr[0]; // 假设第一个数是最大的数
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    int maxLength = String.valueOf(max).length(); // 至此就可以知道待排序数组中最大数是几位数

    for (int i = 0; i < maxLength; i++) {
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的相应位数(个、十、百……)上的数
            int digitOfElement = arr[j] / (int) Math.pow(10,i) % 10;
            // 放入到对应的桶中
            int count = bucketElementCounts[digitOfElement]; // 记录每个桶中存放了多少个数据
            bucket[digitOfElement][count++] = 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];
                }
            }
            // 每遍历完一个桶,都要将其计数桶归零!!!!
            bucketElementCounts[k] = 0;
        }
    }
}

  1. 平均时间复杂度:O(nk)。数据规模 n,待排序数据可分为 k 个关键字
  2. 最好时间复杂度:O(nk)
  3. 最坏时间复杂度:O(nk)
  4. 空间复杂度:O(n+k)。桶数量 k
  5. 稳定性:稳定


END

本文作者:
文章标题:十大经典排序算法
本文地址:https://www.pendulumye.com/data-structure-and-algorithm/73.html
版权说明:若无注明,本文皆PendulumYe原创,转载请保留文章出处。
最后修改:2022 年 07 月 13 日
千山万水总是情,给个一毛行不行💋