选择排序
复制 public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 找出 0 ~ n-1 中的最小值的索引
// 找出 1 ~ n-1 中的最小值的索引
// 找出 2 ~ n-1 中的最小值的索引
// 找出 i ~ n-1 中的最小值的索引
for (int i = 0; i < arr.length; i++) {
int minValueIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
}
// 交换值，将每次最小都放入前面
swap(arr, i, minValueIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int iV = arr[i];
arr[i] = arr[j];
arr[j] = iV;
}
@Test
public void testSelectionSort() {
int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
selectionSort(arr);
System.out.println(Arrays.toString(arr));
} 时间复杂度：
冒泡排序
依次比较相邻的数，并交换，最后将最大的数冒泡到最后，这样循环 n-1 次后，即可排序所有数。
复制 public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ n-1
// 0 ~ n-2
// 0 ~ n-3
// 0 ~ n-4
// 也就是 0 ~ end
for (int end = arr.length - 1; end >= 0; end--) {
// 在 0 ~ end 上对数进行两两比较，将最大的数冒泡到最后
// 需要循环 end-1 次，倒数第二次循环已经将最大值选出了
for (int i = 0; i <= end - 1; i++) { // 从1开始是为了不溢出
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
@Test
public void testBubbleSort() {
int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
} 时间复杂度：
假设数组长度为 n，交换方式是最坏的情况，每次都要交换
那么交换次数为： n, n-1, n-2, ... 3, 2, 1
根据等差数列公式，Sn=n*a1+n(n-1)d/2 或者 Sn=n(a1+an)/2，可以得到数据量级n与交换次数之间的关系为 (1/2)*(n^2) -(1/2 -a1)n
保留最高次项，故冒泡排序的时间复杂度为O(n^2)
插入排序
插入排序之所以叫插入排序，是因为他的排序过程类似扑克游戏斗地主的摸牌的排序过程。
复制 public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ 0
// 0 ~ 1 范围有序
// 0 ~ 2 范围有序
// ...
// 0 ~ n 范围有序
for (int end = 0; end < arr.length; end++) {
// 排序新数
int newNumIndex = end;
while (newNumIndex - 1 >= 0 && arr[newNumIndex-1] > arr[newNumIndex]) {
swap(arr, newNumIndex -1, newNumIndex);
newNumIndex--;
}
}
} 时间复杂度：
归并排序
归并排序是时间复杂度为O(n*logn)。
递归实现
将数组拆分为两半，确认中间位置 (L+R)/2 = M
左右部分排序成功后，准备一个R-L长度的数组空间，同时遍历左右空间，每次取出一个元素，比较两个两个数字的大小。谁小将谁放额外数组空间中，这样就完成了结果的归并
就这样这样依次对半拆分排序，直到不能再拆分，再依次归并，即可完成归并排序
复制 /**
* 递归实现归并排序
*/
public void mergeSort1(int[] arr, int L, int R) {
if (arr == null || arr.length < 2
|| L < 0 || L >= arr.length
|| R < 0 || R >= arr.length || L >= R) {
return;
}
process(arr, L, R);
}
public void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
int M = (L + R) / 2;
process(arr, L, M);
process(arr, M + 1, R);
merge(arr, L, M, R);
}
public void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1]; // 创建一个用于盛放合并后数组的数组
int i = 0; // help的指针，每次填充后+1
int p1 = L; // 遍历左部分的指针
int p2 = M + 1;// 遍历有部分的指针
// p1 p2 都在正确的范围内
while (p1 <= M && p2 <= R) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// 如果p1在正确的范围内，说明p2循环完毕了
while (p1 <= M) {
help[i++] = arr[p1++];
}
// 如果p2在正确的范围内，说明p1循环完毕了
while (p2 <= R) {
help[i++] = arr[p2++];
}
// 将help排序后的内容填充到arr中
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
@Test
public void testMergeSort1() {
int[] arr = new int[]{7, 9, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
mergeSort1(arr, 0, 5);
System.out.println(Arrays.toString(arr));
} 复杂度：
复制 T(n) = aT(n/b) + O(N^d)
T(n) = 2T(n/2) + O(N^1)
a = 2, b = 2, d = 1
logbA = 1 == d，那么时间复杂度为 O(N^d * logN) ，即 O(N*logN) 也可以使用for循环替代while：
复制 package com.rhdk.contractservice;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// 递归实现归并排序
int[] arr = new int[]{2, 1, 3, 4};
mergeSort1(arr);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int L, int R) {
if (L >= R) {
return;
}
int M = (L + R) / 2;
sort(arr, L, M);
sort(arr, M + 1, R);
merge(arr, L, M, R);
}
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int lIndex = L;
int rIndex = M + 1;
for (int i = 0; i < help.length; i++) {
if (lIndex > M && rIndex > R) {
break;
}
if (lIndex > M) {
help[i] = arr[rIndex++];
continue;
}
if (rIndex > R) {
help[i] = arr[lIndex++];
continue;
}
if (arr[lIndex] <= arr[rIndex]) {
help[i] = arr[lIndex++];
} else {
help[i] = arr[rIndex++];
}
}
// 填充到原数组
if (R + 1 - L >= 0) {
System.arraycopy(help, 0, arr, L, R - L + 1);
}
}
} 非递归实现
递归是将数组拆分为两半，而这种方式则是将元素分为固定的k组，整体思想是相同的
k=1：循环数组，因为数组在[0,0]、[1,1]、[2,2]、[3,3]...范围内有序，合并有序数组，让数组在[0,1]、[2,3]、[4,5]...范围内有序
k=2：循环数组，因为数组在[0,1]、[2,3]、[4,5]、[6,7]...范围内有序，合并有序数组，让数组在[0,3]、[4,7]、[8,11]...范围内有序
k=4：循环数组，因为数组在[0,3]、[4,7]、[8,11]...范围内有序，合并有序数组，让数组在[0,7]、[8,15]、[16,23]...范围内有序
k=?：循环数组，因为数组在[i, i+k-1]范围上有序，合并有序数组，让数组在 [i + 2k-1]范围内有序
如此循环数组，直到k>=arr.length时，即完成了数组的排序
此时让 k=4，按照上述流程继续循环，将4个7有序的小组合并为8个有序的小组
代码如下：
复制 public void mergeSort2(int[] arr) {
int k = 1;
int i = 0;
while (k <= arr.length) {
if (i >= arr.length) {
i = 0;
k <<= 1;
}
// 左索引为i，右索引为 i + 2 * k - 1，且不能超过数组长度-1，中间为i + k - 1，且不能超过数组长度
int L = i;
int R = Math.min(i + 2 * k - 1, arr.length - 1);
int M = Math.min(i + k - 1, arr.length - 1);
// 将小组合并为大组
merge(arr, L, M, R);
// 重置i索引
i += 2 * k;
}
}
@Test
public void testMergeSort2() {
int[] arr = new int[]{9, 7, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
mergeSort2(arr);
System.out.println(Arrays.toString(arr));
} 时间复杂度：
复制 while (k <= arr.length)
i += 2 * k;
每次使用x2的方式追赶问题规模N，故外层复杂度为 logN
每当if (i >= arr.length) 重新开始循环，这是内层循环
内层循环只走了merge方法，时间复杂度为N
所以时间复杂度也为 O(N * logN) 为什么选择、冒泡、插入排序O(n^2)的时间复杂度劣于归并排序O(N * logN)？
因为前者在比较时，将所有的数依次比较，很多比较行为并没有交换，造成了很多无效的操作。
小和问题
假设有个数组， [6, 3, 4, 6, 7]，
第4个元素左侧比该元素小的值的总和为6+3+4+6=19
要求复杂度为 O(N*logN)
快速排序
快排的步骤：
以数组中最后一个数字P为边界，将数组内的小于等于P的数放在左侧，大于P的数放右侧
当前数 <= P，当前数在 <= 区，当前数与下一个数交换，<= 区扩容1，当前数指针向后移动一次
