排序算法作为面试必问的题目，其重要性不言而喻，因此必须掌握每种算法的思路以及时间、空间复杂度，最好能够手写出各个排序算法的代码。下面，我将结合
其他资料
以及自己的理解，逐个分析十种排序算法。
目录
算法总览
比较类排序
：通过比较来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)。
非比较类排序
：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行。
稳定
：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
不稳定
：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能会出现在 b 的后面。
按时间复杂度可以分为三类排序
1. O(n * 2)
选择排序、插入排序、冒泡排序
2. O(n * logn)
快速排序、归并排序、堆排序
3. O(n)
计数排序、桶排序、基数排序
冒泡排序（Bubble Sort）
从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至有序。
public class Test {
// 常规冒泡排序
public static void bubbleSort(int[] arr) {
// 外层循环：比较的轮次
for (int i = 0; i < arr.length - 1; i++) {
// 内层循环：每一轮将当前的最大值交换至最后位置，同时缩短数组范围
// 从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至将最大值放至末尾
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}
}
}
// 冒泡排序优化：设置标志位，当目前数组已经有序后，不用再继续遍历比较。
// 最好情况时间复杂度可降低至 O(N)：即当初始数组已经是一个有序数组的情况。
public static void bubbleSortOptimize(int[] arr) {
// 设置标志位，作为判断是否已经有序的标志
int flag = 0;
int length = arr.length;
// 如果此时数组长度不为 0 ，则循环
while (length > 0) {
// 每一轮都需要更新标志为：0
flag = 0;
// 从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至将最大值放至末尾
for (int i = 0; i < length - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
// 更新标志位：记录下当前最大值的位置
flag = i + 1;
}
}
// 更新长度
length = flag;
}
}
// 交换数组元素方法
public static void swap(int[] arr, int cur, int next) {
int temp = arr[cur];
arr[cur] = arr[next];
arr[next] = temp;
}
// 测试
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
bubbleSortOptimize(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
外层 for 循环次数：n – 1；
内层 for 循环次数（平均）：(n – 1) + (n – 2) + … + 1 = n * (n – 1) / (2 * (n – 1)) = n / 2；
时间复杂度：(n – 1) * n / 2 = O(n * 2)。 -
时间复杂度（最坏）
外层 for 循环次数：n – 1；
时间复杂度 ：(n – 1) + (n – 2) + … + 1 = n * (n – 1) / 2 = O(n * 2) -
时间复杂度（最好）
最好情况时间复杂度可降低至 O(N)：即当初始数组已经是一个有序数组的情况，见上述方法 BubbleSortOptimize(int[] arr)。 -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
选择排序（Selection Sort）
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public class Test {
public static void selectionSort(int[] arr) {
// 外层循环：确定无序数组的左边界下标
for (int i = 0; i < arr.length - 1; i++) {
// 保存最小元素的数组下标
int minIndex = i;
// 内层循环：找出 [i, arr.length] 中的最小值下标，并与 i 位置的元素进行替换
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
swap(arr, i, minIndex);
}
}
// 交换数组元素方法
public static void swap(int[] arr, int cur, int minIndex) {
int temp = arr[cur];
arr[cur] = arr[minIndex];
arr[minIndex] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
selectionSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
外层 for 循环次数：n – 1；
内层 for 循环次数（平均）：(n – 1) + (n – 2) + … + 1 = n * (n – 1) / (2 * (n – 1)) = n / 2；
时间复杂度：(n – 1) * n / 2 = O(n * 2)。 -
时间复杂度（最坏）
外层 for 循环次数：n – 1；
时间复杂度 ：(n – 1) + (n – 2) + … + 1 = n * (n – 1) / 2 = O(n * 2)。 -
时间复杂度（最好）
O(n * 2)：同平均和最坏情况。 -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
不稳定：a 原本在 b 前面，而 a = b，排序之后 a 不在 b 的前面。
举例：5，5，2 排序后 前面的 5 会放置最后
插入排序（Insertion Sort）
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
public class Test {
public static void insertionSort(int[] arr) {
// 外层循环：遍历第一个元素以外的所有其他元素，将其插入到前面的有序数组中
for (int i = 1; i < arr.length; i++) {
// 保存前一个元素的下标
int preIndex = i - 1;
// 保存待插入的当前元素
int current = arr[i];
// 如果前一个元素下标合法，同时元素值大于待插入的当前元素
// 则将前一个元素向后移动，同时前一个元素下标向前移动
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// 将待插入元素插入到合适的位置
arr[preIndex + 1] = current;
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
insertionSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
外层 for 循环次数：n – 1；
内层 for 循环次数（平均）：1 + 2 + … + (n – 2) + (n – 1) = n * (n – 1) / (2 * (n – 1)) = n / 2；
时间复杂度：(n – 1) * n / 2 = O(n * 2)。 -
时间复杂度（最坏）
外层 for 循环次数：n – 1；
时间复杂度 ：1 + 2 + … + (n – 2) + (n – 1) = n * (n – 1) / 2 = O(n * 2) -
时间复杂度（最好）
最好情况时间复杂度为 O(N)：即当初始数组已经是一个有序数组的情况，只需考虑外层循环复杂度即可。 -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
希尔排序（Shell Sort）
由 Shell 发明，第一个突破 O(n * 2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
public class Test {
public static void shellSort(int[] arr) {
// 希尔排序的核心在于间隔序列的设定：既可以提前设定好间隔序列，也可以动态的定义间隔序列。
// 设定间隔序列
for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
// 从间隔序列开始遍历，每次遍历即为一次插入排序
for (int i = gap; i < arr.length; i++) {
// 保存待插入的当前元素
int current = arr[i];
// 保存前一个间隔序列元素的下标
int preIndex = i - gap;
// 如果前一个间隔序列元素下标合法，同时元素值大于待插入的当前元素
// 则将前一个间隔序列元素向后移动，同时前一个间隔序列元素下标向前（一个间隔序列）移动
while (preIndex >= 0 && arr[preIndex] > cur) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
// 将待插入元素插入到合适的位置
arr[preIndex + gap] = current;
}
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
shellSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（最坏）
时间复杂度：O(n * 2) -
时间复杂度（最好）
时间复杂度：O(n * 1.3) -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
不稳定：a 原本在 b 前面，而 a = b，排序之后 a 不在 b 的前面（取决于间隔序列）。
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
public class Test {
public static void mergeSorts(int[] arr) {
int[] temps = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temps);
}
/**
* 归并排序
* @param arr 排序数组
* @param left 数组左边界
* @param right 数组右边界
* @param temps 临时数组
*/
public static void mergeSort(int[] arr, int left, int right, int[] temps) {
// 如果左边界大于等于右边界，则直接返回
if (left >= right) return;
// 计算中间索引位置
int mid = (left + right) >> 1;
// 递归左半部分
MergeSort(arr, left, mid, temps);
// 递归右半部分
MergeSort(arr, mid + 1, right, temps);
// 使用i j 分别指向左右两部分数组的头部位置
int i = left;
int j = mid + 1;
// 给临时数组赋值
for (int k = left; k <= right; k++) temps[k] = arr[k];
for (int m = left; m <= right; m++) {
// 如果左半部分数组比对完，直接将右半部分剩余数组插入后面
if (i == mid + 1) arr[m] = temps[j++];
// 如果右半部分数组比对完，直接将左半部分剩余数组插入后面；或者左边的数小于等于右边的数，将左边小的数插入
// temps[i] <= temps[j] 这行代码决定了归并排序是稳定的算法
else if (j == right + 1 || temps[i] <= temps[j]) arr[m] = temps[i++];
// 如果左边的数大于右边的数，则将右边小的数插入
// 这行代码不能合并入第一个 if 语句里面，如果此时 j == right + 1，而 i != mid + 1，就会出现数组越界的问题
else arr[m] = temps[j++];
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
mergeSorts(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
循环次数：logn
循环体复杂度：O(n)
时间复杂度：O(n * logn) -
时间复杂度（最坏）
时间复杂度：O(n * logn) -
时间复杂度（最好）
时间复杂度：O(n * logn) -
空间复杂度
O(n)： 临时数组占用 O(N) 大小的额外空间。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
快速排序（Quick Sort）
通过一趟排序将待排数组用一个中间元素分隔成两部分，其中左部分元素均比中间元素小，右部分元素均比中间元素大，则可分别对这两部分继续进行排序，以达到整个序列有序。
public class Test {
public static void quickSorts(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int left, int right) {
// 递归结束条件
if (left >= right) return;
// 获取中立元素下标：左侧元素均小于中立元素，右侧元素均大于等于中立元素
int index = getIndexByTwo(arr, left, right);
// 递归左部分
quickSort(arr, left, index - 1);
// 递归右部分
quickSort(arr, index + 1, right);
}
/**
* 常规快速排序：找到中立元素的下标：使得左侧元素均小于中立元素，右侧元素均大于等于中立元素
* @param arr 待排序数组
* @param left 数组左边界
* @param right 数组右边界
* @return
*/
public static int getIndex(int[] arr, int left, int right) {
// 保存中立元素下标
int index = left;
// 选取左边界值作为比较对象
int num = arr[left];
// 从前往后扫描
for (int i = left + 1; i <= right; i++) {
// 如果当前值小于比较对象：则 index 向前移动，然后交换位置
if (arr[i] < num) {
index++;
swap(arr, index, i);
}
}
// 交换比较对象和中立元素，交换后：左侧元素均小于中立元素，右侧元素均大于等于中立元素
swap(arr, left, index);
return index;
}
/**
* 二路快速排序，找到中立元素的下标
* @param arr 待排序数组
* @param left 数组左边界
* @param right 数组右边界
* @return
*/
public static int getIndexByTwo(int[] arr, int left, int right) {
int i = left;
int j = right;
while (i < j) {
// 从后往前扫描，找到小于比较对象的元素下标
while (i < j && arr[j] >= arr[left]) j--;
// 从前往后扫描，找到大于比较对象的元素下标
while (i < j && arr[i] <= arr[left]) i++;
// 交换下标
swap(arr, i, j);
}
// 交换数组元素
swap(arr, left, i);
return i;
}
// 交换数组中的两个元素
public static void swap(int[] arr, int pre, int cur) {
int temp = arr[pre];
arr[pre] = arr[cur];
arr[cur] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
quickSorts(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
循环次数：logn
循环体复杂度：O(n)
时间复杂度：O(n * logn) -
时间复杂度（最坏）
循环次数：O(n)
循环体复杂度：O(n)
时间复杂度：O(n * 2) -
时间复杂度（最好）
时间复杂度：O(n * logn) -
空间复杂度
O(logn)：快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的栈空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。
稳定性
不稳定：a 原本在 b 前面，而 a = b，排序之后 a 不在 b 的前面。
快速排序，时间复杂度比较复杂，因为这个和他的基准数选取有关，假如说基准数刚好是中间值，对半分的话，就是O(n * logn)。假如基准数是最小的或者最大的， 那就变成O(n * 2)。
快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。
快速排序快的主要原因是大大减少了比较和交换的次数，因为按基准数切分的两半数组，在一个数组里面的数据是绝对不会和第二个数组里面的数据进行比较。
为什么快排比对堆排序好？
-
堆排序数据访问的方式没有快速排序友好
对于快速排序来说，数据是顺序访问；而对于堆排序来说，数据是跳着访问，所以对 CPU 缓存不友好。 -
堆排序算法的数据交换次数要多于快速排序
排序算法里面有两个概念，有序度（数组中具有有序关系的元素对的个数）和逆序度（数组中具有无序关系的元素对的个数）。
快速排序不会导致数据的有序度降低；但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。
堆排序（Heap Sort）
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
public class Test {
public static void heapSort(int[] arr) {
// 从最后一个叶子节点的父节点开始进行堆调整
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
heapify(arr, arr.length, i);
}
// 将堆顶的最大元素交换至数组尾部，同时缩小数组长度，再次进行堆调整
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);
heapify(arr, j, 0);
}
}
// 堆调整
public static void heapify(int[] arr, int n, int k) {
// 如果有子节点，则进行调整
while (2 * k + 1 < n) {
// 保存左节点下标
int m = 2 * k + 1;
// 找出左右节点中较大的值下标
if (m + 1 < arr.length && arr[m + 1] > arr[m]) m++;
// 如果父节点最大，无需调整，直接退出
if (arr[k] > arr[m]) break;
// 调整父节点和较大子节点的位置
swap(arr, k, m);
// 继续向被调整的子节点位置开始向下调整
k = m;
}
}
public static void swap(int[] arr, int head, int tail) {
int temp = arr[head];
arr[head] = arr[tail];
arr[tail] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
heapSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
循环次数：n
循环体复杂度：O(logn)
时间复杂度：O(n * logn) -
时间复杂度（最坏）
循环次数：n
循环体复杂度：O(logn)
时间复杂度：O(n * logn) -
时间复杂度（最好）
循环次数：n
循环体复杂度：O(logn)
时间复杂度：O(n * logn) -
空间复杂度
O(1)：只需原地交换元素，使用常数大小的额外空间。
稳定性
不稳定：a 原本在 b 前面，而 a = b，排序之后 a 不在 b 的前面。
计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
public class Test {
public static void countingSort(int[] arr) {
// 保存最大值
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
// 构建数组保存每个数字出现的次数
int[] count = new int[max + 1];
for (int num : arr) count[num]++;
// 待排序数组的下标
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
// 次数减 1
count[i]--;
}
}
}
public static void main(String[] args) {
int[] arr = {6, 3, 5, 4, 3, 2, 1};
countingSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
时间复杂度：O(n + k) -
时间复杂度（最坏）
时间复杂度：O(n + k) -
时间复杂度（最好）
时间复杂度：O(n + k) -
空间复杂度
O(n + k)：n 为数据规模，k 为数据范围。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
public class Test {
public static void BucketSort(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// 确定一个桶因子：用于计算桶的数量
// 当然，这个桶因子可以是手动传入，这里默认指定为5
int factor = 5;
int bucketSize = (max - min) / factor + 1;
List<LinkedList<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketSize; i++) buckets.add(new LinkedList<>());
for (int num : arr) {
buckets.get((num - min) / factor).add(num);
}
int index = 0;
for (int j = 0; j < bucketSize; j++) {
buckets.get(j).sort(Comparator.comparingInt(o -> o));
for (int k = 0; k < buckets.get(j).size(); k++) arr[index++] = buckets.get(j).get(k);
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
BucketSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
时间复杂度：O(n + k) -
时间复杂度（最坏）
时间复杂度：O(n * 2) -
时间复杂度（最好）
时间复杂度：O(n) -
空间复杂度
O(n + k)：n 为数据规模，k 为数据范围。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶的数量越多，各个桶里面的数据就越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
public class Test {
public static void radixSort(int[] arr) {
// 找出最大值
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
// 计算最大值的位数
int radix = 0;
while (max > 0) {
max /= 10;
radix++;
}
List<LinkedList<Integer>> buckets = new ArrayList<>();
// 数字的每一位取值：0 - 9
for (int i = 0; i < 10; i++) buckets.add(new LinkedList<>());
// 进行 radix 轮排序，即可得到有序数组
for (int j = 0; j < radix; j++) {
helper(arr, buckets, j);
}
}
public static void helper(int[] arr, List<LinkedList<Integer>> buckets, int radix) {
// 遍历数组，将每一个元素放入对应的桶里面
for (int num : arr) {
int index = (int)(num % Math.pow(10, radix + 1) / Math.pow(10, radix));
buckets.get(index).add(num);
}
// 弹出桶内元素，重新赋值给待排序数组
int k = 0;
for (int i = 0; i < buckets.size(); i++) {
while (!buckets.get(i).isEmpty()) {
arr[k++] = buckets.get(i).poll();
}
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
radixSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
时间复杂度：O(n * k) -
时间复杂度（最坏）
时间复杂度：O(n * k) -
时间复杂度（最好）
时间复杂度：O(n * k) -
空间复杂度
O(n + k)：n 为数据规模，k 为数据范围。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，基数排序的时间复杂度O(n * k) ，当然k要远远小于n，因此基本上还是线性级别的。