在生活中，我们离不开排序，按大小个、按成绩等等

在计算机中也离不开排序：按编号、按价格、按远近等等

根据时间复杂度的不同，主流的排序算法可以分为3大类：

时间复杂度为O(n^2)的排序算法

冒泡排序、选择排序、插入排序、希尔排序

时间复杂度为O(nlogn)的排序算法

快速排序、归并排序、堆排序

时间复杂度为线性的排序算法

计数排序、桶排序、基数排序

根据其稳定性，可以分为稳定排序和不稳定排序：

稳定排序：值相同的元素在排序后仍然保持着排序前的顺序
不稳定排序：值相同的元素在排序后打乱了排序前的顺序

冒泡排序

冒泡排序是最基础的排序算法

冒泡排序的英文是bubble sort，它是一种基础的交换排序

原理

冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变

经过第一轮后：

元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧

每一轮结束都会有一个元素被移到最右侧

实现

package com.rubin.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * T = O(n^2)
 */
public class BubbleSort {

    public static void bubbleSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        for (int i = nums.length - 1; i >= 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {23, 1, 34, 5, 65, 3, 7, 9, 13, 10, 2};
        bubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}

快速排序

原理

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，这种思路就叫作分治法。

基准元素的选择

基准元素，英文是pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边

我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置

元素的交换

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。

双边循环法

首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素

接下来进行第1次循环：

从right指针开始，让指针所指向的元素和基准元素做比较

如果大于或等于pivot，则指针向左移动

如果小于pivot，则right指针停止移动，切换到left指针

轮到left指针行动，让指针所指向的元素和基准元素做比较

如果小于或等于pivot，则指针向右移动

如果大于pivot，则left指针停止移动

左右指针指向的元素交换位置

由于left开始指向的是基准元素，判断肯定相等，所以left右移1位

由于7>4，left指针在元素7的位置停下。这时，让left和right指针所指向的元素进行交换

接下来，进入第2次循环，重新切换到right指针，向左移动。right指针先移

动到8，8>4，继续左移。由于2<4，停止在2的位置

单边循环法

单边循环法只从数组的一边对元素进行遍历和交换

始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界

接下来，从基准元素的下一个位置开始遍历数组

如果遍历到的元素大于基准元素，就继续往后遍历

如果遍历到的元素小于基准元素，则需要做两件事

第一，把mark指针右移1位，因为小于pivot的区域边界增大了1

第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域

首先遍历到元素7，7>4，所以继续遍历

接下来遍历到的元素是3，3<4，所以mark指针右移1位

随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域

按照这个思路，继续遍历，后续步骤如图所示

代码实现

package com.rubin.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序
 * T = O(nlogn)
 */
public class QuickSort {

    /**
     * 双边快速排序
     *
     * @param nums
     */
    public static void doubleQuickSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        doDoubleQuickSort(nums, 0, nums.length - 1);
    }

    private static void doDoubleQuickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = findDoubleQuickSortPivot(nums, start, end);
        doDoubleQuickSort(nums, start, pivot - 1);
        doDoubleQuickSort(nums, pivot + 1, end);
    }

    private static int findDoubleQuickSortPivot(int[] nums, int start, int end) {
        int pivot = nums[start], left = start, right = end;
        while (left != right) {
            while (left < right && nums[right] > pivot) {
                --right;
            }
            while (left < right && nums[left] <= pivot) {
                ++left;
            }
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        nums[start] = nums[left];
        nums[left] = pivot;
        return left;
    }

    /**
     * 单边快排
     */
    public static void singleQuickSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        doSingleQuickSort(nums, 0, nums.length - 1);
    }

    private static void doSingleQuickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = findSingleQuickSortPivot(nums, start, end);
        doSingleQuickSort(nums, 0, pivot -1);
        doSingleQuickSort(nums, pivot + 1, end);
    }

    private static int findSingleQuickSortPivot(int[] nums, int start, int end) {
        int pivot = nums[start], mark = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] < pivot) {
                ++mark;
                int tmp = nums[i];
                nums[i] = nums[mark];
                nums[mark] = tmp;
            }
        }
        nums[start] = nums[mark];
        nums[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
        int[] nums = {23, 1, 34, 5, 65, 3, 7, 9, 13, 10, 2};
        doubleQuickSort(nums);
        System.out.println(Arrays.toString(nums));
        int newNums[] = {23, 13, 1, 34, 5, 65, 3, 7, 9, 13, 10, 2};
        singleQuickSort(newNums);
        System.out.println(Arrays.toString(newNums));
    }

}

堆排序

原理

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

堆是具有以下性质的完全二叉树

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 2*(i+1)
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

1、构造初始堆

将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)

2、此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整

3、找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换

4、这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6

此时，我们就将一个无需序列构造成了一个大顶堆

5、将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换

将堆顶元素9和末尾元素4进行交换

6、重新调整结构，使其继续满足堆定义

7、再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

代码实现

package com.rubin.algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序
 * T = O(nlogn)
 */
public class HeapSort {

    public static void heapSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        createHeap(nums);
        for (int i = nums.length - 1; i > 0; i--) {
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            adjustHeap(nums, 0, i);
        }
    }

    /**
     * 构建堆结构（大顶堆）
     *
     * @param nums
     */
    private static void createHeap(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0 ; i--) {
            adjustHeap(nums, i, nums.length);
        }
    }

    /**
     * 调整堆结构
     *
     * @param nums
     * @param parent
     * @param length
     */
    private static void adjustHeap(int[] nums, int parent, int length) {
        int adjustValue = nums[parent];
        // 左孩子
        int child = parent * 2 + 1;
        while (child < length) {
            // 有右孩子并且大于左孩子 则指针给到右孩子 目的就是选出最大的孩子节点
            if (child + 1 < length && nums[child + 1] > nums[child]) {
                ++child;
            }
            // 如果父节点大于最大的孩子节点 则符合大顶堆结构 无需调整
            if (adjustValue >= nums[child]) {
                break;
            }
            // 如果小于子节点 则将子节点的值赋给父节点
            nums[parent] = nums[child];
            // 此时给不给子节点赋值都可以 目的是继续调整子节点的堆结构 因为子节点交换后可能会影响交换的子节点的子堆
            parent = child;
            child = parent * 2 + 1;
        }
        nums[parent] = adjustValue;
    }

    public static void main(String[] args) {
        int[] nums = {23, 13, 1, 34, 5, 65, 3, 7, 9, 13, 10, 2};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

}

计数排序

原理

计数排序，这种排序算法是利用数组下标来确定元素的正确位置的

假设数组中有10个整数，取值范围为0～10，要求用最快的速度把这10个整数从小到大进行排序

可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0

假设数组数据为：9，1，2，7，8，1，3，6，5，3

下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作

例如第1个整数是9，那么数组下标为9的元素加1

最终，当数列遍历完毕时，数组的状态如下：

该数组中每一个下标位置的值代表数列中对应整数出现的次数

直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次，0不输出

则顺序输出是：1、1、2、3、3、5、6、7、8、9

计数排序：适合于连续的取值范围不大的数组

不连续和取值范围过大会造成数组过大

如果起始数不是从0开始，比如分数排序：95，94，91，98，99，90，99，93，91，92

数组起始数为90，这样数组前面的位置就浪费了

可以采用偏移量的方式：

代码实现

package com.rubin.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序
 * 适用于排数据范围小的数列
 * T = O(n+m)
 * n: 数据个数
 * m: 数据范围
 */
public class CountSort {

    /**
     * 计数排序
     *
     * @param nums
     * @param offset
     * @return
     */
    public static int[] countSort(int[] nums, int offset) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] counts = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i] - offset;
            counts[n]++;
        }
        int[] result = new int[nums.length];
        for (int j = 0, k = 0; j < counts.length; j++) {
            int count = counts[j];
            if (count > 0) {
                for (int l = 0; l < count; l++) {
                    result[k] = j + offset;
                    ++k;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] scores = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        System.out.println(Arrays.toString(countSort(scores, 90)));
    }

}

桶排序

原理

桶排序同样是一种线性时间的排序算法

桶排序需要创建若干个桶来协助排序

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素

桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定

区间跨度 = （最大值-最小值）/ （桶的数量 - 1）

假设有一个非整数数列：4.5，0.84，3.25，2.18，0.5

第1步，分桶

第2步，遍历原始数列，把元素对号入座放入各个桶中

第3步，对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）

第4步，遍历所有的桶，输出所有元素

0.5，0.84，2.18，3.25，4.5

代码实现

package com.rubin.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * 桶排序
 *
 * T = O(n)
 */
public class BucketSort {

    public static double[] bucketSort(double[] nums) {
        if (nums == null || nums.length == 0) {
            return new double[0];
        }
        double min = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        int bucketNum = nums.length;
        double d = (max - min) / (bucketNum - 1);
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }
        for (int i = 0; i < nums.length; i++) {
            int bucketIndex = (int) ((nums[i] - min) / d);
            bucketList.get(bucketIndex).add(nums[i]);
        }
        double[] newNums = new double[bucketNum];
        int index = 0;
        for (LinkedList<Double> linkedList : bucketList) {
            Collections.sort(linkedList);
            for (Double item : linkedList) {
                newNums[index] = item;
                index++;
            }
        }
        return newNums;
    }

    public static void main(String[] args) {
        double[] array = {4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
        double[] sortedArray = bucketSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

}