排序算法(Sorting Algorithms)
By Long Luo
1. 冒泡排序(Bubble Sort)
思路与算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public static int[] bubbleSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
for (int i = len - 1; i >= 0; i--) {
boolean isSorted = true;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
isSorted = false;
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
if (isSorted) {
break;
}
}
return nums;
}
复杂度分析：
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
2. 选择排序(Select Sort)
思路与算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public static int[] selectSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[j] < nums[i]) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
复杂度分析：
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
3. 插入排序(Insert Sort)
思路与算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public static int[] insertSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
for (int i = 1; i < len; i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j + 1];
nums[j + 1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}
复杂度分析：
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
4. 希尔排序(Shell Sort)
思路与算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public static int[] shellSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
for (int gap = len / 2; gap >= 1; gap /= 2) {
for (int i = gap; i < len; i++) {
int j = i;
while (j - gap >= 0 && nums[j] < nums[j - gap]) {
int temp = nums[j];
nums[j] = nums[j - gap];
nums[j - gap] = temp;
j -= gap;
}
}
}
return nums;
}
复杂度分析：
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
5. 堆排序(Heap Sort)
思路与算法：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
40
41
42
43
44
45public static int[] heapSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
// 1. build the Max Heap
for (int i = len / 2 - 1; i >= 0; i--) {
maxHeapify(nums, i, len - 1);
}
// 2. swap Heap peek with the end, adjust the heap
for (int i = len - 1; i > 0; i--) {
swap(nums, 0, i);
maxHeapify(nums, 0, i - 1);
}
return nums;
}
private static void maxHeapify(int[] arr, int start, int end) {
int parent = start;
int child = 2 * start + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] < arr[child + 1]) {
child++;
}
if (arr[parent] < arr[child]) {
swap(arr, parent, child);
parent = child;
child = 2 * child + 1;
} else {
break;
}
}
}
private static void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
复杂度分析：
- 时间复杂度：\(O(NlogN)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
6. 归并排序(Merge Sort)
思路与算法：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
40
41
42
43
44
45public int[] mergeSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int len = nums.length;
mergeSort(nums, 0, len - 1);
return nums;
}
public void mergeSort(int[] nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
public void merge(int[] nums, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int[] temp = new int[nums.length];
int t = 0;
while (i <= mid && j <= right) {
if (nums[i] >= nums[j]) {
temp[t++] = nums[j++];
} else {
temp[t++] = nums[i++];
}
}
while (i <= mid) {
temp[t++] = nums[i++];
}
while (j <= right) {
temp[t++] = nums[j++];
}
t = 0;
while (left <= right) {
nums[left++] = temp[t++];
}
}
复杂度分析：
- 时间复杂度：\(O(NlogN)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
7. 快速排序(Quick Sort)
思路与算法：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
32public int[] quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int low, int high) {
if (low < high) {
int pos = partition(nums, low, high);
quickSort(nums, low, pos - 1);
quickSort(nums, pos + 1, high);
}
}
public int partition(int[] nums, int low, int high) {
int pivot = nums[low];
while (low < high) {
while (low < high && nums[high] > pivot) {
high--;
}
if (low < high) {
nums[low] = nums[high];
}
while (low < high && nums[low] < pivot) {
low++;
}
if (low < high) {
nums[high] = nums[low];
}
}
nums[low] = pivot;
return low;
}
复杂度分析：
- 时间复杂度：\(O(NlogN)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)。
排序算法总结
Array Sorting Algorithms Algorithm Time Complexity Space Complexity Best Average Worst Worst Quicksort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n)) Mergesort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n) Timsort Ω(n) Θ(n log(n)) O(n log(n)) O(n) Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1) Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1) Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1) Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1) Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n) Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1) Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n) Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k) Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k) Cubesort Ω(n) Θ(n log(n)) O(n log(n)) O(n)