八大排序的 Java 实现

1. 冒泡排序（BubbleSort）

图示说明

冒泡排序是一种较为直观简单的排序。它的工作原理是：遍历要排序的数组，每次比较前后两个元素，当前一位要比后一位数大时（位置错误），则交换它们的位置。直到没有元素需要被交换，则排序完成。

从图示来看，冒泡排序就好像在每次遍历后将最大的元素 “浮动” 到最顶端（即数组的末尾）：

代码

我们先来看基础版：实现非常简单，通过双循环来控制冒泡排序的遍历过程：

• 外循环控制排序的趟数，即数组的长度（针对最坏的情况）；
• 内循环控制每趟的比较次数，因为每趟遍历之后，后i个元素都是排序过的，所以只需要比较到arr.length - i - 1即可。

public static int[] bubbleSortBasic(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length; i++) { // 排序的趟数
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) { // 如果前一位比后一位要大，那么互相交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

冒泡排序的升级版也非常简单，即：如果在某趟排序中没有发生交换位置，那么我们可以认为该数组已经排好序了（即冒泡排序的最好情况，传入的是一个已经排好序的数组）：

public static int[] bubbleSortUpgrade(int[] arr) {
    int temp;
    boolean isChanged = false;  // 记录是否发生了置换
    
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isChanged = true;  // 如果进到这里面了，说明发生置换了
            }
        }
        /* 如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了 */
        if (!isChanged) break;
    }
    return arr;
}

2. 选择排序（SelectionSort）

图示说明

选择排序是一种简单直观的排序算法，它的工作原理是：遍历要排序的数组，每趟从数组选出最小（大）的元素并记录其下标，然后再存放到起始（末尾）位置，直到所有的元素到遍历完。

从图示来看，每次遍历先假设第一个元素为最小，如果该趟遍历中有比该元素更小（即红色标志），则替换最小元素下标，然后再该趟遍历结束后将最小元素移动到最前：

代码

和冒泡排序一样，我们需要通过双循环来遍历交换。外循环控制遍历的趟数，次数为arr.length - 1；内层循环来在每趟遍历时，查找i + 1 ~ arr.length中的最小元素下标。然后再每趟遍历结束之后，将最小元素交换到第i个位置：

public void selectionMinSort(int[] arr) {
    int temp;
    int min;  // 记录每趟最小值下标

    for (int i = 0; i < arr.length - 1; i++) {
        min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) min = j;  // 记录目前找到的最小值下标
        }
        // 将该趟找到的最小值和i位置所在的值进行交换
        if (i != min) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

如果是交换最大值的代码则为：

public void selectionMaxSort(int[] arr) {
    int temp;
    int max;  // 记录每趟最大值下标

    for (int i = 0; i < arr.length; i++) {
        max = 0;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[max]) max = j;
        }
        // 将最大值元素与arr.length - 1 - i位置元素交换
        temp = arr[max];
        arr[max] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = temp;
    }
}

3. 插入排序（InsertionSort）

图示说明

插入排序是一种最直观的排序算法，虽然没有上面两种排序方法简单粗暴，但是它的原理比较好理解：对于未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入。

如下图所示，在每次遍历中，都会选取未排序的数据（红色标志），然后在已排序的序列（黄色标志）中找到合适的位置并插入。这样，每一趟插入排序，都可以将一个无序值插入一个有序数列，直至全部值有序：

代码

插入排序的代码中，通过一个for循环来控制需要排序的趟数，因为下标为0时只有一个元素可以比较，则认为是有序的，所以从i = 1开始遍历。每趟都从第i个位置开始通过while循环，向左寻找比arr[i]更小的数，如果每次循环没有找到，则将j - 1的元素向后移动一位并继续向左寻找。

每次while循环结束之后，如果存在比arr[i]还小的数（即j != i），则将其值插入到j位置上。直到for循环遍历完毕，排序则完成：

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i;
        // 从已经排序的序列最右边开始比较，找到比其小的数
        while (j > 0 && temp < arr[j - 1]) {
            arr[j] = arr[j - 1];  // 往后移动一个位置
            j--;                  // 不断往前，直到退出循环
        }
        // 存在比其小的数，插入到第j个位置
        if (j != i) arr[j] = temp;
    }
}

4. 希尔排序（ShellSort）

图示说明

希尔排序又称缩小增量排序，也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本。实际上，希尔排序就是插入排序的高级版。

如下图所示（图片来源），希尔排序通过某个增量将数组元素划分为若干个分组序列，然后在每个分组序列中执行插入排序。接着逐步缩小增量值，继续按组进行插入排序的操作，直至增量值为1：

代码

从下面代码对比插入排序代码来看，除了外层循环控制增量的改变，内层实际上和插入排序逻辑相同。需要注意的是，分组之后比较的相邻元素下标间隔为gap，因此是比较arr[j]与arr[j - gap]的值：

public static void shellSort(int[] arr) {
    // 初始增量为 length / 2，每次增量都减为原来的一半
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 对分组的序列执行插入排序，直至完毕
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while (j - gap >= 0 && temp < arr[j - gap]) {
                arr[j] = arr[j - gap];    // 将元素移动到分组的下一个位置
                j = j - gap;              // 移动到分组的前一个元素
            }
            arr[j] = temp;
        }
    }
}

5. 归并排序（MergeSort）

图示说明

归并排序是建立在归并操作上的一种有效排序算法，是分治法的一个经典应用。该算法分为两个步骤：

• 分：将数组分成各个子序列，直到序列的个数为1，则视为已经排序的状态；
• 治：将两个子序列进行二路归并，每次取较小的元素放到临时数组当中，直到两个子序列所有元素都添加完，则该临时数组为两个子序列合并后的排序状态。

如下图所示（图片来源，侵删）

代码

public static void mergeSort(int[] arr) {
    /* 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间 */
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid, temp); //左边归并排序，使得左子序列有序
        mergeSort(arr, mid + 1, right, temp); //右边归并排序，使得右子序列有序
        merge(arr, left, mid, right, temp); //将两个有序子数组合并操作
    }
}

/**
 * 将两个已经有序的子序列合并成一个有序序列
 */
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;    //左序列指针
    int j = mid + 1; //右序列指针
    int t = 0;       //临时数组指针
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }
    while (i <= mid) { //将左边剩余元素填充进temp中
        temp[t++] = arr[i++];
    }
    while (j <= right) { //将右序列剩余元素填充进temp中
        temp[t++] = arr[j++];
    }
    t = 0;
    // 将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

6. 快速排序（QuickSort）

快速排序与冒泡排序是一类的交换排序，与归并排序类似应用了“分治”的算法来进行排序。它的基本原理是：在数组中找到一个任意的支点，经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大。然后再通过递归使用同样的方式对支点左右两边的子数组进行排序，直到子数组的个数为1。

一般来说，我们都采用第一个元素作为支点。例如对于用户输入的数组，我们选择下标为0作为支点，令pivot = 6，并定义两个变量i、j指向分别指向第一个元素和最后一个元素：

下标	0(i)	1	2	3	4	5(j)
数据	6	2	7	3	8	9

第一遍我们从右往左进行查找，将大于基准点的数移动到pivot的左边，从j开始，不断自增值直到找到比pivot小的元素。当下标为3时小于基准值，于是将i与j指向的元素互相交换：

下标	0	1(i)	2	3(j)	4	5
数据	3	2	7	6	8	9

第二遍我们从左往右进行查找，将小于基准点的数移动到pivot的右边，从i开始，不断自增值直到找到比pivot大的元素。当下标为2时大于基准值，于是同样将i与j指向的元素互相交换：

下标	0(left)	1	2(i)(j)	3	4	5(right)
数据	3	2	6(pivot)	7	8	9

这样就完成了第一个循环，接着再以同样的逻辑进行下一轮的循环，直到i>=j时终止循环，本例中第一次循环后就满足了i==j的条件。可以发现，再第一轮循环之后并没有完成完整的排序，但是基准点6左边的数都小于它，右边的数都大于它，这样就完成了快排的核心算法。接下来再以同样的算法去排序[left, i-1]与[i+1, right]子数组，直到每个子数组的仅剩一个元素即可。实现的算法如下：

public void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}

public void quickSort(int[] arr, int left, int right) {
    // 当left==right说明子数组仅一个元素，为递归的出口

    if (left < right) {
        int pivot = arr[left];  // 保存基准值
        int i = left, j = right;

        while (i < j) {
            while (i < j && arr[j] > pivot) { // 寻找比pivot小的数
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (i < j && arr[i] < pivot) { // 寻找比pivot大的数
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = pivot;  // 将下标为i设置为基准值

        quickSort(arr, left, i - 1);  // 排序左边
        quickSort(arr, i + 1, right); // 排序右边
    }
}

除此之外，我们来可以寻找中点、随机点作为基准点，例如选取中点作为基准点的代码如下：

public void quickSort(int[] arr){
    quickSort(arr,0,arr.length-1);
}

public void quickSort(int[] arr,int left,int right){
    int i=left,j=right;

    int pivot=arr[(left+right)/2]; // 支点

    while(i<=j){
        while(pivot>arr[i]) // 在左边寻找比支点大的数
            i++;
        while(pivot<arr[j]) // 在右边寻找比支点小的数
            j--;
        
        // 此时已经找到比支点大数和比支点小的数，交换i和j指向的元素
        if (i<=j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;
        }
    }

    if(left<j)
        quickSort(arr,left,j);
    
    if(i<right)
        quickSort(arr,i,right);
}

7. 堆排序（HeapSort）

见堆的结构实现与堆排序

8. 基数排序（RadixSort）

基数排序也成为桶排序，与其他七种排序有所区别，不是通过比较或者交换来达到排序的效果。而是通过不断地分配、回收来进行排序。

首先来考虑一种简单的情况，假设所给的乱序数组中元素数值在1~9之间，且没有相同的元素，例如[4, 1, 3, 5, 2, 6]。首选我们准备10个桶，数组的下标即为桶的序号，遍历数组将第i个元素放到第arr[i]个桶当中：

然后再从第一个桶按顺序进行回收，所回收的序列即为排序后的数组。代码实现如下：

public static void sort(int[] arr) {
    int[] buckets = new int[10];
    // 分配到指定需要的桶中
    for (int num : arr){
        buckets[num] = num;
    }
    // 回收
    int idx = 0;
    for (int bucket : buckets) {
        if (bucket != 0)
            arr[idx++]=bucket;
    }
}

明白的桶排序的基本原理，现在考虑正常的情况，即所给元素值可能是两位数、三位数…，而且数组中的元素可能相同，所以每个桶容纳的要大于1，我们将其设置为肯可能的最大值即arr.length（即所有元素都相等）。

实现的原理也基本相似，我们可以按照个位数、十位数、百位数依次进行桶排序，循环分配、回收的过程，直到将最大值最后一位分配回收之后，数组则排序完成。如下图所示（图片来自网络，侵删）：

代码如下所示：

public void radixSort(int[] arr) {
    int max = findMax(arr);

    int i = 1;
    // 控制遍历次数，由数组最大值的位数来决定
    while(max / i > 0) {
        // 初始化桶，一共有十个桶，每个桶的容量为arr.length
        int[][] buckets = new int[arr.length][10];

        for (int j = 0;j < arr.length; j++){
            int num = (arr[j] / i) % 10;
            // 将其放入桶中
            buckets[j][num]=arr[j];
        }

        int k = 0;

        // 将桶里的所有元素回收到数组当中
        for (int j = 0; j < 10; j++) {
            for (int l = 0; l < arr.length; l++) {
                if (buckets[l][j] != 0) {
                    arr[k++]=buckets[l][j];
                }
            }
        }

        i*=10;
    }
}

// 返回数组中的最大值
public int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) 
        if (arr[i]>max) max=arr[i];
    return max;
}

需要注意的是回收的时候和我们正常的二维数组的遍历顺序是有所区别的，如下图所示：

我们应该按照桶的顺序来进行回收，即先回收第一个桶的n个元素，再回收第二个桶的n个元素…

脑洞大开的排序

除了这八大排序之外，还有网友们脑洞大开的睡眠排序和猴子排序，我借机也实现了一下hhhhh~

睡眠排序

为数组的每个元素创建一个线程，其线程的休眠时间为该元素的数值。这样当数值小的线程将较快唤醒，并且较快唤醒的线程将其数值替换到数组的最前边。当子线程全部结束之后，数组排序完成：

public class SleepSort {

    static int idx = 0;

    static void sort(int[] arr) throws InterruptedException {
        List<Thread> threads = new ArrayList<>();
        
        for (int i = 0; i < arr.length; i++) {
            int sleepTime = arr[i];
            Thread thread = new Thread(() -> {
                try {
                    Thread.sleep(sleepTime * 1000);
                    arr[idx++]=sleepTime;
                } catch(InterruptedException e) {
                    e.printStackTrace();
                }
            });
            thread.start();
            threads.add(thread);
        }
        // 主线程等待子线程执行完毕
        for (Thread t : threads)
            t.join();
    }
}

（代码就是瞎写的，别在意并发竞争条件的问题惹…）

猴子排序

据说来自无限猴子定理：

一只猴子随机敲打打字机键盘，如果时间足够长，总是能打出特定的文本，比如莎士比亚全集。

实现非常简单：

public class MonkeySort {

    public static void sort(int[] arr) {
        int i = 0;
        while(!isOrder(arr, arr.length-1)) {
            shuffle(arr);
            i++;
        }
        System.out.println(i);
    }

    // 递归判断是否是顺序数组
    public static boolean isOrder(int[] arr, int idx){
        if (idx == 0) 
            return true;
        return (arr[idx] > arr[idx-1]) && isOrder(arr, idx-1);
    }

    // 随机打乱数组
    public static void shuffle(int[] arr) {
        Random rand = new Random();
        for (int i = arr.length; i > 0; i-- ){
            int randInd = rand.nextInt(i);
            swap(arr, randInd, i-1);
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

测试{4, 1, 5, 3, 2}样例11次，发现遍历次数i的数值变化如下：

---