关于java:面试时写不出排序算法看这篇就够了

5次阅读

共计 18779 个字符，预计需要花费 47 分钟才能阅读完成。

本文次要具体讲述常见的八种排序算法的思维、实现以及复杂度。

冒泡排序是一种替换排序。

什么是替换排序呢？

它反复地走访过要排序的数列，一次比拟两个元素，如果他们的程序谬误就把他们替换过去。走访数列的工作是反复地进行直到没有再须要替换，也就是说该数列曾经排序实现。

这个算法的名字由来是因为越小的元素会经由替换缓缓“浮”到数列的顶端，故名。

假如有一个大小为 N 的无序序列。冒泡排序就是要每趟排序过程中通过两两比拟，找到第 i 个小（大）的元素，将其往上排。

以上图为例，演示一下冒泡排序的理论流程：

假如有一个无序序列 {4. 3. 1. 2, 5}

<li>
第一趟排序：通过两两比拟，找到第一小的数值 1，将其放在序列的第一位。
</li>
<li>
第二趟排序：通过两两比拟，找到第二小的数值 2，将其放在序列的第二位。
</li>
<li>
第三趟排序：通过两两比拟，找到第三小的数值 3，将其放在序列的第三位。
</li>

至此，所有元素曾经有序，排序完结。

要将以上流程转化为代码，咱们须要像机器一样去思考，不然编译器可看不懂。

假如要对一个大小为 N 的无序序列进行升序排序（即从小到大）。

<li>
每趟排序过程中须要通过比拟找到第 i 个小的元素。
</li>
<li>
所以，咱们须要一个内部循环，从数组首端(下标 0) 开始，始终扫描到倒数第二个元素（即下标 N – 2)，剩下最初一个元素，必然为最大。
</li>

假如是第 i 趟排序，可知，前 i-1 个元素曾经有序。当初要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比拟即可。

<li>
所以，须要一个外部循环，从数组末端开始（下标 N – 1），扫描到 (下标 i + 1)。
</li>

public void bubbleSort(int[] list) {
    int temp = 0; // 用来替换的长期数

    // 要遍历的次数
    for (int i = 0; i  list.length - 1; i++) {
        // 从后向前顺次的比拟相邻两个数的大小，遍历一次后，把数组中第 i 小的数放在第 i 个地位上
        for (int j = list.length - 1; j  i; j--) {
            // 比拟相邻的元素，如果后面的数大于前面的数，则替换
            if (list[j - 1]  list[j]) {temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }

        System.out.format("第 %d 趟：t", i);
        printAll(list);
    }
}

冒泡排序算法的性能

若文件的初始状态是正序的，一趟扫描即可实现排序。所需的关键字比拟次数 C 和记录挪动次数 M 均达到最小值：Cmin = N – 1, Mmin = 0。所以，冒泡排序最好工夫复杂度为 O(N)。

若初始文件是反序的，须要进行 N -1 趟排序。每趟排序要进行 N – i 次关键字的比拟(1 ≤ i ≤ N – 1)，且每次比拟都必须挪动记录三次来达到替换记录地位。在这种状况下，比拟和挪动次数均达到最大值：

冒泡排序的最坏工夫复杂度为 O(N2)。因而，冒泡排序的均匀工夫复杂度为 O(N2)。

总结起来，其实就是一句话：当数据越靠近正序时，冒泡排序性能越好。

冒泡排序就是把小的元素往前调或者把大的元素往后调。比拟是相邻的两个元素比拟，替换也产生在这两个元素之间。

所以雷同元素的前后程序并没有扭转，所以冒泡排序是一种稳固排序算法。

对冒泡排序常见的改良办法是退出标志性变量 exchange，用于标记某一趟排序过程中是否有数据交换。

如果进行某一趟排序时并没有进行数据交换，则阐明所有数据曾经有序，可立刻完结排序，防止不必要的比拟过程。

外围代码

// 对 bubbleSort 的优化算法
public void bubbleSort_2(int[] list) {
    int temp = 0; // 用来替换的长期数
    boolean bChange = false; // 替换标记

    // 要遍历的次数
    for (int i = 0; i  list.length - 1; i++) {
        bChange = false;
        // 从后向前顺次的比拟相邻两个数的大小，遍历一次后，把数组中第 i 小的数放在第 i 个地位上
        for (int j = list.length - 1; j  i; j--) {
            // 比拟相邻的元素，如果后面的数大于前面的数，则替换
            if (list[j - 1]  list[j]) {temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
                bChange = true;
            }
        }

        // 如果标记为 false，阐明本轮遍历没有替换，曾经是有序数列，能够完结排序
        if (false == bChange)
            break;

        System.out.format("第 %d 趟：t", i);
        printAll(list);
    }
}

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

疾速排序是一种替换排序。

疾速排序由 C. A. R. Hoare 在 1962 年提出。

它的根本思维是：

通过一趟排序将要排序的数据宰割成独立的两局部：宰割点右边都是比它小的数，左边都是比它大的数。

而后再按此办法对这两局部数据别离进行疾速排序，整个排序过程能够递归进行，以此达到整个数据变成有序序列。

具体的图解往往比大堆的文字更有阐明力，所以间接上图：

上图中，演示了疾速排序的处理过程：

<li>
初始状态为一组无序的数组：2、4、5、1、3。
</li>
<li>
通过以上操作步骤后，实现了第一次的排序，失去新的数组：1、2、5、4、3。
</li>
<li>
新的数组中，以 2 为宰割点，右边都是比 2 小的数，左边都是比 2 大的数。
</li>
<li>
因为 2 曾经在数组中找到了适合的地位，所以不必再动。
</li>
<li>
2 右边的数组只有一个元素 1，所以显然不必再排序，地位也被确定。（注：这种状况时，left 指针和 right 指针显然是重合的。因而在代码中，咱们能够通过设置断定条件 left 必须小于 right，如果不满足，则不必排序了）。
</li>
<li>
而对于 2 左边的数组 5、4、3，设置 left 指向 5，right 指向 3，开始持续反复图中的一、二、三、四步骤，对新的数组进行排序。
</li>

外围代码

public int division(int[] list, int left, int right) {// 以最右边的数 (left) 为基准
    int base = list[left];
    while (left  right) {
        // 从序列右端开始，向左遍历，直到找到小于 base 的数
        while (left  right && list[right] = base)
            right--;
        // 找到了比 base 小的元素，将这个元素放到最右边的地位
        list[left] = list[right];

        // 从序列左端开始，向右遍历，直到找到大于 base 的数
        while (left  right && list[left] = base)
            left++;
        // 找到了比 base 大的元素，将这个元素放到最左边的地位
        list[right] = list[left];
    }

    // 最初将 base 放到 left 地位。此时，left 地位的左侧数值应该都比 left 小；// 而 left 地位的右侧数值应该都比 left 大。list[left] = base;
    return left;
}

private void quickSort(int[] list, int left, int right) {

    // 左下标肯定小于右下标，否则就越界了
    if (left  right) {
        // 对数组进行宰割，取出下次宰割的基准标号
        int base = division(list, left, right);

        System.out.format("base = %d:t", list[base]);
        printPart(list, left, right);

        // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值残缺的排序
        quickSort(list, left, base - 1);

        // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值残缺的排序
        quickSort(list, base + 1, right);
    }
}

疾速排序算法的性能

当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。

而当数据随机散布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数靠近相等，此时执行效率最好。

所以，数据越随机散布时，疾速排序性能越好；数据越靠近有序，疾速排序性能越差。

疾速排序在每次宰割的过程中，须要 1 个空间存储基准值。而疾速排序的大略须要 Nlog2N 次的宰割解决，所以占用空间也是 Nlog2N 个。

在疾速排序中，相等元素可能会因为分区而替换程序，所以它是不稳固的算法。

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

间接插入排序是一种最简略的插入排序。

插入排序：每一趟将一个待排序的记录，依照其关键字的大小插入到有序队列的适合地位里，晓得全副插入实现。

在解说间接插入排序之前，先让咱们脑补一下咱们打牌的过程。

<li>
先拿一张 5 在手里，
</li>
<li>
再摸到一张 4，比 5 小，插到 5 后面，
</li>
<li>
摸到一张 6，嗯，比 5 大，插到 5 前面，
</li>
<li>
摸到一张 8，比 6 大，插到 6 前面，
</li>
<li>
。。。
</li>
<li>
最初一看，我靠，凑到的竟然是同花顺，这下牛逼大了。
</li>

以上的过程，其实就是典型的间接插入排序，每次将一个新数据插入到有序队列中的适合地位里。

很简略吧，接下来，咱们要将这个算法转化为编程语言。

假如有一组无序序列 R0, R1, … , RN-1。

<li>
咱们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
</li>
<li>
而后，咱们要顺次把 R1, R2, … , RN-1 插入到这个有序序列中。所以，咱们须要一个内部循环，从下标 1 扫描到 N-1。
</li>
<li>
接下来形容插入过程。假如这是要将 Ri 插入到后面有序的序列中。由后面所述，咱们可知，插入 Ri 时，前 i-1 个数必定曾经是有序了。
</li>

所以咱们须要将 Ri 和 R0 ~ Ri-1 进行比拟，确定要插入的适合地位。这就须要一个外部循环，咱们个别是从后往前比拟，即从下标 i-1 开始向 0 进行扫描。(对于常见排序算法更多学习，能够在 Java 知音公众号回复“排序算法聚合”)

外围代码

public void insertSort(int[] list) {
   // 打印第一个元素
   System.out.format("i = %d:t", 0);
   printPart(list, 0, 0);

   // 第 1 个数必定是有序的，从第 2 个数开始遍历，顺次插入有序序列
   for (int i = 1; i  list.length; i++) {
       int j = 0;
       int temp = list[i]; // 取出第 i 个数，和前 i - 1 个数比拟后，插入适合地位

       // 因为前 i - 1 个数都是从小到大的有序序列，所以只有以后比拟的数 (list[j]) 比 temp 大，就把这个数后移一位
       for (j = i - 1; j = 0 && temp  list[j]; j--) {list[j + 1] = list[j];
       }
       list[j + 1] = temp;

       System.out.format("i = %d:t", i);
       printPart(list, 0, i);
   }
}

间接插入排序的算法性能

当数据正序时，执行效率最好，每次插入都不必挪动后面的元素，工夫复杂度为 O(N)。

当数据反序时，执行效率最差，每次插入都要后面的元素后移，工夫复杂度为 O(N2)。

所以，数据越靠近正序，间接插入排序的算法性能越好。

由间接插入排序算法可知，咱们在排序过程中，须要一个长期变量存储要插入的值，所以空间复杂度为 1。

间接插入排序的过程中，不须要扭转相等数值元素的地位，所以它是稳固的算法。

示例代码

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

希尔 (Shell) 排序又称为放大增量排序，它是一种插入排序。它是间接插入排序算法的一种威力加强版。

该办法因 DL．Shell 于 1959 年提出而得名。

希尔排序的根本思维是：

把记录按步长 gap 分组，对每组记录采纳间接插入排序办法进行排序。

随着步长逐步减小，所分成的组蕴含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，形成一组有序记录，则实现排序。

咱们来通过演示图，更深刻的了解一下这个过程。

在下面这幅图中：

初始时，有一个大小为 10 的无序序列。

在第一趟排序中，咱们无妨设 gap1 = N / 2 = 5，即相隔间隔为 5 的元素组成一组，能够分为 5 组。

<li>
接下来，依照间接插入排序的办法对每个组进行排序。
</li>

在 第二趟排序中，咱们把上次的 gap 放大一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔间隔为 2 的元素组成一组，能够分为 2 组。

<li>
依照间接插入排序的办法对每个组进行排序。
</li>

在第三趟排序中，再次把 gap 放大一半，即 gap3 = gap2 / 2 = 1。这样相隔间隔为 1 的元素组成一组，即只有一组。

<li>
依照间接插入排序的办法对每个组进行排序。此时，排序曾经完结。
</li>

须要留神一下的是，图中有两个相等数值的元素 5 和 5。咱们能够分明的看到，在排序过程中，两个元素地位替换了。

所以，希尔排序是不稳固的算法。

外围代码

public void shellSort(int[] list) {
   int gap = list.length / 2;

   while (1 = gap) {
       // 把间隔为 gap 的元素编为一个组，扫描所有组
       for (int i = gap; i  list.length; i++) {
           int j = 0;
           int temp = list[i];

           // 对间隔为 gap 的元素组进行排序
           for (j = i - gap; j = 0 && temp  list[j]; j = j - gap) {list[j + gap] = list[j];
           }
           list[j + gap] = temp;
       }

       System.out.format("gap = %d:t", gap);
       printAll(list);
       gap = gap / 2; // 减小增量
   }
}

希尔排序的算法性能

步长的抉择是希尔排序的重要局部。只有最终步长为 1 任何步长序列都能够工作。

算法最开始以肯定的步长进行排序。而后会持续以肯定步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为插入排序，这就保障了数据肯定会被排序。

Donald Shell 最后倡议步长抉择为 N/2 并且对步长取半直到步长达到 1。尽管这样取能够比 O(N2)类的算法（插入排序）更好，但这样依然有缩小均匀工夫和最差工夫的余地。可能希尔排序最重要的中央在于当用较小步长排序后，以前用的较大步长依然是有序的。

比方，如果一个数列以步长 5 进行了排序而后再以步长 3 进行排序，那么该数列不仅是以步长 3 有序，而且是以步长 5 有序。如果不是这样，那么算法在迭代过程中会打乱以前的程序，那就不会以如此短的工夫实现排序了。

已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)，该序列的项来自这两个算式。

这项钻研也表明“比拟在希尔排序中是最次要的操作，而不是替换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比疾速排序还快，然而在波及大量数据时希尔排序还是比疾速排序慢。

由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会替换地位，所以希尔排序是不稳固的算法。

<li>
间接插入排序是稳固的；而希尔排序是不稳固的。
</li>
<li>
间接插入排序更适宜于原始记录根本有序的汇合。
</li>
<li>
希尔排序的比拟次数和挪动次数都要比间接插入排序少，当 N 越大时，成果越显著。
</li>
<li>
在希尔排序中，增量序列 gap 的取法必须满足：最初一个步长必须是 1。
</li>
<li>
间接插入排序也实用于链式存储构造；希尔排序不适用于链式构造。
</li>

示例代码

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。(对于常见排序算法更多学习，能够在 Java 知音公众号回复“排序算法聚合”)

简略抉择排序是一种抉择排序。

抉择排序：每趟从待排序的记录中选出关键字最小的记录，程序放在已排序的记录序列开端，直到全副排序完结为止。

<li>
从待排序序列中，找到关键字最小的元素；
</li>
<li>
如果最小元素不是待排序序列的第一个元素，将其和第一个元素调换；
</li>
<li>
从余下的 N – 1 个元素中，找出关键字最小的元素，反复 1、2 步，直到排序完结。
</li>

如图所示，每趟排序中，将以后 第 i 小的元素放在地位 i 上。

简略抉择排序算法的性能

简略抉择排序的比拟次数与序列的初始排序无关。假如待排序的序列有 N 个元素，则 比拟次数总是 N (N – 1) / 2 。

而挪动次数与序列的初始排序无关。当序列正序时，挪动次数起码，为 0。

当序列反序时，挪动次数最多，为 3N (N – 1) / 2。

所以，综合以上，简略排序的工夫复杂度为 O(N2)。

简略抉择排序须要占用一个长期空间，在替换数值时应用。

示例代码

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

在介绍堆排序之前，首先须要阐明一下，堆是个什么玩意儿。

堆是一棵顺序存储的齐全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于 n 个元素的序列 {R0, R1, … , Rn} 当且仅当满足下列关系之一时，称之为堆：

其中 i=1,2,…,n/2 向下取整;

如上图所示，序列 R{3, 8,15, 31, 25} 是一个典型的小根堆。

堆中有两个父结点，元素 3 和元素 8。

元素 3 在数组中以 R[0] 示意，它的左孩子结点是 R[1]，右孩子结点是 R[2]。

元素 8 在数组中以 R[1] 示意，它的左孩子结点是 R[3]，右孩子结点是 R[4]，它的父结点是 R[0]。能够看出，它们满足以下法则：

设以后元素在数组中以 R[i] 示意，那么，

<li>
它的左孩子结点是：R[2*i+1];
</li>
<li>
它的右孩子结点是：R[2*i+2];
</li>
<li>
它的父结点是：R[(i-1)/2];
</li>
<li>
R[i] = R[2*i+1] 且 R[i] = R[2i+2]。
</li>

<li>
首先，按堆的定义将数组 R[0..n]调整为堆（这个过程称为创立初始堆），替换 R[0]和 R[n]；
</li>
<li>
而后，将 R[0..n-1]调整为堆，替换 R[0]和 R[n-1]；
</li>
<li>
如此重复，直到替换了 R[0]和 R[1]为止。
</li>

以上思维可演绎为两个操作：

<li>
依据初始数组去结构初始堆（构建一个齐全二叉树，保障所有的父结点都比它的孩子结点数值大）。
</li>
<li>
每次替换第一个和最初一个元素，输入最初一个元素（最大值），而后把剩下元素从新调整为大根堆。
</li>

当输入完最初一个元素后，这个数组曾经是依照从小到大的顺序排列了。

先通过具体的实例图来看一下，如何构建初始堆。

设有一个无序序列 {1, 3,4, 5, 2, 6, 9, 7, 8, 0}。

结构了初始堆后，咱们来看一下残缺的堆排序解决：

还是针对后面提到的无序序列 {1,3, 4, 5, 2, 6, 9, 7, 8, 0} 来加以阐明。

置信，通过以上两幅图，应该能很直观的演示堆排序的操作解决。

外围代码

public void HeapAdjust(int[] array, int parent, int length) {int temp = array[parent]; // temp 保留以后父节点
    int child = 2 * parent + 1; // 先取得左孩子

    while (child  length) {
        // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
        if (child + 1  length && array[child]  array[child + 1]) {child++;}

        // 如果父结点的值曾经大于孩子结点的值，则间接完结
        if (temp = array[child])
            break;

        // 把孩子结点的值赋给父结点
        array[parent] = array[child];

        // 选取孩子结点的左孩子结点, 持续向下筛选
        parent = child;
        child = 2 * child + 1;
    }

    array[parent] = temp;
}

public void heapSort(int[] list) {
    // 循环建设初始堆
    for (int i = list.length / 2; i = 0; i--) {HeapAdjust(list, i, list.length);
    }

    // 进行 n - 1 次循环，实现排序
    for (int i = list.length - 1; i  0; i--) {
        // 最初一个元素和第一元素进行替换
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;

        // 筛选 R[0] 结点，失去 i - 1 个结点的堆
        HeapAdjust(list, 0, i);
        System.out.format("第 %d 趟: t", list.length - i);
        printPart(list, 0, list.length - 1);
    }
}

堆排序算法的总体状况

堆的存储示意是程序的。因为堆所对应的二叉树为齐全二叉树，而齐全二叉树通常采纳顺序存储形式。

当想得到一个序列中第 k 个最小的元素之前的局部排序序列，最好采纳堆排序。

因为堆排序的工夫复杂度是 O(n+klog2n)，若 k ≤ n/log2n，则可失去的工夫复杂度为 O(n)。

堆排序是一种不稳固的排序办法。

因为在堆的调整过程中，关键字进行比拟和交换所走的是该结点到叶子结点的一条门路，因而对于雷同的关键字就可能呈现排在前面的关键字被替换到后面来的状况。

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

归并排序是建设在归并操作上的一种无效的排序算法，该算法是采纳 分治法（Divide and Conquer）的一个十分典型的利用。

将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

将待排序序列 R[0…n-1] 看成是 n 个长度为 1 的有序序列，将相邻的有序表成对归并，失去 n/2 个长度为 2 的有序表；将这些有序序列再次归并，失去 n/4 个长度为 4 的有序序列；如此重复进行上来，最初失去一个长度为 n 的有序序列。

综上可知：

归并排序其实要做两件事：

<li>
“合成”——将序列每次折半划分。
</li>
<li>
“合并”——将划分后的序列段两两合并后排序。
</li>

咱们先来思考第二步，如何合并？

在每次合并过程中，都是对两个有序的序列段进行合并，而后排序。

这两个有序序列段别离为 R[low, mid] 和 R[mid+1, high]。

先将他们合并到一个部分的暂存数组 R2 中，带合并实现后再将 R2 复制回 R 中。

为了不便形容，咱们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。

每次从两个段中取出一个记录进行关键字的比拟，将较小者放入 R2 中。最初将各段中余下的局部间接复制到 R2 中。

通过这样的过程，R2 曾经是一个有序的序列，再将其复制回 R 中，一次合并排序就实现了。

外围代码

public void Merge(int[] array, int low, int mid, int high) {
    int i = low; // i 是第一段序列的下标
    int j = mid + 1; // j 是第二段序列的下标
    int k = 0; // k 是长期寄存合并序列的下标
    int[] array2 = new int[high - low + 1]; // array2 是长期合并序列

    // 扫描第一段和第二段序列，直到有一个扫描完结
    while (i = mid && j = high) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并持续向下扫描
        if (array[i] = array[j]) {array2[k] = array[i];
            i++;
            k++;
        } else {array2[k] = array[j];
            j++;
            k++;
        }
    }

    // 若第一段序列还没扫描完，将其全副复制到合并序列
    while (i = mid) {array2[k] = array[i];
        i++;
        k++;
    }

    // 若第二段序列还没扫描完，将其全副复制到合并序列
    while (j = high) {array2[k] = array[j];
        j++;
        k++;
    }

    // 将合并序列复制到原始序列中
    for (k = 0, i = low; i = high; i++, k++) {array[i] = array2[k];
    }
}

把握了合并的办法，接下来，让咱们来理解如何合成。

在某趟归并中，设各子表的长度为 gap，则归并前 R[0…n-1] 中共有 n/gap 个有序的子表：R[0…gap-1], R[gap…2gap-1], … , R[(n/gap)gap … n-1]。

调用 Merge 将相邻的子表归并时，必须对表的非凡状况进行非凡解决。

若子表个数为奇数，则最初一个子表毋庸和其余子表归并（即本趟解决轮空）：若子表个数为偶数，则要留神到最初一对子表中后一个子表区间的下限为 n-1。

外围代码

public void MergePass(int[] array, int gap, int length) {
    int i = 0;

    // 归并 gap 长度的两个相邻子表
    for (i = 0; i + 2 * gap - 1  length; i = i + 2 * gap) {Merge(array, i, i + gap - 1, i + 2 * gap - 1);
    }

    // 余下两个子表，后者长度小于 gap
    if (i + gap - 1  length) {Merge(array, i, i + gap - 1, length - 1);
    }
}

public int[] sort(int[] list) {for (int gap = 1; gap  list.length; gap = 2 * gap) {MergePass(list, gap, list.length);
        System.out.print("gap =" + gap + ":t");
        this.printAll(list);
    }
    return list;
}

归并排序算法的性能

归并排序的模式就是一棵二叉树，它须要遍历的次数就是二叉树的深度，而依据齐全二叉树的能够得出它的工夫复杂度是 O(n*log2n)。

由后面的算法阐明可知，算法处理过程中，须要一个大小为 n 的长期存储空间用以保留合并序列。

在归并排序中，相等的元素的程序不会扭转，所以它是稳固的算法。

<li>
若从空间复杂度来思考：首选堆排序，其次是疾速排序，最初是归并排序。
</li>
<li>
若从稳定性来思考，应选取归并排序，因为堆排序和疾速排序都是不稳固的。
</li>
<li>
若从均匀状况下的排序速度思考，应该抉择疾速排序。
</li>

示例代码

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

基数排序与本系列后面解说的七种排序办法都不同，它不须要比拟关键字的大小。

它是依据关键字中各位的值，通过对排序的 N 个元素进行若干趟“调配”与“收集”来实现排序的。

无妨通过一个具体的实例来展现一下，基数排序是如何进行的。

设有一个初始序列为: R {50, 123, 543, 187, 49, 30,0, 2, 11, 100}。

咱们晓得，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来示意的。

所以咱们无妨把 0~9 视为 10 个桶。

咱们先依据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，咱们在从各个桶中，将这些数依照从编号 0 到编号 9 的程序顺次将所有数取出来。

这时，失去的序列就是个位数上呈递增趋势的序列。

依照个位数排序：{50, 30, 0, 100, 11, 2, 123,543, 187, 49}。

接下来，能够对十位数、百位数也依照这种办法进行排序，最初就能失去排序实现的序列。

基数排序的性能

通过上文可知，假如在基数排序中，r 为基数，d 为位数。则基数排序的工夫复杂度为 O(d(n+r))。

咱们能够看出，基数排序的效率和初始序列是否有序没有关联。

在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都须要 n+r 个长期空间。

在基数排序过程中，每次都是将以后位数上雷同数值的元素对立“装桶”，并不需要替换地位。所以基数排序是稳固的算法。

样本蕴含：数组个数为奇数、偶数的状况；元素反复或不反复的状况。且样本均为随机样本，实测无效。

最初，给大家分享我珍藏的几个不错的 github 我的项目，内容都还是不错的，如果感觉有帮忙，能够顺便给个 star。

计算机专业学生必须要啃的书籍举荐: https://github.com/hello-go-maker/cs-books
Java 实战我的项目举荐: https://github.com/hello-go-maker/Java-project
举荐一些很不错的计算机学习教程，包含：数据结构、算法、计算机网络、操作系统、Java（spring、springmvc、springboot、springcloud），也包含多个企业级实战我的项目: https://github.com/hello-go-maker/cs-learn-source
Java 面试 +Java 后端技术学习指南】：一份通向现实互联网公司的面试指南，包含 Java，技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、零碎设计、分布式、数据库（MySQL、Redis）、Java 我的项目实战等: https://github.com/hello-java-maker/JavaInterview

正文完

java

发表至： java

2022-03-02

0

关于分布式:分布式链路追踪系统-Zipkin-埋点库-Brave-使用入门

java实现微信公众平台发送模板消息

关于java:Socket粘包问题的3种解决方案最后一种最完美

对于单例模式面试官会怎样提问呢你又该如何回答呢

关于php:php内存泄露的原因分析和垃圾回收机制的探讨

关于java:面试时写不出排序算法看这篇就够了

冒泡排序

要点

算法思维

算法剖析

工夫复杂度

算法稳定性

优化

示例代码

疾速排序

要点

算法思维

算法剖析

工夫复杂度

空间复杂度

算法稳定性

示例代码

插入排序

要点

算法思维

算法剖析

工夫复杂度

空间复杂度

算法稳定性

希尔排序

要点

算法思维

算法剖析

工夫复杂度

算法稳定性

间接插入排序和希尔排序的比拟

简略抉择排序

要点

算法思维

算法剖析

工夫复杂度

空间复杂度

堆排序

要点

算法思维

算法剖析

工夫复杂度

算法稳定性

示例代码

归并排序

要点

算法思维

算法剖析

工夫复杂度

空间复杂度

算法稳定性

归并排序和堆排序、疾速排序的比拟

基数排序

要点

算法剖析

工夫复杂度

空间复杂度

算法稳定性

示例代码

站内搜索