排序总结 | Depeng's Blog

排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率，有时候排序的稳定性还是实际问题中必须考虑的，这篇博客对常见的排序算法进行整理，包括：选择排序、插入排序、希尔排序、冒泡排序、鸡尾酒排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序(代码略)。

十大经典排序算法

比较和非比较排序

比较排序

常见的快速排序、归并排序、堆排序、冒泡排序等排序算法属于比较排序，在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

非比较排序

计数排序、基数排序、桶排序则属于非比较排序。因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。
非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所以一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

比较排序时间复杂度证明

比较排序的时间复杂度通常为O(n²)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。

比较排序时间复杂度为O(nlogn)的证明：

a1, a2, a3, ……, an数列的所有排序有n!种，所以满足要求的排序a1’, a2’, a3’, ……, an’（其中a1’<=a2’<=a3’……<=an’）的概率为1/n!。
基于输入元素的比较排序，每一次比较的返回不是0就是1，这恰好可以作为决策树的一个决策将一个事件分成两个分支。
比如冒泡排序时通过比较a1和a2两个数的大小，可以把序列分成a1, a2, ……, an与a2, a1, ……, an（气泡a2上升一个身位）两种不同的结果，因此比较排序也可以构造决策树。根节点代表原始序列a1, a2, a3, ……, an，所有叶子节点都是这个序列的重排（共有n!个，其中有一个就是我们排序的结果a1’, a2’, a3’, ……, an’）。
如果每次比较的结果都是等概率的话（恰好划分为概率空间相等的两个事件），那么二叉树就是高度平衡的，深度至少是log(n!)。

又因为：

n! < n^n ，两边取对数就得到log(n!) < nlog(n)，所以 log(n!) = O(nlogn)。
n! = n(n-1)(n-2)(n-3)…1 > (n/2)^(n/2) 两边取对数得到 log(n!) > (n/2)log(n/2) = Ω(nlogn)，所以 log(n!) = Ω(nlogn)。

因此log(n!)的增长速度与 nlogn 相同，即 log(n!) = Θ(nlogn)，这就是通用排序算法的最低时间复杂度为 O(nlogn) 的依据。

排序稳定性和复杂度

不稳定

选择排序（Selection Sort）— O(n²)

希尔排序（Shell Sort）— O(nlogn)

快速排序（Quick Sort）— O(nlogn) 平均时间， O(n²)最坏情况;对于大的、乱序串列一般认为是最快的已知排序。

堆排序（Heap Sort）— O(nlogn)

基数排序（Radix Sort）— O(n·k); 需要 O(n) 额外存储空间（K为特征个数）

稳定

插入排序（Insertion Sort）— O(n²)

冒泡排序（Bubble Sort） — O(n²)

归并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外存储空间

二叉树排序（Binary Tree Sort） — O(nlogn); 需要 O(n) 额外存储空间

计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外存储空间，k为序列中 Max-Min+1

桶排序（Bucket Sort）— O(n); 需要 O(k) 额外存储空间

10种排序的原理和实现(基数排序和二叉树排序暂无)

选择排序（Selection Sort）

选择排序的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

遍历数组，遍历到i时，a0, a1, …, ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。

选择排序实现部分

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < = 1) {
        return;
    }

    int currentMin;
    int currentMinIndex;

    for (int i = 0; i < arr.length - 1; i++) {
        //  找到最小值和最小值下标位置，在范围arr[i  ... arr.length-1]
        currentMin = arr[i];
        currentMinIndex = i;

        for (int j = i + 1; j < arr.length; j++) {
            if (currentMin > arr[j]) {
                currentMin = arr[j];
                currentMindIndex = j;
            }
        }

        if (currentMinIndex != i) {
            arr[currentMinIndex] = arr[i];
            arr[i] = currentMin;
        }
    }
}

插入排序（Insertion Sort）

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

遍历数组，遍历到i时，a0,a1…ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。

可见相等元素比较是，原来靠后的还是排在后边，所以插入排序是稳定的。
当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。

插入排序实现部分

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 插入arr[i]到已经排好序的子线性表arr[0 ... i-1]中
        int currentElement = arr[i];
        int k;

        for (k = i - 1; k >= 0 && arr[k] > currentElement; k--) {
            arr[k+1] = arr[k];
        }

        //  插入当前元素到arr[k+1]中
        arr[k + 1] = currentElement;
    }
}

希尔排序（Shell Sort）

希尔排序又叫缩小增量排序，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序是对插入排序的优化，基于以下两个认识：1.数据量较小时插入排序速度较快，因为n和n²差距很小；2.数据基本有序时插入排序效率很高，因为比较和移动的数据量少。

因此，希尔排序的基本思想是，将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

希尔排序的划分子序列不是像归并排序那种的二分，而是采用的叫做增量的技术，例如有十个元素的数组进行希尔排序，首先选择增量为10/2=5，此时第1个元素和第（1+5）个元素配对成子序列使用插入排序进行排序，第2和（2+5）个元素组成子序列，完成后增量继续减半为2，此时第1个元素、第（1+2）、第（1+4）、第（1+6）、第（1+8）个元素组成子序列进行插入排序。这种增量选择方法的好处是可以使数组整体均匀有序，尽可能的减少比较和移动的次数。
二分法中即使前一半数据有序，后一半中如果有比较小的数据，还是会造成大量的比较和移动，因此这种增量的方法和插入排序的配合更佳。

希尔排序的时间复杂度和增量的选择策略有关，上述增量方法造成希尔排序的不稳定性。

希尔排序实现部分

public static int[] shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
        // 对子序列插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int currentElement = arr[i];
            while (j - gap >= 0 && arr[j - gap] > currentElement) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = currentElement;
        }
    }
    return arr;
}

冒泡排序（Bubble Sort）

冒泡排序，重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的名字很形象，实际实现是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。这是最基本的冒泡排序，还可以进行一些优化。
优化一：如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个isSorted做标记，默认为true，如果发生交换则置为false，每轮结束时检测isSorted，如果为false则继续，如果为true则返回。
优化二：某一轮结束位置为j，但是这一轮的最后一次交换发生在lastExchangedIndex的位置，则lastExchangedIndex到j之间是排好序的，下一轮的结束点就不必是j–了，而直接到lastExchangedIndex即可。

优化一实现

public static void bubbleSort(int[] arr) {
    int tmp = 0;

    for (int i = 0; i < arr.length; i++) {
        boolean isSorted = true;

        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                isSorted = false;
            }
        }

        if (isSorted) {
            break;
        }
    }
}

优化二实现

public static void bubbleSort(int[] arr) {
    int tmp = 0;
    //记录最后一次交换的位置
    int lastExchangedIndex = 0;
    //无序数列的边界，每次比较只需要比到这里为止        
    int sortBorder = arr.length - 1;  

    for (int i = 0; i < arr.length; i++) {
        //有序标记，每一轮的初始是true
        boolean isSorted = true;    

        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;

                //把无序数列的边界更新为最后一次交换元素的位置
                lastExchangedIndex = j;
            }
        }
        sortBorder = lastExchangedIndex;

        if (isSorted) {
            break;
        }
    }
}

鸡尾酒排序（Cocktail Sort）

回顾冒泡排序的思想：
冒泡排序的每一个元素都可以像一个小气泡一样，根据自身大小，一点一点向着数组的一侧移动。算法的每一轮都是 从左到右比较元素，进行单向的位置交换。
那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是 双向的。

鸡尾酒排序代码实现

public static void cockTailSort(int[] arr) {
    int tmp = 0;

    int lastRightExchangedIndex = 0;    //记录右侧最后一次交换的位置
    int lastLeftExchangedIndex = 0;    //记录左侧最后一次交换的位置 

    //无序数列的右边界，每次比较只需要比到这里为止
    int rigthSortBorder = arr.length - 1;
    //无序数列的左边界，每次比较只需要比到这里为止
    int leftSortBorder = 0;

    for (int i = 0; i < arr.length / 2; i++) {
        boolean isSorted = true;
        //奇数轮，从左向右比较和交换
        for (int j = leftSortBorder; j < rigthSortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                isSorted = false;
                lastRightExchangedIndex = j;
            }
        }
        rigthSortBorder = lastRightExchangedIndex;
        if (isSorted) {
            break;
        }

        isSorted = true;
        //偶数轮，从右向左比较和交换
        for (int j = rigthSortBorder; j > leftSortBorder; j--) {
            if (arr[j] < arr[j - 1]) {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;

                isSorted = false;
                lastLeftExchangedIndex = j;
            }
        }
        leftSortBorder = lastLeftExchangedIndex;
        if (isSorted) {
            break;
        }
    }
}

归并排序（Merge Sort）

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

首先考虑下如何将二个有序数列合并。这个非常简单，只要从比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行 logn次，因此，总的时间复杂度为O(nlogn)。

归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。
归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。

归并排序实现

public static void mergeSort(int[] arr, int left, int right) {
    if (left == right) {
        return;
    } else {
        //  取中间的数进行拆分
        int mid = (left + right) / 2;
        //  左边的数不断进行拆分
        mergeSort(arr, left, mid);
        //  右边的数不断进行拆分
        mergeSort(arr, mid + 1, right);

        // 合并
        merge(arr, left, mid + 1, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] leftArray = new int[mid - left];
    int[] rightArray = new int[right - mid + 1];
    for (int i = left; i < mid; i++) {
        leftArray[i - left] = arr[i];
    }
    for (int i = mid; i <= right; i++) {
        rightArray[i - mid] = arr[i];
    }

    int i = 0, j = 0;
    int k = left;

    while (i < leftArray.length && j < rightArray.length) {
        if (leftArray[i] < rightArray[j]) {
            arr[k++] = leftArray[i++];
        } else {
            arr[k++] = rigthArray[j++];
        }
    }

    while (i < leftArray.length) {
        arr[k++] = leftArray[i++];
    }
    while (j < rightArray.length) {
        arr[k++] = rigthArray[j++];
    }
}

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。其中，最重要的partition主要有两种方法：
A.先把选定为pivot的元素放到最后，然后设定指针low和指针high，low指针左移，high指针右移，当两个指针相撞后停止移动。期间如果符合交换条件，两元素交换。最后把pivot元素放到中间。
B.类似冒泡排序的思路，把比pivot大的元素“往下沉”，把比pivot小的元素“往上浮”。
快速排序是目前被认为最好的一种内部排序方法。快速排序算法处理的最好情况指每次都是将待排序数列划分为均匀的两部分，通常认为快速排序的平均时间复杂度是O(nlogn)。

但是，快速排序的最差情况就是基本逆序或者基本有序的情况，那么此时快速排序将蜕化成冒泡排序，其时间复杂度为O(n^2)

快排实现（挖坑法）

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    //递归结束条件
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);

    // 用分治法递归数列两部分
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, startIndex + 1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第一个位置的元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;

    // 坑的位置，初始等于pivot的位置
    int index = startIndex;

    // 大循环左右指针重合或者指针交换时结束
    while (right >= left) {
        // right指针从右向左进行比较
        while (right >= left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        //left指针从左向右进行比较
        while (right >= left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    arr[index] = pivot;
    return index;
}

快排实现（指针交换法）

public static quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准信息
    int pivotIndex = partition(arr, startIndex, endIndex);
    //根据基准元素，分成两部分进行递归
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    // 取第一个元素作为基准元素
    int pivot = arr[startIndex];
    int left = startIndex;
    int right = endIndex;

    while (left != right) {
        // 控制right指针比较并左移
        while (left < right && arr[right] > pivot) {
            right--;
        }
        // 控制left指针比较并左移
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        // 交换left和right指向的元素
        if (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
    }
    // pivot和指针重合交换
    int tmp = arr[left];
    arr[left] = arr[startIndex];
    arr[startIndex] = tmp;

    return left;
}

单边循环法

public static void quickSort(int[] arr, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

private static int partition(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];
    int mark = startIndex;

    for (int i = startIndex + 1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            mark++;
            int tmp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = tmp;
        }
    }

    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

计数排序（Count Sort）

如果通过比较进行排序，那么复杂度的下界是O(nlogn)，但是如果数据本身有可以利用的特征，可以不通过比较进行排序，就能使时间复杂度降低到O(n)。

计数排序要求待排序的数组元素都是整数，有很多地方都要求是 0-K 的正整数，其实负整数也可以通过都加一个偏移量解决的。

计数排序的思想是，考虑待排序数组中的某一个元素a，如果数组中比a小的元素有s个，那么a在最终排好序的数组中的位置将会是s+1，如何知道比a小的元素有多少个，肯定不是通过比较去觉得，而是通过数字本身的属性，即累加数组中最小值到a之间的每个数字出现的次数（未出现则为0），而每个数字出现的次数可以通过扫描一遍数组获得。

计数排序的步骤：

1.找出待排序的数组中最大和最小的元素（计数数组C的长度为max-min+1，其中位置0存放min，依次填充到最后一个位置存放max）
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1（反向填充是为了保证稳定性）

计数排序适合数据分布集中的排序，如果数据太分散，会造成空间的大量浪费，假设数据为（1,2,3,1000000），这就需要1000000的额外空间，并且有大量的空间浪费和时间浪费。

计数排序实现

public static int[] countSort(int[] arr) {
    // 1. 得到数列的最大值和最小值，并计算出差值d
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int d = max - min;

    // 2. 创建统计数组并统计对应元素个数
    int[] countArray = new int[d + 1];
    for (int i = 0; i < arr.length; i++) {
        countArray[arr[i] - min]++;
    }
    // 3. 统计数组做变型，后面的元素等于前面的元素之和
    int sum = 0;
    for (int i = 0; i < countArray.length; i++) {
        sum += countArray[i];
        countArray[i] = sum;
    }
    // 4. 倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
    int[] sortedArray = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        //  arr[i]-min找到这个数在countArray中的位置
        int sumCount = countArray[arr[i] - min];

        //得到实际排序后的位置
        int sortedPos = sumCount - 1;

        //  向最终结果里存放元素
        sortedArray[sortedPos] = arr[i];
        // 针对重复的元素，先放后面，然后减1，下次循环就会放在前面
        countArray[arr[i] - min]--;
    }
    return sortedArray;
}

桶排序（Bucket Sort）

假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。

桶排序利用函数的映射关系，减少了计划所有的比较操作，是一种Hash的思想，可以用在海量数据处理中。
计数排序也可以看作是桶排序的特例，数组关键字范围为N，划分为N个桶。

桶排序实现

public static double[] bucketSort(double[] arr) {
    // 1. 得到数列的最大值和最小值，并计算出差值d
    double max = arr[0];
    double min = arr[0];

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    double d = max - min;

    // 2. 初始化桶
    int bucketNum = arr.length;

    ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
    for (int i = 0; i < bucketNum; i++) {
        bucketList.add(new LinkedList<Double>());
    }

    // 3. 遍历原始数组，将每个元素放入桶中
    for (int i = 0; i < arr.length; i++) {
        int num = (int) ((arr[i] - min) * (bucketNum - 1) / d);
        bucketList.get(num).add(arr[i]);
    }

    // 4. 对每个桶内部进行排序
    for (int i = 0; i < bucketList.size(); i++) {
        // JDK低层采用了归并排序或归并的优化版本
        Collections.sort(bucketList.get(i));
    }

    // 5. 输出全部元素
    double[] sortedArray = new double[arr.length];
    int index = 0;

    for (LinkedList<Double> list : bucketList) {
        for (double element : list) {
            sortedArray[index] = element;
            index++;
        }
    }
    return sortedArray;
}

堆排序（Heap Sort）

堆排序是把数组看作堆，第i个结点的孩子结点为第2i + 1和2i + 2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。

下述代码使用的大顶堆，建立好堆后堆顶元素为最大值，此时取堆顶元素即使堆顶元素和最后一个元素交换，最大的元素处于数组最后，此时调整小了一个长度的堆，然后再取堆顶和倒数第二个元素交换，依次类推，完成数据的非递减排序。

堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的文件。

堆排序实现

//堆排序 arr为待调整的堆
public static void heapSort(int[] arr) {
    // 1. 把无序数组构建成二叉堆
    for (int i = (arr.length - 2) / 2; i >= 0; i--) {
        downAdjust(arr, i, arr.length);
    }
    System.out.println(Arrays.toString(arr));

    // 2.循环删除栈顶元素，移到集合尾部，调整堆产生新的栈顶
    for (int i = arr.length - 1; i > 0; i--) {
        //最后一个元素和第一个元素进行交换
        int tmp = arr[i];
        arr[i] = arr[0];
        arr[0] = tmp;
        // 下沉调整最大堆
        downAdjust(arr, 0, i);
    }
}
public static downAdjust(int[] arr, int parentIndex, int length) {
    int tmp = arr[parentIndex];
    int childIndex = 2 * parentIndex + 1;

    while (childIndex < length) {
        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
        if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
            childIndex++;
        }
        //如果父节点大于任何一个孩子的值，直接跳出
        if (tmp >= arr[childIndex]) 
            break;
        //无需真正交换，单向赋值即可
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * childIndex + 1;
    }
    arr[parentIndex] = tmp;
}