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 23
| public 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(N2),其中 N 是数组 nums 的长度。
- 空间复杂度:O(1)。
2. 选择排序(Select Sort)
思路与算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public 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(N2),其中 N 是数组 nums 的长度。
- 空间复杂度:O(1)。
3. 插入排序(Insert Sort)
思路与算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public 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(N2),其中 N 是数组 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 20
| public 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(N2),其中 N 是数组 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 45
| public static int[] heapSort(int[] nums) { if (nums == null || nums.length <= 1) { return nums; }
int len = nums.length;
for (int i = len / 2 - 1; i >= 0; i--) { maxHeapify(nums, i, len - 1); }
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 是数组 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 45
| public 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 是数组 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 32
| public 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 是数组 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)
参考资料
- Sorting Visualization
- Sorting Algorithms
- 常用的排序算法总结
- 八大经典排序算法详解
- 复习基础排序算法
- Big O Cheat Sheet
- 手撕九大经典排序算法,看我就够了!
- 常用排序算法复杂度分析
- 排序算法全解析