冒泡排序
外层循环次数为集合元素数 - 1 (两两比较)
内层循环每次 -1 (每次循环确定最末尾数)
1
2
3
4
5
6
7
8
9
10
11
| public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int idx = 0; idx < arr.length - 1 - i; idx++) {
if (arr[idx] > arr[idx + 1]) {
int temp = arr[idx + 1];
arr[idx + 1] = arr[idx];
arr[idx] = temp;
}
}
}
}
|
选择排序
默认首位数为最小，遍历后续元素，确定最小索引，交换数据
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int tmp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = tmp;
}
}
|
插入排序
默认从二号元素开始，左侧元素为有序列
遍历时若较左侧小的数，进行移动(类冒泡)，否则直接进入下次外循环 (较左侧最近数大，则较有序列所有数大)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void insertionSort(int[] a) {
int cur = 0;
int len = a.length;
while (++cur < len) {
if (a[cur] < a[cur - 1]) {
int val = a[cur];
int idx = cur;
while (--idx >= 0 && val < a[idx]) {
a[idx + 1] = a[idx];
}
a[idx + 1] = val;
}
}
}
|
希尔排序
一种改进的插入排序
最外层循环为步长
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void shellSort(int[] arr) {
for (int step = arr.length >>> 1; step > 0; step >>>= 1) {
for (int j = step; j < arr.length; j++) {
for (int idx = j; idx > 0 && idx - step >= 0; idx -= step) {
if (arr[idx] < arr[idx - step]) {
int temp = arr[idx - step];
arr[idx - step] = arr[idx];
arr[idx] = temp;
} else {
break;
}
}
}
}
}
|
快速排序
首先确定一个基数，将大于/小于他的数置于其两侧，再对左右两侧集合进行递归
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
| public static void quickSort(int[] arr, int start, int end) {
if (start + 1 > end) {
return;
}
boolean isStartWithEnd = true;
int left = start;
int right = end;
int meanVal = arr[start];
while (true) {
if (isStartWithEnd) {
if (arr[end] >= meanVal) {
end--;
} else if (arr[end] < meanVal) {
arr[start] = arr[end];
start++;
isStartWithEnd = false;
}
} else {
if (arr[start] <= meanVal) {
start++;
} else if (arr[start] > meanVal) {
arr[end] = arr[start];
end--;
isStartWithEnd = true;
}
}
if (start == end) {
arr[start] = meanVal;
break;
}
}
quickSort(arr, left, start - 1);
quickSort(arr, start + 1, right);
}
|
归并排序
先进行递归，将列表进行拆分，首先从最小的切分集合进行排序，之后进行合并排序，最终合并排序为一个有序表
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
| public static void mergeSort(int[] arr, int start, int end) {
if (end <= start) {
return;
}
int mid = (start + end) >>> 1;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
int left = start;
int right = mid + 1;
int idx = 0;
int[] resArr = new int[end - start + 1];
while (left <= mid && right <= end) {
if (arr[left] <= arr[right]) {
resArr[idx] = arr[left];
left++;
} else {
resArr[idx] = arr[right];
right++;
}
idx++;
}
while (left <= mid || right <= end) {
if (left <= mid) {
resArr[idx] = arr[left];
left++;
} else {
resArr[idx] = arr[right];
right++;
}
idx++;
}
if (end - start + 1 >= 0) {
System.arraycopy(resArr, 0, arr, start, end - start + 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
27
28
29
30
31
| class HeapSort {
public static void sort(int[] arr) {
for (int i = arr.length >>> 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
for (int j = arr.length - 1; j > 0; j--) {
int tmp = arr[0];
arr[0] = arr[j];
arr[j] = tmp;
adjustHeap(arr, 0, j);
}
}
private static void adjustHeap(int[] arr, int cur, int len) {
int tmp = arr[cur];
for (int idx = cur * 2 + 1; idx < len; idx = idx * 2 + 1) {
if (idx + 1 < len && arr[idx + 1] > arr[idx]) {
idx++;
}
if (arr[idx] > tmp) {
arr[cur] = arr[idx];
cur = idx;
} else {
break;
}
}
arr[cur] = tmp;
}
}
|
基数排序
此处是最低位优先 (Least Significant Digit first，LSD) 法，从个位开始，对数组进行排序
将对应位元素出现的次数存储在 buckets 中
buckets[i] += buckets[i - 1] 将 bucket 的值变为对应最后一个元素的索引 (此时buckets 为一个有序索引桶)，每确定一个索引的元素将对应 bucket 的值 -1，将 bucket 存储的索引移动到对应的下一个索引
(实际上是索引 + 1，因为默认没有元素的 bucket 的值为 0，之后从 bucket 中取得索引需要 -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
| public static void radixSort(int[] arr) {
int max = arr[0];
int exp;
for (int num : arr) {
if (num > max) {
max = num;
}
}
for (exp = 1; max / exp > 0; exp *= 10) {
int[] tmpArr = new int[arr.length];
int[] buckets = new int[10];
for (int value : arr) {
buckets[(value / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
tmpArr[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
System.arraycopy(tmpArr, 0, arr, 0, arr.length);
}
}
|