冒泡排序
每次从左到右两两比较，把大的交换到后面，每次可以确保将前M个元素的最大值移动到最右边。
|
1 2 3 4 5 6 7 8 9 10 |
void bubble_sort(vector<int> &nums) { for (int i = 0; i < nums.size() - 1; i++) { // times for (int j = 0; j < nums.size() - i - 1; j++) { // position if (nums[j] > nums[j + 1]) { std::swap(nums[j], nums[j + 1]); } } } } |
插入排序
插入排序的原理是从左到右，把选出的一个数和前面的数进行比较，找到最适合它的位置放入，使前面部分有序。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void insert_sort(vector<int>& nums) { int n = (int) nums.size(); for (int i = 1; i < n; ++i) { int tmp = nums[i]; int j = i - 1; for (; j >= 0 && nums[j] > tmp; --j) { nums[j + 1] = nums[j]; } nums[j + 1] = tmp; } } |
选择排序
选择排序的原理是，每次都从乱序数组中找到最大（最小）值，放到当前乱序数组头部，最终使数组有序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void select_sort(vector<int>& nums) { int n = (int) nums.size(); for (int i = 0; i < n; ++i) { int min = i; for (int j = i + 1; j < n; ++j) { if (nums[j] < nums[min]) { min = j; } } std::swap(nums[min], nums[i]); } } |
希尔排序
将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void shell_sort(vector<int> &nums) { for (int gap = nums.size() >> 1; gap > 0; gap >>= 1) { // times for (int i = gap; i < nums.size(); i++) { // position int tmp = nums[i]; int j = i - gap; for (; j >= 0 && nums[j] > tmp; j -= gap) { nums[j + gap] = nums[j]; } nums[j + gap] = tmp; } } } |
归并排序
分治思想，归并排序的思想就是先递归分解数组，再合并数组。
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和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 |
void merge_array(vector<int> &nums, int begin, int mid, int end, vector<int> &temp) { int i = begin, j = mid, tb = begin; while (i != mid && j != end) if (nums[i] < nums[j]) temp[tb++] = nums[i++]; else temp[tb++] = nums[j++]; while (i < mid) temp[tb++] = nums[i++]; while (j < end) temp[tb++] = nums[j++]; for (int k = begin; k < end; ++k) nums[k] = temp[k]; } void merge_sort(vector<int> &nums, int begin, int end, vector<int> &temp) { int mid = (begin + end) / 2; if (mid != begin) { merge_sort(nums, begin, mid, temp); merge_sort(nums, mid, end, temp); merge_array(nums, begin, mid, end, temp); } } |
堆排序
- 构造最大堆（Build Max Heap）：首先将当前元素放入最大堆下一个位置，然后将此元素依次和它的父节点比较，如果大于父节点就和父节点交换，直到比较到根节点。重复执行到最后一个元素。
- 最大堆调整（Max Heapify）：调整最大堆即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换，然后把堆看做n-1长度，将当前根节点逐步移动到其应该在的位置。
- 堆排序（HeapSort）：重复执行2，直到所有根节点都已移除。
|
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 |
void max_heapify(vector<int>& nums, int begin, int end) { int root = begin; int child = root * 2 + 1; while (child < end) { if (child + 1 < end && nums[child] < nums[child + 1]) { ++child; } if (nums[root] < nums[child]) { std::swap(nums[root], nums[child]); root = child; child = 2 * root + 1; } else { break; } } } void heap_sort(vector<int>& nums) { int n = nums.size(); for (int i = n / 2 - 1; i >= 0; i--) { // build max heap max_heapify(nums, i, nums.size() - 1); } for (int i = n - 1; i > 0; i--) { // heap sort std::swap(nums[i], nums[0]); max_heapify(nums, 0, i); } } |
快速排序
分治法思想，选择一个基准数，把比这个数小的挪到左边，把比这个数大的移到右边。然后不断对左右两部分也执行相同步骤，直到整个数组有序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void quick_sort(vector<int> &nums, int begin, int end) { if (begin < end - 1) { int left = begin, right = end - 1; while (left < right) { while (left < right && nums[right] >= nums[begin]) right--; while (left < right && nums[left] <= nums[begin]) left++; std::swap(nums[left], nums[right]); } std::swap(nums[begin], nums[left]); quick_sort(nums, begin, left); quick_sort(nums, left + 1, end); } } |
总结
| 排序方法 | 平均时间 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 希尔排序 | O(nlog(n))～O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 归并排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) | 稳定 |
| 堆排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(1) | 不稳定 |
| 快速排序 | O(nlog(n)) | O(nlog(n)) | O(n2) | O(log(n))-O(n) | 不稳定 |
微信扫一扫，打赏作者吧～