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 ( N 2 ) O(N^2) O ( N 2 ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N 2 ) O(N^2) O ( N 2 ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N 2 ) O(N^2) O ( N 2 ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N 2 ) O(N^2) O ( N 2 ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N l o g N ) O(NlogN) O ( N l o g N ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N l o g N ) O(NlogN) O ( N l o g N ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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 ( N l o g N ) O(NlogN) O ( N l o g N ) ,其中 N N N 是数组 nums \textit{nums} nums 的长度。
空间复杂度:O ( 1 ) O(1) 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
手撕九大经典排序算法,看我就够了!
常用排序算法复杂度分析
排序算法全解析