冒泡排序
每次从左到右两两比较,把大的交换到后面,每次可以确保将前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) | 不稳定 |