1. 经典排序算法

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	⭕
选择排序	O(n²)	O(n²)	O(n²)	O(1)	❌
插入排序	O(n²)	O(n)	O(n²)	O(1)	⭕
希尔排序	O(n㏒n)	O(n㏒²n)	O(n㏒²n)	O(1)	❌
归并排序	O(n㏒n)	O(n㏒n)	O(n㏒n)	O(n)	⭕
快速排序	O(n㏒n)	O(n㏒n)	O(n²)	O(㏒n)	❌
堆排序	O(n㏒n)	O(n㏒n)	O(n㏒n)	O(1)	❌
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	⭕
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	⭕
基数排序	O(n × k)	O(n × k)	O(n × k)	O(n + k)	⭕

稳定性： 假设 a=1, b=4, c=2, d=2, e=5，按从小到大排序后，有两种正确结果：

a c d b e ：c 和 d 等值，原数组中 c 在前 d 在后，排序后也是 c 在前 d 在后，因此排序稳定。
a d c b e ：c 和 d 等值，原数组中 c 在前 d 在后，排序后却是 d 在前 c 在后，因此排序不稳定。

以下排序算法都是以数组从小到大进行排序进行演示

2. 选择排序

无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。

【算法步骤】

从未排序序列中找到最小元素，存放到排序序列的起始位置。
从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
重复执行步骤2，直到所有元素均排序完毕。

【动图演示】

【代码实现】

public class SelectionSort {
    public void sort(int[] sourceArray) {
		if (sourceArray.length <= 1) return;
        for (int i = 0; i < sourceArray.length-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < sourceArray.length; j++) {
                // 记录目前能找到的最小值元素的下标
                if (sourceArray[j] < sourceArray[minIndex]) minIndex = j;
            }

            if (i == minIndex) continue;
            // 将找到的最小值和i位置所在的值进行交换
            int tmp = sourceArray[i];
            sourceArray[i] = sourceArray[minIndex];
            sourceArray[minIndex] = tmp;
        }
    }
}
复制代码

【算法分析】

时间复杂度：算法共迭代 n-1 轮，每一轮选出最小值再交换到左侧的时间复杂度是 O(n)，所以时间复杂度是 O(n²)。

空间复杂度：算法是原地排序，并没有利用到额外的数据结构，所以空间复杂度是 O(1)。

稳定性：不稳定。当数列包含多个值相等的元素时，选择排序有可能打乱它们的原有顺序。绿色的 5 原本排在橙色的 5 之前，但是随着第一轮元素 3 和绿色 5 的交换，使得后续操作中，绿色的 5 排在了橙色的 5 之后。

3. 插入排序

类似于整理扑克牌。工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

【算法步骤】

将全部待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从未排序序列中找到最左边的元素，将他的数值临时保存一份。
从已排序序列中从右往左，依次与临时元素比较，如果大于则向前覆盖，否则就将临时元素覆盖到空位。
重复执行步骤2,3，直到所有元素均排序完毕。

【动图演示】

【代码实现】

public class InsertionSort {

    public void sort(int[] sourceArray) {
        if (sourceArray.length <= 1) return;
        // 从索引为1的元素开始，从前往后遍历
        for (int i = 1; i < sourceArray.length; i++) {
            // 临时保存一份，减少交换次数
            int tmp = sourceArray[i];
            int j;
            // 从标记元素开始，从后往前遍历
            for (j = i; j > 0 && sourceArray[j - 1] > tmp; j--) {
                // 如果前一个 > 临时元素，则用前一个数据覆盖当前
                sourceArray[j] = sourceArray[j - 1];
            }
            if (i == j) continue;
            // 将临时元素插入到合适位置
            sourceArray[j] = tmp;
        }
    }
}
复制代码

【算法分析】

时间复杂度：算法共迭代n-1轮，每一轮比较赋值的时间复杂度是 O(n)，所以时间复杂度是 O(n²)。

空间复杂度：算法是原地排序，并没有利用到额外的数据结构，所以空间复杂度是 O(1)。

稳定性：稳定。

4. 归并排序

典型的分而治之思想，采用分治法的一个非常典型的应用。

归：自上而下的递归（需要注意递归深度导致栈溢出）。
并：自下而上的合并。

【算法步骤】

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复执行步骤 3 直到某一指针达到序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。

【动图演示】

【代码实现】

public class MergeSort {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        // 使用递归法
        mergeSort(array, 0, length - 1);

        // 使用迭代法
//        for (int i = 1; i <= length; i += i) {
//            for (int j = 0; j + i < length; j += i + i) {
//                // 对array的[j,j+i-1]区间和array的[j+i,j+i*2-1]区间进行归并
//                merge(array, j, j + i - 1, Math.min(j + i + i - 1, length - 1));
//            }
//        }
    }

    // 使用递归，对array的[l,r]区间进行归并排序
    private void mergeSort(int[] array, int l, int r) {
        if (l >= r) return;
        // 折半成两个小集合，分别进行递归
        int mid = l + (r - l) / 2;
        mergeSort(array, l, mid);
        mergeSort(array, mid + 1, r);
        // 如果左边集合的最大值都不超过右边集合的最小值，则数组已经有序，不必做操作
        if (array[mid] <= array[mid + 1]) return;
        // 把两个有序小集合，归并成一个大集合
        merge(array, l, mid, r);
    }

    // 将array的[l,m]和array的[m+1,r]两部分进行合并
    private void merge(int[] array, int l, int m, int r) {
        // 开辟临时大集合，并初始化为未排序的数组
        int[] tmpArray = Arrays.copyOfRange(array, l, r + 1);
        int p1 = l;     // 指针指向左边区间的第一个元素
        int p2 = m + 1; // 指针指向右边区间的第一个元素
        // 新一轮迭代，区间重新排序并放回原始数组
        for (int i = l; i <= r; i++) {
            if (p1 > m) {
                // p1越界，表示左边元素已经全部使用完毕，因此把右边集合放入大集合尾部
                array[i] = tmpArray[p2 - l];
                p2++;
            } else if (p2 > r) {
                // p2越界，表示右边元素已经全部使用完毕，因此把左边集合放入大集合尾部
                array[i] = tmpArray[p1 - l];
                p1++;
            } else if (tmpArray[p1 - l] < tmpArray[p2 - l]) {
                array[i] = tmpArray[p1 - l];
                p1++;
            } else {
                array[i] = tmpArray[p2 - l];
                p2++;
            }
        }
    }
}
复制代码

【算法分析】

时间复杂度：算法的递归深度是 ㏒n，每一轮排序的复杂度是 O(n)，所以时间复杂度是 O(n㏒n)。

空间复杂度：算法每一轮排序，都额外用到了相同大小的临时数据结构，所以空间复杂度是 O(n)。

稳定性：稳定。

5. 快速排序

典型的分而治之思想，采用分治法的一个非常典型的应用。与归并排序不同的是，归并排序是简单的二分；而快速排序在分割时会动态计算合适的分割点。

【算法步骤】

先从数列中取出一个数作为基准数。
遍历数列，将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。
再对左右区间各重复执行步骤1,2 ，直到某一指针达到序列尾。

【图示说明】

快速排序和冒泡排序一样，最基本的操作就是元素交换

private void swap(int[] array, int i1, int i2) {
    int tmp = array[i1];
    array[i1] = array[i2];
    array[i2] = tmp;
}
复制代码

5.1. 精简版（无优化）

【代码实现】

public class QuickSort {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        quickSort(array, 0, array.length - 1);
    }

    // 对array的[l,r]区间进行快速排序
    private void quickSort(int[] array, int l, int r) {
        if (l >= r) return;
        // 找到中间的分割点位置
        int p = partition(array, l, r);
        // 对左右两个子区间递归进行快速排序
        quickSort(array, l, p - 1);
        quickSort(array, p + 1, r);
    }

    // 对array的[l,r]区间计算合适的标定位置
    private int partition(int[] array, int l, int r) {
        // 选定最左边的元素作为基准元素
        int v = array[l];
        // j满足array[l+1,j] < v 并且 array[j+1,r] > v
        int j = l;
        // 遍历数组的[l,r]区间
        for (int i = l + 1; i <= r; i++) {
            // 从左边第2个元素开始做比较
            if (array[i] <= v) {
                // 如果当前值 <= 基准元素
                // 则将当前值与j的下一个位置交换，并同时向右移动i指针和j指针
                swap(array, ++j, i);
            }
        }
        // 最后交换基准元素与j指针的元素，该位置就是最终排好序的正确位置
        swap(array, l, j);
        // 返回分割点的索引值
        return j;
    }
}
复制代码

【算法分析】

对于完全随机的数据而言，快速排序要比归并排序快。

随机数组 length：1000000，max：1000000

【MergeSort】293.772 ms

【QuickSort】180.077 ms

5.2. 基础版（随机基准元素）

如果给定的原始数据近乎有序（极端情况下为数组已经有序），由于每次都固定以最左边的第一个元素作为基准元素，则分割后左区间将会消失，只有一个右区间，导致每一轮递归只能排好一个元素，因此 O(n㏒n) 的算法将会退化成 O(n²) 的算法。

近乎有序的随机数组 length：1000000，max：1000000，swapTimes：10

【MergeSort】75.397 ms

【QuickSort】84.493 s 栈溢出，且耗时是归并排序的1000倍

【解决办法】

在选择基准元素时，采用随机原则，避免退化成 O(n²) 。

【代码实现】

public class QuickSort {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        quickSort(array, 0, array.length - 1);
    }

    // 对array的[l,r]区间进行快速排序
    private void quickSort(int[] array, int l, int r) {
        if (l >= r) return;

        // 找到中间的分割点位置
        int p = partition(array, l, r);
        // 对左右两个子区间递归进行快速排序
        quickSort(array, l, p - 1);
        quickSort(array, p + 1, r);
    }

    // 对array的[l,r]区间计算合适的标定位置
    private int partition(int[] array, int l, int r) {
        // ?新增2行代码。随机选择一个元素作为基准元素，并和最左边元素交换位置
        int baseIndex = (int) (Math.random() * (r - l + 1) + l);
        swap(array, l, baseIndex);
        // 选定最左边的元素作为基准元素
        final int v = array[l];
        // j满足array[l+1,j] < v 并且 array[j+1,r] > v
        int j = l;
        // 遍历数组的[l,r]区间
        for (int i = l + 1; i <= r; i++) {
            // 从左边第2个元素开始做比较
            if (array[i] <= v) {
                // 如果当前值 <= 基准元素
                // 则将当前值与j的下一个位置交换，并同时向右移动i指针和j指针
                swap(array, ++j, i);
            }
        }
        // 最后交换基准元素与j指针的元素，该位置就是最终排好序的正确位置
        swap(array, l, j);
        // 返回分割点的索引值
        return j;
    }
}
复制代码

【算法分析】

对于近乎有序的数据而言，此项优化已经好了太多。但是仍然要比归并排序慢，这是因为归并排序里面，当两个区间已经有序时，则不需要合并。

近乎有序的随机数组 length：1000000，max：1000000，swapTimes：10

【MergeSort】54.817 ms

【QuickSort】102.640 ms

5.3. 标准版（双路快速排序）

如果给定的原始数据有大量的重复数据（极端情况下为数组元素完全相等），由于每次和基准元素做比较时，如果相等也会和左边的元素进行交换（无论是放到左边区间还是右边区间都是一样的问题），则分割后左右两个区间会很不平衡，因此 O(n㏒n) 的算法将会退化成 O(n²) 的算法。

随机数组 length：1000000，max：10

【MergeSort】224.483 ms

【QuickSort】39.529 s

【解决办法】

从两个方向同时向中间遍历数组，把和基准元素相等的元素，平均分散到两个区间，防止左右两个区间不平衡，避免退化成 O(n²) 。

【关键步骤】

i 指针从前往后遍历，如果当前元素 < 基准元素，则指针后移，直到 >= 基准元素。
j 指针从后往前遍历，如果当前元素 > 基准元素，则指针前移，直到 <= 基准元素。
如果两指针相遇了，则遍历结束；否则交换两个指针指向的元素，同时再移动两个指针。
重复执行步骤1,2,3，直到遍历完一轮。

【代码实现】

public class QuickSort {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        quickSort(array, 0, array.length - 1);
    }

    // 对array的[l,r]区间进行快速排序
    private void quickSort(int[] array, int l, int r) {
        if (l >= r) return;

        // 找到中间的分割点位置
        int p = partition(array, l, r);
        // 对左右两个子区间递归进行快速排序
        quickSort(array, l, p - 1);
        quickSort(array, p + 1, r);
    }

    // 对array的[l,r]区间计算合适的标定位置
    private int partition(int[] array, int l, int r) {
        // 随机选择一个元素作为基准元素，并和最左边元素交换位置
        int baseIndex = (int) (Math.random() * (r - l + 1) + l);
        swap(array, l, baseIndex);
        // 选定最左边的元素作为基准元素
        final int v = array[l];
        // i满足array[l+1,i-1] <= v
        int i = l + 1;  // 因为l位置已经被基准元素占用了，所以要+1
        // j满足array[j+1,r] >= v
        int j = r;

        while (true) {
            // i指针从前往后遍历，如果当前元素<基准元素，则指针后移，直到>=基准元素
            while (i <= r && array[i] < v) i++;
            // j指针从后往前遍历，如果当前元素>基准元素，则指针前移，直到<=基准元素
            while (j >= l + 1 && array[j] > v) j--;
            // 如果两个指针相遇了，则遍历结束
            if (i >= j) break;
            // 交换两个指针指向的元素，同时移动指针
            swap(array, i++, j--);
        }
        // 最后交换基准元素与j指针的元素，该位置就是最终排好序的正确位置
        swap(array, l, j);
        // 返回分割点的索引值
        return j;
    }
}
复制代码

【算法分析】

对于大量的重复数据而言，此项优化已经好了太多。有时甚至比归并排序还好。

随机数组 length：1000000，max：10

【MergeSort】217.552 ms

【QuickSort】158.082 ms

5.4. 高级版（三路快速排序）

同样是为了优化大量重复数据时，时间效率退化成 O(n²) 的问题。

【关键步骤】

i 指针从前往后遍历，并与基准元素比较：

如果当前元素 = 基准元素，则只需要右移 i 指针。
如果当前元素 < 基准元素，则交换 lt + 1 和 i 两个指针指向的元素，然后右移 i 指针和 lt 指针。
如果当前元素 > 基准元素，则交换 gt - 1 和 i 两个指针指向的元素，然后左移 gt 指针。

重复执行步骤1，直到 i 指针和 gt 指针相遇，则一轮遍历结束。

【代码实现】

public class QuickSort {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        quickSort3Ways(array, 0, array.length - 1);
    }

    // 对array的[l,r]区间进行3路快速排序
    private void quickSort3Ways(int[] array, int l, int r) {
        // 递归终止条件
        if (l >= r) return;

        // 随机选择一个元素作为基准元素，并和最左边元素交换位置
        int baseIndex = (int) (Math.random() * (r - l + 1) + l);
        swap(array, l, baseIndex);

        // 选定最左边的元素作为基准元素
        final int v = array[l];
        // lt满足array[l+1,lt] < v
        int lt = l;
        // gt满足array[gt,r] > v
        int gt = r + 1;
        // i满足array[lt+1,i-1] == v
        int i = l + 1;
        // 直到i和gt相遇，一轮遍历结束
        while (i < gt) {
            if (array[i] < v) {
                // 如果当前元素<基准元素，则交换lt+1和i两个指针指向的元素，然后右移i指针和lt指针
                swap(array, ++lt, i++);
            } else if (array[i] > v) {
                // 如果当前元素>基准元素，则交换gt-1和i两个指针指向的元素，然后左移gt指针
                swap(array, --gt, i);
            } else {
                // 如果当前元素=基准元素，则只需要右移i指针
                i++;
            }
        }
        // 最后交换基准元素和左区间的最后一个元素
        swap(array, l, lt);
        // 递归排序其他两个区间
        quickSort3Ways(array, l, lt - 1);
        quickSort3Ways(array, gt, r);
    }
}
复制代码

【算法分析】

时间复杂度：平均时间复杂度是 O(n㏒n)；最差的情况就是每一次取到的元素就是数组中最大值或最小值，就退化成冒泡排序了 O(n²) ，但由于是随机选取基准元素，使得出现最差情况的概率大大降低；因此说快速排序的时间复杂度是 O(n㏒n)。

空间复杂度：算法是原地排序，所以空间复杂度是 O(1)，但是由于是递归调用，需要保存一些数据，因此空间复杂度是 O(㏒n)。

稳定性：不稳定。

对于大量的重复数据而言，性能比标准快速排序和归并排序都要好。

随机数组 length：1000000，max：10

【MergeSort】172.234 ms

【QuickSort】118.999 ms

【QuickSort3Ways】39.054 ms

一般情况下，性能差不多。

随机数组 length：1000000，max：1000000

【MergeSort】255.119 ms

【QuickSort】198.002 ms

【QuickSort3Ways】250.287 ms

近乎有序的数据。

近乎有序的随机数组 length：1000000，max：1000000，swapTimes：100

【MergeSort】267.889 ms

【QuickSort】148.813 ms

【QuickSort3Ways】164.961 ms

5.5. 迭代版（非递归实现）

绝大多数递归实现的问题，都能用迭代+栈的实现方式来代替：代码递归的过程本身就是一个函数栈的入栈和出栈，因此，把递归转化成一个栈，然后在栈中存储每一次方法调用的参数即可。

【关键步骤】

创建一个 Stack 对象，用于模拟递归的过程，保存每次调用的顺序。
自定义一个 Frame 类，每个栈帧用一个 Frame 对象表示，存储每次调用的参数列表。
先将第一次完整的调用入栈。
然后循环取出栈中的栈帧，直到栈为空。

【代码实现】

public class QuickSortIteration {

    public void sort(int[] array) {
        final int length = array.length;
        if (length < 2) return;

        quickSortIteration(array, 0, array.length - 1);
    }

    // 对array的[l,r]区间进行快速排序
    // 使用迭代实现
    private void quickSortIteration(int[] array, int l, int r) {
        if (l >= r) return;

        // 用一个Stack来代替递归的函数栈
        Stack<Frame> quickSortStack = new Stack<>();
        // 使用Frame表示栈帧，并将首次调用入栈
        Frame firstFrame = new Frame(l, r);
        quickSortStack.push(firstFrame);
        // 循环结束条件：栈为空时结束
        while (!quickSortStack.isEmpty()) {
            // 取出栈顶元素
            Frame frame = quickSortStack.pop();
            // 获取方法调用参数，找到基准元素的位置
            int p = partition2(array, frame.left, frame.right);
            // 将左右两部分区间调用入栈
            if (frame.left < p - 1) {
                quickSortStack.push(new Frame(frame.left, p - 1));
            }
            if (frame.right > p + 1) {
                quickSortStack.push(new Frame(p + 1, frame.right));
            }
        }
    }

    // 对array的[l,r]区间计算合适的标定位置
    // 双指针相向扫描
    private int partition2(int[] array, int l, int r) {
        // 随机选择一个元素作为基准元素，并和最左边元素交换位置
        int baseIndex = (int) (Math.random() * (r - l + 1) + l);
        swap(array, l, baseIndex);
        // 选定最左边的元素作为基准元素
        final int v = array[l];
        // i满足array[l+1,i-1] <= v
        int i = l + 1;  // 因为l位置已经被基准元素占用了，所以要+1
        // j满足array[j+1,r] >= v
        int j = r;

        while (true) {
            // i指针从前往后遍历，如果当前元素<基准元素，则指针后移，直到>=基准元素
            while (i <= r && array[i] < v) i++;
            // j指针从后往前遍历，如果当前元素>基准元素，则指针前移，直到<=基准元素
            while (j >= l + 1 && array[j] > v) j--;
            // 如果两个指针相遇了，则遍历结束
            if (i >= j) break;
            // 交换两个指针指向的元素，同时移动指针
            swap(array, i++, j--);
        }
        // 最后交换基准元素与j指针的元素，该位置就是最终排好序的正确位置
        swap(array, l, j);
        // 返回分割点的索引值
        return j;
    }

    // 模拟栈帧，保存方法调用的参数列表
    private static class Frame {
        public int left;
        public int right;

        public Frame(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
}
复制代码

【算法分析】

迭代实现的快速排序和递归实现的快速排序性能上差别不大。

随机数组 length：1000000，max：1000000

【MergeSort】255.983 ms

【QuickSort】210.200 ms

【QuickSort3Ways】183.901 ms

【QuickSortIteration】257.451 ms

6. 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

6.1. 二叉堆概念

漫画：什么是二叉堆？

二叉堆是一种特殊的堆，是完全二叉树或近似完全二叉树。二叉堆有两种：

最大堆：父结点 >= 子结点，堆顶是整个堆中的最大元素。
最小堆：父结点 <= 子结点，堆顶是整个堆中的最小元素。

【适用说明】

若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n²)，但是堆可以提高入队和出队的效率。

数据结构	入队	出队
普通数组	O(1)	O(n)
顺序数组	O(n)	O(1)
堆	O(㏒n)	O(㏒n)

【插入结点】

在完全二叉树的最后一个位置插入新的结点 M。
让 M 结点与其父结点比较：
- 如果小于（最小堆）或大于（最大堆）父结点，则与父结点交换位置。
- 如果相等或者没有父结点，则该位置就是 M 结点的最终位置。
重复执行步骤2，直到 M 结点找到最终位置。

【删除结点】

删除完全二叉树的根结点（堆顶结点），并把最后一个位置的结点 M 移动到堆顶。
让 M 结点与其子结点比较：
- 如果小于（最大堆）或大于（最小堆）其中一个子结点，则与该子结点交换位置。
- 如果小于（最大堆）或大于（最小堆）两个子结点，则与较大的（最大堆）或较小的（最小堆）子结点交换位置。
- 如果相等或者没有子结点，则该位置就是 M 结点的最终位置。
重复执行步骤2，直到 M 结点找到最终位置。

【构建二叉堆】

就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子结点依次下沉。

从最后一个非叶子结点开始。
让该结点与其子结点比较：
- 如果小于（最大堆）或大于（最小堆）其中一个子结点，则与该子结点交换位置。
- 如果小于（最大堆）或大于（最小堆）两个子结点，则与较大的（最大堆）或较小的（最小堆）子结点交换位置。
- 如果相等或者没有子结点，则该位置就是该结点的临时位置。
重复执行步骤2，直到遍历完全部非叶子结点。

【代码实现】

二叉堆虽然是一棵完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，即数组。

因此，假设一个结点的索引是 parent，结点总数是 count 则：

其父结点的索引就是 (parent-1)÷2
左子结点的索引就是 2×parent+1
右子结点的索引就是 2×parent+2
最后一个非叶子结点的索引 (count-1)÷2

public class MaxHeap {

    private final int[] data;   // 数据存储结构
    private final int capacity; // 额定容量
    private int count = 0;      // 实时数量

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.data = new int[capacity];
    }

    public MaxHeap(int[] initData) {
        this.capacity = initData.length;
        this.data = Arrays.copyOf(initData, initData.length);
        this.count = initData.length;
        // 最后一个非叶子结点：(count - 1) / 2
        // 从最后一个非叶子结点开始下沉
        for (int i = (this.count - 1) / 2; i >= 0; i--) {
            shiftDown(i);
        }
    }

    // 插入一个新元素
    public void insert(int element) {
        if (this.count >= this.capacity) {
            throw new IllegalStateException("The maxHeap is full");
        }

        this.count++;
        // 先把新增的元素放到最后一个位置
        this.data[this.count - 1] = element;
        // 对当前最后一个元素执行上浮操作
        shiftUp(this.count - 1);
    }

    // 弹出堆顶元素
    public int popMax() {
        if (this.count == 0) {
            throw new IllegalStateException("The maxHeap is empty");
        }

        // 先暂存堆顶元素
        final int root = data[0];
        // 把最后一个位置的元素移动到堆顶
        data[0] = data[--count];
        // 对当前堆顶元素执行下沉操作
        shiftDown(0);
        return root;
    }

    // 元素上浮操作
    private void shiftUp(int index) {
        // 父结点：(index - 1) / 2
        // 循环条件：当前结点有父结点 且 当前结点>父结点
        while (index > 0 && this.data[index] > this.data[(index - 1) / 2]) {
            // 与父结点交换位置
            swap(this.data, (index - 1) / 2, index);
            // 更新当前结点的新索引值
            index = (index - 1) / 2;
        }
    }

    // 元素下沉操作
    private void shiftDown(int index) {
        // 左子结点：2 * index + 1
        // 右子结点：2 * index + 2
        // 循环条件：当前结点有子结点（完全二叉树没有左子结点，就更不可能有右子结点）
        while (2 * index + 1 <= this.count) {
            int j = 2 * index + 1;  // 先默认与左子结点交换
            if (2 * index + 2 < this.count && data[2 * index + 1] < data[2 * index + 2]) {
                // 如果有右子结点，且右子结点>左子结点
                j = 2 * index + 2;
            }
            if (data[index] >= data[j]) break;

            // 如果当前结点<待交换的子结点，则交换位置并更新索引值
            swap(data, index, j);
            index = j;
        }
    }

    private void swap(int[] array, int i1, int i2) {
        int tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }
}
复制代码

6.2. 简单版（利用最大堆）

最大堆每次pop堆顶元素时，都是剩下元素中最大的元素，因此pop过程天然就是有序的。

【代码实现1】

public class HeapSort1 {

    public void sort(int[] array) {
        MaxHeap maxHeap = new MaxHeap(array.length);
        // 将元素一个一个添加到最大堆
        for (int j : array) {
            maxHeap.insert(j);
        }
        // 循环从最大堆中取出堆顶元素
        for (int i = array.length - 1; i >= 0; i--) {
            array[i] = maxHeap.popMax();
        }
    }
}
复制代码

【代码实现2】

public class HeapSort2 {

    public void sort(int[] array) {
        // 将全部元素一次性添加到堆，由最大堆内部进行整理
        MaxHeap maxHeap = new MaxHeap(array);
        // 循环从最大堆中取出堆顶元素
        for (int i = array.length - 1; i >= 0; i--) {
            array[i] = maxHeap.popMax();
        }
    }
}
复制代码

【算法分析】

方法1：每次向最大堆中添加一个元素，使其每次都自行整理，时间复杂度是 O(n㏒n)。
方法2：向最大堆一次性添加全部元素，使其自行整理，时间复杂度是 O(n)。
综上，这种方法的堆排序时间复杂度是 O(n㏒n)，由于需要复制一遍原始数组，因此空间复杂度是 O(n)。

随机数组 length：1000000，max：1000000

【MergeSort】319.844 ms

【QuickSort】217.748 ms

【QuickSort3Ways】245.090 ms

【QuickSortIteration】305.352 ms

【HeapSort1】280.493 ms

【HeapSort2】169.068 ms

6.3. 标准版（原地堆排序）

直接把原始数组作为堆的存储结构，则不需要拷贝一份数组，因此空间复杂度可以降低至 O(1)。

【算法图示】

【代码实现】

public class HeapSort {

    public void sort(int[] array) {
        // 从最后一个非叶子结点开始下沉
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
        // 结束后，原始数据已经按照最大堆排列好了
        // 循环取出堆顶元素，每取出一个，则重新执行一遍下沉
        for (int count = array.length - 1; count > 0; count--) {
            swap(array, 0, count);
            shiftDown(array, 0, count);
        }
    }

    // 元素下沉操作
    private void shiftDown(int[] array, int index, int count) {
        // 左子结点：2 * index + 1
        // 右子结点：2 * index + 2
        // 循环条件：当前结点有子结点（完全二叉树没有左子结点，就更不可能有右子结点）
        while (2 * index + 1 < count) {
            int j = 2 * index + 1;  // 先默认与左子结点交换
            if (j + 1 < count && array[j] < array[j + 1]) {
                // 如果有右子结点，且右子结点>左子结点
                j = j + 1;
            }
            if (array[index] >= array[j]) break;

            // 如果当前结点<待交换的子结点，则交换位置并更新索引值
            swap(array, index, j);
            index = j;
        }
    }
}
复制代码

【算法分析】

时间复杂度：无序数组构建成二叉堆，下沉调整的最坏时间复杂度=二叉堆的高度，即 O(㏒n)；循环取出堆顶元素，并再次下沉，时间复杂度是 O(n㏒n)，两步骤综合，时间复杂度是 O(n㏒n)。

空间复杂度：算法是原地排序，并没有利用到额外的数据结构，所以空间复杂度是 O(1)。

稳定性：不稳定。

随机数组 length：1000000，max：1000000

【MergeSort】272.868 ms

【QuickSort】237.082 ms

【QuickSort3Ways】189.954 ms

【QuickSortIteration】232.458 ms

【HeapSort】208.720 ms

文章版权归作者所有，未经允许请勿转载。

THE END

阅读