常见的排序算法复杂度：
冒泡排序：时间复杂度O(n^2)
排序方法：
- 比较相邻元素，如果第一个比第二个大，则交换他们
- 一轮下来，可以保证最后一个数是最大的
- 执行n-1轮，就可以完成排序
实现思路：
- 用二重循环实现，外循环变量设为i，内循环变量设为j。假如有n个数需要进行排序，则外循环重复n-1次，内循环依次重复n-1，n-2，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,n-1，对于每一个i，j的值依次为0,1,2,...n-i 。
- 设数组长度为N：
- 比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
- 这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
- N=N-1，如果N不为0就重复前面二步，否则排序完成。
代码：
public class BubbleSort {
public static void BubbleSort(int[] arr) {
int temp;//定义一个临时变量
for (int i = 0; i < arr.length - 1; i++) {//冒泡趟数
for (int j = 0; j < arr.length - i - 1; j++) {
// 后面比前面小，则进行交换，这样必然就是大的往后挪动
if (arr[j + 1] < arr[j]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] = new int[]{1, 6, 2, 2, 5};
System.out.println("原数组：");
for (int num : arr) {
System.out.print(num + " ");
}
BubbleSort.BubbleSort(arr);
System.out.println();
System.out.println("排序后：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}选择排序：时间复杂度O(n^2)
排序思路：
- 找到数组中的最小值，将它放在第一位；(直接将最小的元素与第一个元素进行交换)
- 接着找到第二小的值，将它放在第二位；
- 依次类推，执行n-1轮；
代码实现：
public class SelectionSort {
public static void SelectionSort(int[] arr) {
//选择排序的优化
for (int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for (int j = k + 1; j < arr.length; j++) {// 选最小的记录
if (arr[j] < arr[k]) {
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if (i != k) { //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 6, 2, 2, 5};
System.out.println("原数组：");
for (int num : arr) {
System.out.print(num + " ");
}
SelectionSort(arr);
System.out.println();
System.out.println("排序后：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}插入排序：时间复杂度O(n^2)
排序方法：将元素插入到排序好的数组中
- 从第二个数开始往前比；(所以需要设置临时变量)
- 寻找合适的插入位置，直到当前这个元素比前面大且比后面小为止；
- 以此类推直到最后一个数；
代码实现：
public class StraightInsertionSort {
//直接插入排序
static void insertSort(int[] a) {
int Arrlength = a.length;
// 从第二个数开始
for (int i = 1; i < Arrlength; i++) {
// 前面比后面大，需要进行排序
if (a[i - 1] > a[i]) {
// 记录这个比后面大元素的位置,需要寻找后面这个元素的插入位置，寻找的范围是前i-1的位置
int j = i - 1;
// 后面的这个元素
int temp = a[i];
// 给后面这个元素寻址位置
while (temp < a[j]) {
// 元素往后窜的过程
a[j + 1] = a[j];
j--;
if (j < 0) {
break;
}
}
a[j + 1] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 6, 2, 2, 5};
System.out.println("原数组：");
for (int num : arr) {
System.out.print(num + " ");
}
insertSort(arr);
System.out.println();
System.out.println("排序后：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}希尔排序：
排序方法：
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
代码实现：似乎不常用？
归并排序：时间复杂度O(nlogn)，分的时间复杂度O(logn)，合并的过程的复杂度是O(n)
排序方法：
- 分：把数组分成两半，递归子数组,进行分割操作，直到分成一个数；
- 合：把两个字数组合并成一个有序数组，直到全部子数组合并完毕，合并前先准备一个空数组，存放合并之后的结果，然后不断取出两个子数组的第一个元素，比较他们的大小，小的先进入之前准备的空数组中，然后继续遍历其他元素，直到子数组中的元素都完成遍历；
这图可能来源就是图中水印位置，不太记得了，笔记里的老图
代码实现：
public class MergeSort {
public static void main(String[] args) {
int[] arr = {1, 6, 2, 2, 5};
System.out.println("原数组：");
for (int num : arr) {
System.out.print(num + " ");
}
//tmp是用于存放新排序的数组的
int[] tmp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, tmp);
System.out.println();
System.out.println("排序后：");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
int i = 0;
int j = low, k = mid + 1; //左边序列和右边序列起始索引
while (j <= mid && k <= high) {
if (arr[j] < arr[k]) {
tmp[i++] = arr[j++];
} else {
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余，则将其全部拷贝进tmp[]中
while (j <= mid) {
tmp[i++] = arr[j++];
}
while (k <= high) {
tmp[i++] = arr[k++];
}
for (int t = 0; t < i; t++) {
arr[low + t] = tmp[t];
}
}
public static void mergeSort(int[] arr, int low, int high, int[] tmp) {
if (low < high) {
int mid = (low + high) / 2;
// 分
mergeSort(arr, low, mid, tmp); //对左边序列进行归并排序
mergeSort(arr, mid + 1, high, tmp); //对右边序列进行归并排序
// 合
merge(arr, low, mid, high, tmp); //合并两个有序序列
}
}
}相关习题：
- 148. 排序链表【中等+归并排序】
- 23. 合并K个升序链表【困难+归并（分治）】
- 373. 查找和最小的K对数字【中等+多路归并+自定义优先队列的排序规则】
- 786. 第 K 个最小的素数分数【困难+多路分治递归！惊艳了】
- 378. 有序矩阵中第 K 小的元素【中等+分治+优先队列】
- 373. 查找和最小的K对数字【中等+多路归并+自定义优先队列的排序规则】
快速排序：时间复杂度O(nlogn)，递归复杂度是O(logn),分区复杂度O(n)
排序方法：(啊哈算法中讲到)
- 第一步：设置两个指针left和right分别指向数组的头部和尾部，并且以头部的元素（6）为基准数
- 第二步：right指针先往左移动，找到小于基准数的元素就停下，然后移动left指针
- 第三步：left指针往右移动，找到大于基准数的元素就停下，然后交换right和left指针所值元素的值
- 重复第二、三步，直到两个指针left和right重合
- 第四步：两个指针重合后将基准数（6）与两个指针指向的元素值（3）交换
- 到这时，第一轮排序结束，此时以基准数（6）为分界点，（6）左边的数都小于等于6，（6）右边的数都大于等于6，现在我们已经将原来的序列以（6）为分界点拆成了两个序列左边的序列是3 1 2 5 4，右边的序列是9 7 10 8，接下来分别处理这两个序列，原理相同。
- 最终序列为1 2 3 4 5 6 7 8 9 10，到此排序完全结束（快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止）
排序要注意的：
必须是右先动，否则就不是从小到大排序了；
代码实现：
?
public class QuickSort {
public static void main(String[] args) {
int[] arr = {1, 6, 2, 2, 5};
System.out.println("原数组：");
for (int num : arr) {
System.out.print(num + " ");
}
quickSort(arr, 0, arr.length - 1);
System.out.println();
System.out.println("排序后：");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] arr, int leftPos, int rightPos) {
if (rightPos < leftPos) {
} else {
//将数列最左边第一个数字作为基准数
int initLeftPos = leftPos;
int initRightPos = rightPos;
int baseNum = arr[leftPos];
while (rightPos > leftPos) {
//第二步：右边指针找到小于基准数的就停下
while (arr[rightPos] >= baseNum & rightPos > leftPos) {
rightPos--;
}
//第二步：左边指针找到大于基准数的就停下
while (arr[leftPos] <= baseNum & rightPos > leftPos) {
leftPos++;
}
//交换两个指针最终标记的数字
if (rightPos > leftPos)
swap(arr, leftPos, rightPos);
}
//当左右两边指针重合时，将基准数与指针指向数字交换
swap(arr, leftPos, initLeftPos);
//指针左半边递归，以进来的数组的左边为界，右边是左右指针相同时左边一个
quickSort(arr, initLeftPos, leftPos - 1);
//右边同理
quickSort(arr, rightPos + 1, initRightPos);
}
}
//swap方法：将数组中leftPos和rightPos上的两个数值进行交换
public static void swap(int[] arr, int leftPos, int rightPos) {
int temp = arr[leftPos];
arr[leftPos] = arr[rightPos];
arr[rightPos] = temp;
}
}参考文献：
部分参考百度百科
归并排序（Java代码实现）_Leo的博客-CSDN博客_归并排序java
《啊哈！算法》/ 啊哈磊著. 人民邮电出版社