笔记|几种面试常见排序的实现排序|#

题目链接 【笔记|几种面试常见排序的实现】实现了，快速排序，归并排序，堆排序。

快速排序，分治，每次通过双指针挖坑确定一个数的位置
归并排序，分治，每次合并两个有序数组
堆排序，维护一个最小堆
- 插入，插入末尾，从末尾开始向根节点方向交换
- 推出，取出根节点，将末尾和根节点交换，从根节点向叶子节点交换

class Solution { public: vector sortArray(vector& nums) { // quicksort(nums, 0, nums.size() - 1); // mergesort(nums, 0, nums.size() - 1); heapsort(nums, 0, nums.size() - 1); return nums; } // 快速排序 // 分治，每次确定一个数的位置，通过挖坑交换方法 void quicksort(vector &nums, int begin, int end) { if(begin >= end) return; int l = begin, r = end; int tmp = nums[l]; while(l < r) { while(l < r && nums[r] >= tmp) --r; if(l < r) nums[l] = nums[r]; while(l < r && nums[l] <= tmp) ++l; if(l < r) nums[r] = nums[l]; } nums[l] = tmp; quicksort(nums, begin, l-1); quicksort(nums, l+1, end); } // 归并排序 // 分治，合并两个有序数组 void mergesort(vector &nums, int begin, int end) { if(begin >= end) return; int mid = (begin + end) >> 1; mergesort(nums, begin, mid); mergesort(nums, mid+1, end); vector tmp; int l = begin, m = mid+1; while(l <= mid && m <= end) { if(nums[l] < nums[m]) tmp.push_back(nums[l++]); else tmp.push_back(nums[m++]); } while(l <= mid) tmp.push_back(nums[l++]); while(m <= end) tmp.push_back(nums[m++]); for(int i = begin; i <= end; ++i) nums[i] = tmp[i-begin]; } // 堆排序，根据堆排思想和优先队列想的瞎搞实现 // push 末尾向上爪巴 // pop 头部，将末尾替换头部向下爪巴 void push(vector &nums, int val, int len) { nums.push_back(val); int pos = len - 1; while(pos && nums[pos] < nums[(pos-1)/2]) swap(nums[pos], nums[(pos-1)/2]), pos = (pos-1)/2; } int pop(vector &nums, int len) { int ans = nums[0]; nums[0] = nums[len-1]; --len; nums.erase(nums.end()-1); int pos = 0, l = 1, r = 2; while(l < len && r < len) { if(nums[l] < nums[r]) { if(nums[l] < nums[pos]) { swap(nums[l], nums[pos]); pos = l; } else break; } else { if(nums[r] < nums[pos]) { swap(nums[r], nums[pos]); pos = r; } else break; } l = pos * 2 + 1; r = l + 1; } if(l < len && nums[l] < nums[pos]) swap(nums[l], nums[pos]); return ans; } void heapsort(vector &nums, int begin, int end) { vector tmp; for(int i = begin; i <= end; ++i) push(tmp, nums[i], i-begin+1); for(int i = begin; i <= end; ++i) nums[i] = pop(tmp, end-i+1); } };