排序
# 插入排序
# 直接插入排序（稳定）
public static int[] insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return arr;
}
int n = arr.length;
for (int i = 1; i < n; i++) {//注意i不能等于数组长度，因为数组下标从零开始而不是从1
int temp = arr[i];//存储待插入数的数值
int j;
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];//如果大于temp，往前移动一个位置
}
arr[j + 1] = temp;//将temp插入到适当位置
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 折半插入排序
public static int[] BInsertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];//保存要插入的数的数值
int low = 0;
int high = i - 1;
while (low <= high) {//low就是待插入值的适当插入点
int mid = (low + high) / 2;
if (arr[mid] > temp) {//待插入值小于中间值
high = mid - 1;//上区间值变为中间值-1
} else {
low = mid + 1;//下区间值变为中间值+1
}
}
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];//将low及low之前的数向前移动一位
}
arr[low] = temp;//low就是待插入值的适当插入点
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 希尔排序（缩小增量排序）
public static int[] shellSort(int[] arr) {
int d = arr.length / 2;
for (; d > 0; d = d / 2) {
for (int i = d; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i - d; j >= 0 && temp < arr[j]; j -= d) {
arr[j + d] = arr[j];
}
arr[j + d] = temp;
}
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 交换排序
# 冒泡排序（稳定）
public static int[] 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]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 分治-快速排序（重要）
public static int[] quickSort(int[] arr, int low, int high) {
if (low < high) {
int position = partition(arr, low, high);
quickSort(arr, low, position - 1);
quickSort(arr, position + 1, high);
}
return arr;
}
public static int partition(int[] arr, int low, int high) {
// 优化：随机选择基准，减少最坏情况概率
int randomPivotIndex = low + new Random().nextInt(high - low + 1);
swap(arr, randomPivotIndex, high);
// 基准值
int pivot = arr[high];
int pointer = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
pointer++;
swap(arr, pointer, j);
}
}
// 将中心元素和指针指向的元素交换位置
swap(arr, pointer + 1, high);
return pointer + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 选择排序
# 选择排序
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 堆排序（重要）
public static int[] heapSort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);
adjustHeap(arr, 0, j);
}
return arr;
}
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
//根节点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k < length - 1 && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
swap(arr, i, k);
i = k;
} else {
break;
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 归并排序
# 归并排序（重要）（稳定）
public static int[] mergeSort(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
merge(arr, 0, n - 1, temp);
return arr;
}
private static void merge(int[] arr, int low, int high, int[] temp) {
if (low < high) {//递归结束条件：分解直到数组长度不小于1
int mid = (low + high) / 2;
merge(arr, low, mid, temp);//左子数组
merge(arr, mid + 1, high, temp);//右子数组
if (arr[mid] > arr[mid + 1]) {//如果左子数组最大的数都不大于右子数组最小数，数组已经有序，不需要进行排序
//将无序数组赋给temp
for (int i = low; i <= high; i++) {
temp[i] = arr[i];
}
//给无序数组排序，并赋给原数组
int i = low; //左子数组起点
int j = mid + 1; //右子数组起点
for (int k = low; k <= high; k++) {//k为原数组赋值点
if (i == mid + 1) { //如果i下标已经到了右子数组起点，说明左子数组已经比较完毕
arr[k] = temp[j]; //只需要将右子数组剩下的全部值赋给原数组即可
j++; //j标签向前移动
} else if (j == high + 1) {
arr[k] = temp[i];
i++;
} else if (temp[i] < temp[j]) { //如果左子数组最小值[i]小于右子数组最小值[j]
arr[k] = temp[i]; //将[i]作为两个子数组中的最小值赋给原数组
i++; //i下标向前移动
} else {
arr[k] = temp[j];
j++;
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 基于非比较
# 基数排序
todo
1
# 计数排序
todo
1
# 桶排序
todo
1
编辑 (opens new window)