排序算法

前言

Java 中常见的排序算法有如下几种：

• 选择排序（SelectionSort）
• 冒泡排序（BubbleSort）
• 插入排序（InsertionSort）
• 快速排序（QuickSort）
• 归并排序（MergeSort）
• 希尔排序（ShellSort）
• 堆排序（HeapSort）

代码中使用到的SortUtils和SortAlgorithm请查看章节 SortUtils和SortAlgorithm

选择排序（SelectionSort）

选择排序	选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

算法说明

From Wikipedia：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

Java代码实现

package sort;

import static sort.SortUtils.*;

/**
 * 选择排序
 *
 * @see SortAlgorithm
 *
 */

public class SelectionSort implements SortAlgorithm {

    /**
     * This method implements the Generic Selection Sort
     *
     * @param arr The array to be sorted
     * Sorts the array in increasing order
     **/
    @Override
    public <T extends Comparable<T>> T[] sort(T[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Initial index of min
            int min = i;

            for (int j = i +1 ; j < n; j++) {
                if (less(arr[j], arr[min])) {
                    min = j;
                }
            }

            // Swapping if index of min is changed
            if (min != i) {
                swap(arr, i , min);
            }
        }

        return arr;
    }

    // Driver Program
    public static void main(String[] args) {

        Integer[] arr = {4, 23, 6, 78, 1, 54, 231, 9, 12};

        SelectionSort selectionSort = new SelectionSort();

        Integer[] sorted = selectionSort.sort(arr);

        // Output => 1   4     6 9  12 23 54 78 231
        print(sorted);

        // String Input
        String[] strings = {"c", "a", "e", "b","d"};
        String[] sortedStrings = selectionSort.sort(strings);

        //Output => a  b   c  d  e
        print(sortedStrings);
    }
}

冒泡排序（BubbleSort）

使用冒泡排序为一列数字进行排序的过程	冒泡排序

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

冒泡排序对n个项目需要O( n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要 O(n^{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地运行O(n^{2})，而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最优情况下的复杂度降低到 O(n)。在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。

冒泡排序算法的运作如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

Java代码实现

package sort;

import static sort.SortUtils.*;

/**
 * 冒泡排序
 *
 * @see SortAlgorithm
 */

class BubbleSort implements SortAlgorithm {
    /**
     * This method implements the Generic Bubble Sort
     *
     * @param array The array to be sorted
     * Sorts the array in increasing order
     **/

    @Override
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        int n = unsorted.length;
        int newn;
        do {
            newn = 0;
            for (int i = 1; i < n; i++)
                if (unsorted[i - 1].compareTo(unsorted[i]) > 0) {
                    swap(unsorted, i - 1, i);
                    newn = i;
                }
            n = newn;
        } while (newn > 0);
        return null;
    }

    // Driver Program
    public static void main(String[] args) {

        // Integer Input
        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.sort(integers);

        // Output => 231, 78, 54, 23, 12, 9, 6, 4, 1
        print(integers);

        // String Input
        String[] strings = {"c", "a", "e", "b","d"};
        //Output => e, d, c, b, a
        print(bubbleSort.sort(strings));

    }
}

插入排序（InsertionSort）

使用插入排序为一列数字进行排序的过程	使用插入排序为一列数字进行排序的过程

From Wikipedia:插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

Java代码实现

package sort;

import static sort.SortUtils.less;
import static sort.SortUtils.print;

/**
 *插入排序
 *
 */

class InsertionSort implements SortAlgorithm {

    /**
     * This method implements the Generic Insertion Sort
     * Sorts the array in increasing order
     *
     * @param array The array to be sorted
     *
     **/

    @Override
    public <T extends Comparable<T>> T[] sort(T[] array) {
        for (int j = 1; j < array.length; j++) {

            // Picking up the key(Card)
            T key = array[j];
            int i = j - 1;

            while (i >= 0 && less(key, array[i])) {
                array[i + 1] = array[i];
                i--;
            }
            // Placing the key (Card) at its correct position in the sorted subarray
            array[i + 1] = key;
        }
        return array;
    }

    // Driver Program
    public static void main(String[] args) {
        // Integer Input
        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};

        InsertionSort sort = new InsertionSort();

        sort.sort(integers);

        // Output => 1 4 6 9 12 23 54 78 231
        print(integers);

        // String Input
        String[] strings = {"c", "a", "e", "b","d"};

        sort.sort(strings);

        //Output => a  b  c  d  e
        print(strings);
    }
}

快速排序（QuickSort）

使用快速排序法对一列数字进行排序的过程	快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分区版本。

From Wikipedia:快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n个项目要O(n\log n)（大O符号）次比较。在最坏状况下则需要 O(n^{2})次比较，但这种状况并不常见。事实上，快速排序 \Theta (n log n)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

Java代码实现

package sort;

import static sort.SortUtils.*;

/**
 * 快排
 * @see SortAlgorithm
 */
class QuickSort implements SortAlgorithm {


    /**
     * This method implements the Generic Quick Sort
     *
     * @param array The array to be sorted
     *              Sorts the array in increasing order
     **/

    @Override
    public <T extends Comparable<T>> T[] sort(T[] array) {
        doSort(array, 0, array.length - 1);
        return array;
    }


    /**
     * The sorting process
     *
     * @param left  The first index of an array
     * @param right The last index of an array
     * @param array The array to be sorted
     **/

    private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
        if (left < right) {
            int pivot = partition(array, left, right);
            doSort(array, left, pivot - 1);
            doSort(array, pivot, right);
        }
    }

    /**
     * This method finds the partition index for an array
     *
     * @param array The array to be sorted
     * @param left  The first index of an array
     * @param right The last index of an array
     *              Finds the partition index of an array
     **/

    private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
        int mid = (left + right) / 2;
        T pivot = array[mid];

        while (left <= right) {
            while (less(array[left], pivot)) {
                ++left;
            }
            while (less(pivot, array[right])) {
                --right;
            }
            if (left <= right) {
//                System.out.println("pivot >> " + pivot + " left >> " + left + " right >> " + right + " vleft >> " + array[left] + " vright >> " + array[right]);
                swap(array, left, right);
                ++left;
                --right;
            }
        }
        return left;
    }

    // Driver Program
    public static void main(String[] args) {

        // For integer input
        Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

        QuickSort quickSort = new QuickSort();
        quickSort.sort(array);

        //Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
        print(array);

        String[] stringArray = {"c", "a", "e", "b", "d"};
        quickSort.sort(stringArray);

        //Output => a  b  c  d  e
        print(stringArray);
    }
}

归并排序（MergeSort）

归并排序	一个归并排序的例子：对一个随机点的链表进行排序

归并排序有的地方也称为合并排序。

From Wikipedia:归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(n log n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

归并操作

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法（Top-down）

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

迭代法（Bottom-up）

原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
2. 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
3. 重复步骤2，直到所有元素排序完毕，即序列数为1

Java代码实现

递归法（Top-down）

package sort;

import static sort.SortUtils.print;

/**
 * This method implements the Generic Merge Sort
 * 归并排序 递归方式
 * @see SortAlgorithm
 */

class MergeSort implements SortAlgorithm {


    /**
     * This method implements the Generic Merge Sort
     *
     * @param unsorted the array which should be sorted
     * @param <T>      Comparable class
     * @return sorted array
     */
    @Override
    @SuppressWarnings("unchecked")
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        T[] tmp = (T[]) new Comparable[unsorted.length];
        doSort(unsorted, tmp, 0, unsorted.length - 1);
        return unsorted;
    }

    /**
     * @param arr   The array to be sorted
     * @param temp  The copy of the actual array
     * @param left  The first index of the array
     * @param right The last index of the array
     *              Recursively sorts the array in increasing order
     **/
    private static <T extends Comparable<T>> void doSort(T[] arr, T[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            doSort(arr, temp, left, mid);
            doSort(arr, temp, mid + 1, right);
            merge(arr, temp, left, mid, right);
        }

    }

    /**
     * This method implements the merge step of the merge sort
     *
     * @param arr   The array to be sorted
     * @param temp  The copy of the actual array
     * @param left  The first index of the array
     * @param mid   The middle index of the array
     * @param right The last index of the array
     *              merges two parts of an array in increasing order
     **/

    private static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
        System.arraycopy(arr, left, temp, left, right - left + 1);


        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            arr[k] = temp[i];
            i++;
            k++;
        }

        while (j <= right) {
            arr[k] = temp[j];
            j++;
            k++;
        }
    }

    // Driver program
    public static void main(String[] args) {

        // Integer Input
        Integer[] arr = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(arr);

        // Output => 1    4    6 9  12 23 54 78 231
        print(arr);

        // String Inpu
        String[] stringArray = {"c", "a", "e", "b", "d"};
        mergeSort.sort(stringArray);
        //Output => a  b  c  d  e
        print(stringArray);
    }
}

From wikipedia，整体思路一致，区别为：👆那版本是先通过 System.arraycopy()将arr数组指定数据段复制到temp数组中后直接对arr数组进行操作。而wikipedia版的则为操作result数组后再拷贝回arr数组。

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, result, start1, end1);
	merge_sort_recursive(arr, result, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		result[k++] = arr[start1++];
	while (start2 <= end2)
		result[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
	int len = arr.length;
	int[] result = new int[len];
	merge_sort_recursive(arr, result, 0, len - 1);
}

迭代法（Bottom-up）

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;
    
    // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
    for(block = 1; block < len; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
	        result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
	        result[low++] = arr[start1++];
            }
            while(start2 < end2) {
	        result[low++] = arr[start2++];
            }
        }
	int[] temp = arr;
	arr = result;
	result = temp;
    }
    result = arr;       
}

希尔排序（ShellSort）

希尔排序	希尔排序算法彩条

From Wikipedia:希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

Donald Shell最初建议步长选择为 n/2 并且对步长取半直到步长达到1。虽然这样取可以比O(n^{2})类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

步长序列	最坏情况下复杂度
n/2^i	O(n^2)
2^k - 1	O(n^{3/2})
(2^i)*(3^j)	O(n log^2 n)

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)，该序列的项来自
$$
9\times 4^{i}-9\times 2^{i}+1
$$
和
$$
2^{i+2}\times (2^{i+2}-3)+1
$$
这两个算式[1]。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

另一个在大数组中表现优异的步长序列是（斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列）：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)[2]

Java代码实现

package sort;

import static sort.SortUtils.*;


/**
 * 希尔排序
 * 
 * @see SortAlgorithm
 *
 */
public class ShellSort implements SortAlgorithm {

  /**
   * This method implements Generic Shell Sort.
   * @param array The array to be sorted
   */
  @Override
  public <T extends Comparable<T>> T[] sort(T[] array) {
    int N = array.length;
    int h = 1;

    while (h < N/3) {
        h = 3 * h + 1;
    }

    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && less(array[j], array[j-h]); j -= h) {
                swap(array, j, j - h);
            }
        }

        h /= 3;
    }

    return array;
  }

  public static void main(String[] args) {
      Integer[] toSort = {4, 23, 6, 78, 1, 54, 231, 9, 12};

      ShellSort sort = new ShellSort();
      Integer[] sorted = sort.sort(toSort);

      print(sorted);

  }
}

堆排序（HeapSort）

算法说明

堆排序是对简单选择排序的改进

简单选择排序是从n个记录中找出一个最小的记录，需要比较n-1次。但是这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。

二叉树: 每个结点最多有两个子树的有序树

完全二叉树：除最后一层，其他各层的节点都有2个子节点。并且最后一层从左往右有若干连续节点。

满二叉树：完全二叉树的特殊存在，即完全二叉树的最后一层都有节点。即除最后一层外，每个节点下都有2个子节点

堆里面有两个特殊的存在：

• 最大堆（大顶堆）：每个结点的值都大于或等于其左右孩子结点的值
• 最小堆（小顶堆）：每个结点的值都小于或等于其左右孩子结点的值

通过最小堆（最大堆）和完全二叉树的特性，构成了堆排序。

维基百科

堆排序（英语：Heapsort）是指利用堆)这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法思路

思路一：将数据排列成最小堆。第一项即为最小值。取出后将数据序列的最后一项移到第一项处，刷新当前最小堆从而得出当前最小堆中的最小值。以此往复得出排序。

思路二：将数据排列成最大堆。第一项即为最大值。取出后将数据序列的最后一项移到第一项处，刷新当前最大堆从而得出当前最大堆中的最大值。以此往复得出排序

思路一适用于从大到小排序，可以直接将每次的首项与当前堆的最后一节点数据置换，可以在同一个数组上操作。当然也可以新建一个数组存放从小到大的数据。

Java代码实现

最大堆（维基百科-堆排序Java）

import java.util.Arrays;

public class HeapSort {
    
    private int[] arr;
    
    public HeapSort(int[] arr){
        this.arr = arr;
    }
    
    /**
     * 堆排序的主要入口方法，共两步。
     */
    public void sort(){
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1; 
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }
        
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }
    
    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     * 
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。
        
        if(li > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }
    
    /**
     * 测试用例
     * 
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};        
        new HeapSort(arr).sort();        
        System.out.println(Arrays.toString(arr));
    }
    
}

SortUtils和SortAlgorithm

SortAlgorithm.java

public interface SortAlgorithm {

    /**
     * Main method arrays sorting algorithms
     * @param unsorted - an array should be sorted
     * @return a sorted array
     */
    <T extends Comparable<T>> T[] sort(T[] unsorted);

    /**
     * Auxiliary method for algorithms what wanted to work with lists from JCF
     * @param unsorted - a list should be sorted
     * @return a sorted list
     */
    @SuppressWarnings("unchecked")
    default <T extends Comparable<T>> List<T> sort(List<T> unsorted){
        return Arrays.asList(sort(unsorted.toArray((T[]) new Comparable[unsorted.size()])));
    }

}

SortUtils.java

/**
 * The class contains util methods
 * 数组、打印 的一些帮助类
 **/
final class SortUtils {


    /**
     * Helper method for swapping places in array
     * @param array The array which elements we want to swap
     * @param idx index of the first element
     * @param idy index of the second element
     */
    static <T> boolean swap(T[] array, int idx, int idy){
        T swap = array[idx];
        array[idx] = array[idy];
        array[idy] = swap;
        return true;
    }


    /**
     * This method checks if first element is less then the other element
     * @param v first element
     * @param w second element
     * @return true if the first element is less then the second element
     */
    static <T extends Comparable<T>> boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }


    /**
     * Just print list
     * @param toPrint - a list which should be printed
     */
    static void print(List<?> toPrint){
        toPrint.stream()
                .map(Object::toString)
                .map(str -> str + " ")
                .forEach(System.out::print);

        System.out.println();
    }


    /**
     * Prints an array
     * @param toPrint - the array  which should be printed
     */
    static void print(Object[] toPrint){
        System.out.println(Arrays.toString(toPrint));
    }



    /**
     * Swaps all position from {@param left} to @{@param right} for {@param array}
     * @param array is an array
     * @param left is a left flip border of the array
     * @param right is a right flip border of the array
     */
    static <T extends Comparable<T>> void flip(T[] array, int left, int right) {
        while (left <= right) {
            swap(array, left++ , right--);
        }
    }
}

参考

维基百科-堆排序

Java排序算法(五)：堆排序

引用

1. ^Pratt, V. Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Garland. 1979. ISBN 0-824-04406-1. (This was originally presented as the author’s Ph.D. thesis, Stanford University, 1971)
2. ^ A154393 The fibonacci to the power of two times the golden ratio gap sequence

算法目录

排序算法
理论	计算复杂性理论 大O符号 全序关系 列表 稳定性 比较排序 自适应排序 排序网络 整数排序
交换排序	冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 臭皮匠排序 Bogo排序
选择排序	选择排序 堆排序 平滑排序 笛卡尔树排序 锦标赛排序 圈排序
插入排序	插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序
归并排序	归并排序 梯级归并排序 振荡归并排序 多相归并排序 串列排序
分布排序	美国旗帜排序 珠排序 桶排序 爆炸排序 计数排序 比较计数排序 鸽巢排序 相邻图排序 基数排序 闪电排序 插值排序
并发排序	双调排序器 Batcher归并网络 两两排序网络
混合排序	块排序 Tim排序 内省排序 Spread排序 J排序
其他	拓扑排序 煎饼排序 意粉排序

算法
排序—比较排序	冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 堆排序 鸡尾酒排序 梳排序 侏儒排序 图书馆排序 内省排序 奇偶排序
排序—线性时间排序	鸽巢排序 基数排序 计数排序 桶排序
排序—并行排序	排序网络 Batcher归并网络
排序—不实用的	Bogo排序 臭皮匠排序
排序—图	拓扑排序
搜索—列表	线性搜索 二分搜索
搜索—树・图	广度优先搜索 最良优先搜索 均一开销搜索 A* 深度优先搜索 迭代深化深度优先搜索 深度限制搜索 双方向探索 分枝限定法
搜索—字符串	克努斯-莫里斯-普拉特算法 Boyer-Moore字符串搜索算法 AC自动机算法 Rabin-Karp算法 位图算法
最短路问题	戴克斯特拉算法 贝尔曼-福特算法 Floyd-Warshall算法
最小生成树	普林姆算法 克鲁斯克尔算法
最大流 最小割	Ford–Fulkerson算法 Edmonds–Karp算法
线性规划	单纯形法 Karmarkar算法
顺序统计量	选择算法 中位数的中位数
种类	近似算法 随机化算法
其他	分治法 动态规划 贪心法