当前位置：自学咖网 > 技术教程 > 编程最新 > 十大排序算法
wenwen 编程最新

十大排序算法

十大排序算法

冒泡排序

  1. 从数组头开始，比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个
  2. 对每一对相邻元素作同样的工作，从开始第一对到尾部的最后一对，这样在最后的元素应该会是最大(小)的数
  3. 重复步骤1~2，重复次数等于数组的长度，直到排序完成

image-20210728113340011

代码实现

对下面数组实现排序：{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

代码实现

public class BubbleSort {

    public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }

    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //array.length - 1 -i 已经冒泡到合适位置无需在进行排序，减少比较次数
            for (int j = 0; j < array.length - 1 -i; j++) {
                //前面的数大于后面的数交换
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
}

时间复杂度

对于上面12个数据项，从第一个元素开始，第一趟比较了11次，第二趟比较了10次，依次类推，一直到最后一趟，就是：

11 + 10 + 9 + 8 + 7 + 6 + 5  + 4 + 3  + 2 + 1  =  66次

若有n个元素，则第一趟比较为(n-1)次，第二趟比较为(n-2)次，依次类推：

(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2

在大O表示法中，去掉常数系数和低阶项，该排序方式的时间复杂度为：O(n2)

算法稳定性

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

在代码中可以看到，array[j + 1] = array[j]的时候，我们可以不移动array[i]和array[j]，所以冒泡排序是稳定的。

选择排序

  1. 找到数组中最大（或最小）的元素
  2. 将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）
  3. 在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

image-20210728144443166

代码实现

对下面数组实现排序：{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}

动图演示

选择排序

代码实现

public class SelectionSort {

    public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};

    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //最小数的下标，每个循环开始总是假设第一个数最小
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                //找到最小索引
                if (array[j] < array[minIndex]) {
                    //保存最小索引
                    minIndex = j;
                }
            }
            //最小索引的值
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

很明显，和冒泡排序相比，在查找最小（或最大）元素的索引，比较次数仍然保持为O(n2)

，但元素交换次数为O(n)。

算法稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，数组5，8，5，2，9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

image-20210728144637093

插入排序

当我们在玩扑克牌的时候，总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

  1. 对于未排序数据（一般取数组的二个元素，把第一个元素当做有序数组），在已排序序列中从左往右扫描，找到相应位置并插入。
  2. 为了给要插入的元素腾出空间，需要将插入位置之后的已排序元素在都向后移动一位。

image-20210728162127494

代码实现

对下面数组实现排序：{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

动图演示

插入排序

代码实现

public class InsertionSort {

    public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};

    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        //待排序数据，改数据之前的已被排序
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            //已被排序数据的索引
            int index = i;
            current = array[index + 1];
            //将当前元素后移一位
            while (index >= 0 && current < array[index]) {
                array[index + 1] = array[index];
                index--;
            }
            //插入
            array[index + 1] = current;
        }
        return array;
    }


    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

在上面图示中，第一趟循环比较一次，第二趟循环两次，依次类推，则最后一趟比较n-1次：

1 + 2 + 3 +… + n-1 = n*(n-1)/2

也就是说，在最坏的情况下（逆序），比较的时间复杂度为O(n2)

在最优的情况下，即while循坏总是假的，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n-1次，时间复杂度为O(n)。

算法稳定性

在比较的时候，过两个数相等的话，不会进行移动，前后两个数的次序不会发生改变，所以插入排序是稳定的。

希尔排序

一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要n-1次移动。

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序。

希尔排序是把待排序数组按一定的数量分组，对每组使用直接插入排序算法排序；然后缩小数量继续分组排序，随着数量逐渐减少，每组包含的元素越来越多，当数量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的数量，就构成了一个增量序列，这里的数量称为增量。

image-20210729135834646

代码实现

public class ShellSort {

    public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};

    public static int[] sort(int[] array) {
        int len = array.length;
        if (len < 2) {
            return array;
        }
        //当前待排序数据，该数据之前的已被排序
        int current;
        //增量
        int gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                //前面有序序列的索引
                int index = i - gap;
                while (index >= 0 && current < array[index]) {
                    array[index + gap] = array[index];
                    //有序序列的下一个
                    index -= gap;
                }
                //插入
                array[index + gap] = current;
            }
            //int相除取整
            gap = gap / 2;
        }
        return array;
    }


    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

希尔排序的复杂度和增量序列有关。

在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高，尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。

从理论上说，只要一个数组是递减的，并且最后一个值是1，都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢？但是目前从数学上来说，无法证明某个序列是最好的。

常用的增量序列：

  • 希尔增量序列 ：{n/2, (n / 2)/2, …, 1}，其中N为原始数组的长度，这是最常用的序列，但却不是最好的
  • Hibbard序列：{2k-1, …, 3,1}
  • Sedgewick序列：{… , 109 , 41 , 19 , 5，1} 表达式为9 * 4i– 9 * 2i + 1，i = 0，1，2，3，4…

算法稳定性

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，如数组5，2，2，1，第一次排序第一个元素5会和第三个元素2交换，第二个元素2会和第四个元素1交换，原序列中两个2的相对前后顺序就被破坏了，所以希尔排序是一个不稳定的排序算法。

image-20210729165300142

归并排序

归并，指合并，合在一起。归并排序（Merge Sort）是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么是分而治之？分而治之就是将一个复杂的计算，按照设定的阈值进行分解成多个计算，然后将各个计算结果进行汇总。即“分”就是把一个大的通过递归拆成若干个小的，“治”就是将分后的结果在合在一起。

若将两个有序集合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

image-20210730115340519

怎么分

  • 对于排序最好的情况来讲，就是只有两个元素，这时候比较大小就很简单，但是还是需要比较
  • 如果拆分为左右各一个，无需比较即是有序的。

怎么治

借助一个辅助空数组，把左右两边的数组按照大小比较，按顺序放入辅助数组中即可。

以下面两个有序数组为例：

归并排序

代码实现

public class MergeSort {
    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};

    public static int[] sort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        //分成2组
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        //递归拆分
        return merge(sort(left), sort(right));
    }

    //治---合并
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        //i代表左边数组的索引，j代表右边
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {//说明左侧的数据已经全部取完，取右边的数据
                result[index] = right[j++];
            } else if (j >= right.length) {//说明右侧的数据已经全部取完，取左边的数据
                result[index] = left[i++];
            } else if (left[i] > right[j]) {//左边大于右边，取右边的
                int a = right[j++];
                result[index] = a;
            } else {//右边大于左边，取左边的
                result[index] = left[i++];
            }
        }
        return result;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

归并排序方法就是把一组n个数的序列，折半分为两个序列，然后再将这两个序列再分，一直分下去，直到分为n个长度为1的序列。然后两两按大小归并。如此反复，直到最后形成包含n个数的一个数组。

归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间

无论每个序列有多少数都是折中分解，所以分解时间是个常数，可以忽略不计，则：

归并排序总时间 = 子序列排好序时间 + 合并时间

假设处理的数据规模大小为 n，运行时间设为：T(n)，则T(n) = n，当 n = 1时，T(1) = 1

由于在合并时，两个子序列已经排好序，所以在合并的时候只需要 if 判断即可，所以n个数比较，合并的时间复杂度为 n。

  • 将 n 个数的序列，分为两个 n/2 的序列，则：T(n) = 2T(n/2) + n
  • 将 n/2 个数的序列，分为四个 n/4 的序列，则：T(n) = 4T(n/4) + 2n
  • 将 n/4 个数的序列，分为八个 n/8 的序列，则：T(n) = 8T(n/8) + 3n
  • ……
  • 将 n/2k 个数的序列，分为2k个 n/2k 的序列，则：T(n) = 2kT(n/2k) + kn

当 T(n/2k) = T(1)时， 即n/2k = 1（此时也是把n分解到只有1个数据的时候），转换为以2为底n的对数：k = log2n，把k带入到T(n)中，得：T(n) = n + nlog2n。

使用大O表示法，去掉常数项 n，省略底数 2，则归并排序的时间复杂度为：O(nlogn)

算法稳定性

从原理分析和代码可以看出，为在合并的时候，如果相等，选择前面的元素到辅助数组，所以归并排序是稳定的。

快速排序

快速排序是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。JDK中Arrays的sort()方法，具体的排序细节就是使用快速排序实现的。

从数组中任意选取一个数据（比如数组的第一个数或最后一个数）作为关键数据，我们称为基准数(pivot，或中轴数)，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。

问题

若给定一个无序数组 [8, 5, 6, 4, 3, 1, 7, 2]，并指定一个数为基准，拆分数组使得左侧的数都小于等于它 ，右侧的数都大于它。

基准的选取最优的情况是基准值刚好取在无序区数值的中位数，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式：

  • 选取数组的第一个元素
  • 选取数组的最后一个元素
  • 以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为５, 所以选择5作为基准）。

思路

  1. 随机选择数组的一个元素，比如 6 为基准，拆分数组同时引入一个初始指针，也叫分区指示器，初始指针指向 -1
  2. 将数组中的元素和基准数遍历比较
  3. 若当前元素大于基准数，不做任何变化
  4. 若当前元素小于等于基准数时，分割指示器右移一位，同时
    • 当前元素下标小于等于分区指示器时，当前元素保持不动
    • 当前元素下标大于分区指示器时，当前元素和分区指示器所指元素交换

快速排序

荷兰国旗问题

荷兰的国旗是由红白蓝三种颜色构成，如图：

若现在给一个随机的图形，如下：

image-20210803151023780

把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，这类问题称作荷兰国旗问题。

对应leetcode：颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

分析：

假如给定一个数组[8, 3, 6, 2, 5, 1, 7, 5]，做如下操作：

  1. 随机选择数组的一个元素，比如 5 为基准，拆分数组同时引入一个左分区指示器，指向 -1，右分区指示器指向基准数（注：此时的基准数为尾元素）

  2. 若当前元素大于基准数，右分区指示器左移一位，当前元素和右分区指示器所指元素交换，

    索引保持不变

  3. 若当前元素小于等于基准数时，左分区指示器右移一位，索引右移

    • 当前元素大于等于左分区指示器所指元素，当前元素保持不动
    • 当前元素小于左分区指示器所指元素，交换

简单来说就是，左分区指示器向右移动的过程中，如果遇到大于或等于基准数时，则停止移动，右分区指示器向左移动的过程中，如果遇到小于或等于主元的元素则停止移动。这种操作也叫双向快速排序。

345345

代码实现

public class QuickSort {

    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};

    public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};

    private static int[] sort(int[] array, int left, int right) {
        if (array.length < 1 || left > right) return null;
        //拆分
        int partitionIndex = partition(array, left, right);
        //递归
        if (partitionIndex > left) {
            sort(array, left, partitionIndex - 1);
        }
        if (partitionIndex < right) {
            sort(array, partitionIndex + 1, right);
        }
        return array;
    }

    /**
     * 分区快排操作
     *
     * @param array 原数组
     * @param left  左侧头索引
     * @param right 右侧尾索引
     * @return 分区指示器  最后指向基准数
     */
    public static int partition(int[] array, int left, int right) {
        //基准数下标---随机方式取值，也就是数组的长度随机1-8之间
        int pivot = (int) (left + Math.random() * (right - left + 1));
        //分区指示器索引
        int partitionIndex = left - 1;
        //基准数和尾部元素交换
        swap(array, pivot, right);
        //按照规定，如果当前元素大于基准数不做任何操作；
        //小于基准数，分区指示器右移，且当前元素的索引大于分区指示器，交换
        for (int i = left; i <= right; i++) {
            if (array[i] <= array[right]) {//当前元素小于等于基准数
                partitionIndex++;
                if (i > partitionIndex) {//当前元素的索引大于分区指示器
                    //交换
                    swap(array, i, partitionIndex);
                }
            }
        }
        return partitionIndex;
    }

    /**
     * 双向扫描排序
     */
    public static int partitionTwoWay(int[] array, int left, int right) {
        //基准数
        int pivot = array[right];
        //左分区指示器索引
        int leftIndex = left - 1;
        //右分区指示器索引
        int rightIndex = right;
        //索引
        int index = left;
        while (index < rightIndex) {
            //若当前元素大于基准数，右分区指示器左移一位，当前元素和右分区指示器所指元素交换，索引保持不变
            if (array[index] > pivot) {
                swap(array, index, --rightIndex);
            } else if (array[index] <= pivot) {//当前元素小于等于基准数时，左分割指示器右移一位，索引右移
                leftIndex++;
                index++;
                //当前元素小于等于左分区指示器所指元素，交换
                if (array[index] < array[leftIndex]) {
                    swap(array, index, leftIndex);
                }
            }
        }
        //索引和 L 指向同一个元素
        swap(array, right, rightIndex);
        return 1;
    }

    //交换
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }


    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY, 0, ARRAY.length - 1));
        System.out.println("====================双向排序==================");
        print(ARRAY2);
        System.out.println("============================================");
        print(sort(ARRAY2, 0, ARRAY2.length - 1));
    }
}

时间复杂度

在拆分数组的时候可能会出现一种极端的情况，每次拆分的时候，基准数左边的元素个数都为0，而右边都为n-1个。这个时候，就需要拆分n次了。而每次拆分整理的时间复杂度为O(n)，所以最坏的时间复杂度为O(n2)。什么意思？举个简单例子：

在不知道初始序列已经有序的情况下进行排序，第1趟排序经过n-1次比较后，将第1个元素仍然定在原来的位置上，并得到一个长度为n-1的子序列；第2趟排序经过n-2次比较后，将第2个元素确定在它原来的位置上，又得到一个长度为n-2的子序列；以此类推，最终总的比较次数：

C(n) = (n-1) + (n-2) + … + 1 = n(n-1)/2

所以最坏的情况下，快速排序的时间复杂度为O(n^2)

而最好的情况就是每次拆分都能够从数组的中间拆分，这样拆分logn次就行了，此时的时间复杂度为O(nlogn)。

而平均时间复杂度，则是假设每次基准数随机，最后算出来的时间复杂度为O(nlogn)

参考：快速排序的时间复杂度与空间复杂度

算法稳定性

通过上面的分析可以知道，在随机取基准数的时候，数据是可能会发生变化的，所以快速排序有不是稳定的情况。

堆排序

这里的堆并不是JVM中堆栈的堆，而是一种特殊的二叉树，通常也叫作二叉堆。它具有以下特点：

  • 它是完全二叉树
  • 堆中某个结点的值总是不大于或不小于其父结点的值

知识补充

二叉树

树中节点的子节点不超过2的有序树

image-20210804135913978

满二叉树

二叉树中除了叶子节点，每个节点的子节点都为2，则此二叉树为满二叉树。

image-20210804140132004

完全二叉树

如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右。则深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

image-20210804144904950

二叉堆

二叉堆是一种特殊的堆，可以被看做一棵完全二叉树的数组对象，而根据其性质又可以分为下面两种：

  • 大根堆：每一个根节点都大于等于它的左右孩子节点，也叫最大堆
  • 小根堆：每一个根节点都小于等于它的左右孩子节点，也叫最小堆

如果把一个数组通过大根堆的方式来表示（数组元素的值是可变的），如下：

image-20210804180209118

由此可以推出：

  • 对于位置为 k 的节点，其子节点的位置分别为，左子节点 = 2k + 1，右子节点 = 2(k + 1)

    如：对于 k = 1，其节点的对应数组为 5

    左子节点的位置为 3，对应数组的值为 3

    右子节点的位置为 4，对应数组的值为 2

  • 最后一个非叶子节点的位置为 (n/2) – 1，n为数组长度

    如：数组长度为6，则 (6/2) – 1 = 2，即位置 2 为最后一个非叶子节点

给定一个随机数组[35,63,48,9,86,24,53,11]，将该数组视为一个完全二叉树：

image-20210804190655494

从上图很明显的可以看出，这个二叉树不符合大根堆的定义，但是可以通过调整，使它变为最大堆。如果从最后一个非叶子节点开始，从下到上，从右往左调整，则：

image-20210804224254053

通过上面的调整，该二叉树为最大堆，这个时候开始排序，排序规则：

  • 将堆顶元素和尾元素交换
  • 交换后重新调整元素的位置，使之重新变成二叉堆

image-20210804234843626

代码实现

public class HeapSort {

    public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};

    public static int[] sort(int[] array) {
        //数组的长度
        int length = array.length;
        if (length < 2) return array;
        //首先构建一个最大堆
        buildMaxHeap(array);
        //调整为最大堆之后，顶元素为最大元素并与微元素交换
        while (length > 0) {//当lenth <= 0时，说明已经到堆顶
            //交换
            swap(array, 0, length - 1);
            length--;//交换之后相当于把树中的最大值弹出去了，所以要--
            //交换之后从上往下调整使之成为最大堆
            adjustHeap(array, 0, length);
        }
        return array;
    }

    //对元素组构建为一个对应数组的最大堆
    private static void buildMaxHeap(int[] array) {
        //在之前的分析可知，最大堆的构建是从最后一个非叶子节点开始，从下往上，从右往左调整
        //最后一个非叶子节点的位置为：array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //调整使之成为最大堆
            adjustHeap(array, i, array.length);
        }
    }

    /**
     * 调整
     * @param parent 最后一个非叶子节点
     * @param length 数组的长度
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //定义最大值的索引
        int maxIndex = parent;
        //parent为对应元素的位置（数组的索引）
        int left = 2 * parent + 1;//左子节点对应元素的位置
        int right = 2 * (parent + 1);//右子节点对应元素的位置
        //判断是否有子节点，再比较父节点和左右子节点的大小
        //因为parent最后一个非叶子节点，所以如果有左右子节点则节点的位置都小于数组的长度
        if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
            maxIndex = left;
        }
        if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
            maxIndex = right;
        }
        //maxIndex为父节点，若发生改变则说明不是最大节点，需要交换
        if (maxIndex != parent) {
            swap(array, maxIndex, parent);
            //交换之后递归再次调整比较
            adjustHeap(array, maxIndex, length);
        }
    }

    //交换
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

堆的时间复杂度是 O(nlogn)

参考：堆排序的时间复杂度分析

算法稳定性

堆的结构为，对于位置为 k 的节点，其子节点的位置分别为，左子节点 = 2k + 1，右子节点 = 2(k + 1)，最大堆要求父节点大于等于其2个子节点，最小堆要求父节点小于等于其2个子节点。

在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(最大堆)或者最小(最大堆)，这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1，n/2-2，… 1 这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

参考：排序的稳定性

思考

对于快速排序来说，其平均复杂度为O(nlogn)，堆排序也是O(nlogn)，怎么选择？如下题：

leetcode：数组中的第K个最大元素

此题的意思是对于一个无序数组，经过排序后的第 k 个最大的元素。

我们知道快速排序是需要对整个数组进行排序，这样才能取出第 k 个最大的元素。

如果使用堆排序，且是最大堆的方式，则第k次循环即可找出第 k 个最大的元素，并不需要吧整个数组排序。

所以对于怎么选择的问题，要看具体的场景，或者是两者都可。

计数排序

一种非比较排序。计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。

如果一个数组里所有元素都是整数，而且都在0-k以内。对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

如给定一个0~5范围内的数组[2,5,3,0,2,3,0,3]，对于元素5为其中最大的元素，创建一个大小为（5-0+1 = 6）的计数数组，如果原数组中的值对应计数数组的下标，则下标对应计数数组的值加1。

image-20210806112939098

问题

上面是通过数组的最大值来确定计数数组的长度的，但如果需要对学生的成绩进行排序，如学生成绩为：[95,93,92,94,92,93,95,90]，如果按照上面的方法来处理，则需要一个大小为100的数组，但是可以看到其中的最小值为90，那也就是说前面 0~89 的位置都没有数据存放，造成了资源浪费。

如果我们知道了数组的最大值和最小值，则计数数组的大小为（最大值 – 最小值 + 1），如上面数组的最大值为99，最小值为90，则定义计数数组的大小为（95 – 90 + 1 = 6）。并且索引分别对应原数组9095的值。我们把090的范围用一个偏移量来表示，即最小值90就是这个偏移量。

image-20210806121018728

代码实现

public class CountSort {

    public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3};
    public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90};

    //优化前
    private static int[] sort(int[] array) {
        if (array.length < 2) return array;
        //找出数组的最大值
        int max = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
        }
        //初始化一个计数数组且值为0
        int[] countArray = new int[max + 1];
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }
        //填充计数数组
        for (int temp : array) {
            countArray[temp]++;
        }
        int o_index = 0;//原数组下标
        int n_index = 0;//计数数组下标
        while (o_index < array.length) {
            //只要计数数组的下标不为0，就将计数数组的值从新写回原数组
            if (countArray[n_index] != 0) {
                array[o_index] = n_index;//计数数组下标对应元素组的值
                countArray[n_index]--;//计数数组的值要-1
                o_index++;
            } else {
                n_index++;//上一个索引的值为0后开始下一个
            }
        }
        return array;
    }

    //优化后
    private static int[] sort2(int[] array) {
        if (array.length < 2) return array;
        //找出数组中的最大值和最小值
        int min = array[0], max = array[0];
        for (int i : array) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //定义一个偏移量,即最小值前面0~min的范围,这里直接用一个负数来表示
        int bias = 0 - min;
        //初始化一个计数数组且值为0
        int[] countArray = new int[max - min + 1];
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }
        for (int temp : array) {
            countArray[temp + bias]++;
        }
        //填充计数数组
        int o_index = 0;//原数组下标
        int n_index = 0;//计数数组下标
        while (o_index < array.length) {
            if (countArray[n_index] != 0) {
                array[o_index] = n_index - bias;
                countArray[n_index]--;
                o_index++;
            } else {
                n_index++;
            }
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
        System.out.println("=================优化排序====================");
        print(ARRAY2);
        System.out.println("============================================");
        print(sort2(ARRAY2));
    }
}

时间复杂度

很明显，在排序过程中，我们至少遍历了三次原始数组，一次计数数组，所以它的复杂度为Ο(n+m)。因此，计数排序比任何排序都要块，这是一种牺牲空间换取时间的做法，因为排序过程中需要用一个计数数组来存元素组的出现次数。

算法稳定性

在新建的计数数组中记录原始数组中每个元素的数量，如果原始数组有相同的元素，则在输出时，无法保证元素原来的排序，是一种不稳定的排序算法。

桶排序

桶排序是计数排序的升级，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过函数的某种映射关系，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序），最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

image-20210808133137559

代码实现

  1. 找出数组中的最大值max和最小值min，可以确定出数组所在范围min~max

  2. 根据数据范围确定桶的数量

    • 若桶的数量太少，则桶排序失效
    • 若桶的数量太多，则有的桶可能，没有数据造成空间浪费

    所以桶的数量由我们自己来确定，但尽量让元素平均分布到每一个桶里，这里提供一个方式

    (最大值 - 最小值)/每个桶所能放置多少个不同数值+1

  3. 确定桶的区间，一般是按照(最大值 - 最小值)/桶的数量来划分的，且左闭右开

public class BucketSort {

    public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};

    /**
     * @param bucketSize 作为每个桶所能放置多少个不同数值,即数值的类型
     *                   例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，
     *                   但是容量不限，即可以存放100个3
     */
    public static List<Integer> sort(List<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        //获取桶的数量
        int bucketCount = (max - min) / bucketSize + 1;
        //构建桶，初始化
        List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        List<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<>());
        }
        //将原数组的数据分配到桶中
        for (int i = 0; i < array.size(); i++) {
            //区间范围
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }

        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {
                for (int j = 0; j < bucketArr.get(i).size(); j++)
                    resultArr.add(bucketArr.get(i).get(j));
            } else {
                if (bucketCount == 1)
                    bucketSize--;
                //对桶中的数据再次用桶进行排序
                List<Integer> temp = sort(bucketArr.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++)
                    resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }

    public static void print(List<Integer> array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
        System.out.println("============================================");
        print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
    }
}

时间复杂度

桶排序算法遍历了2次原始数组，运算量为2N，最后，遍历桶输出排序结果的运算量为N，初始化桶的运算量为M。

对桶进行排序，不同的排序算法算法复杂度不同，冒泡排序算法复杂度为O(N^2)，堆排序、归并排序算法复杂度为O(NlogN)，我们以排序算法复杂度为O(NlogN)进行计算，运算量为N/M * log(N/M) * M

最终的运算量为3N+M+N/M * log(N/M) * M，即3N+M+N(logN-logM)，去掉系数，时间复杂度为O(N+M+N(logN-logM))

参考：桶排序算法详解

算法稳定性

桶排序算法在对每个桶进行排序时，若选择稳定的排序算法，则排序后，相同元素的位置不会发生改变，所以桶排序算法是一种稳定的排序算法。

基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。

基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序有两种方法：

  • MSD 从高位开始进行排序
  • LSD 从低位开始进行排序

对于大小范围为0~9的数的组合（若是两位数，就是个位数和十位数的组合），于是可以准备十个桶，然后放到对应的桶里，然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

image-20210809173152835

代码实现

public class RadixSort {

    public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};

    public static int[] sort(int[] array) {
        if (array.length < 2) return array;
        //根据最大值算出位数
        int max = array[0];
        for (int temp : array) {
            if (temp > max) {
                max = temp;
            }
        }
        //算出位数digit
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        //创建桶并初始化
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<>());
        }
        //按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，每一轮排序都基于上轮排序后的结果
        int mold = 10;//取模运算
        int div = 1;//获取对应位数的值
        for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                //获取个位/十位/百位......
                int num = (array[j] % mold) / div;
                //把数据放入到对应的桶里
                bucket.get(num).add(array[j]);
            }
            //把桶中的数据重新写回去，并把桶的元素清空，开始第二轮排序
            int index = 0;
            for (int k = 0; k < bucket.size(); k++) {
                //桶中对应的数据
                ArrayList<Integer> list = bucket.get(k);
                for (int m = 0; m < list.size(); m++) {
                    array[index++] = list.get(m);
                }
                //清除桶
                bucket.get(k).clear();
            }
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

时间复杂度

计数排序算法的时间复杂度是O(N+M)，基数排序算法执行了k次计数排序，所以基数排序算法的时间复杂度为O(K(N+M))。

算法稳定性

从上面的分析可以看出，相同元素会按照顺序放进固定的桶内，取出的时候也是按照顺序取出来的，所以基数排序算法是一种稳定的排序算法。

基数排序 vs 桶排序 vs 计数排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异

  • 基数排序：根据每一位的关键字来分配桶
  • 桶排序：存储一定范围的值
  • 计数排序：每个桶只存储一个类型值，但是数量不限

image-20210810001026742

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » 十大排序算法

wen 普通

分享到：

相关推荐

apk分析仪

功能 目前提取了APK内： 所有弦 所有网址 所有ip 可能是hash值的字符串 存在的敏感词（如oss.aliyun） 可能是accessKey的值

Go单元测试实践

　　单元测试通常用来在日常开发中检查代码中存在的问题，是提升代码质量一种有效手段。在保证代码功能没有问题的同时，可以得到预期结果。Golang有许多优秀的框架支持UT，下面列举日常开发中不同框架对应的UT情况，以便后来人...