排序算法分类
基于比较的排序
通过比较大小来决定元素间的相对次序
可以证明时间复杂度下界为O(NlogN)——不可能突破这个复杂度达到更快
非比较类排序
不通过比较大小来决定元素间的相对次序
时间复杂度受元素的范围以及分布等多种因素影响，不单纯取决于元素数量N
基于比较的排序
初级排序算法
选择排序(Selection Sort)——“该放哪个数了?“
每次从未排序数据中找最小值，放到已排序序列的末尾
插入排序(Insertion Sort)——“这个数该放哪儿?”
从前到后依次考虑每个未排序数据，在已排序序列中找到合适位置插入
冒泡排序（Bubble Sort)
不断循环扫描，每次查看相邻的元素，如果逆序，则交换
平均时间复杂度均为O(N2)
堆排序
堆排序(Heap Sort)是对选择排序的优化——利用二叉堆高效地选出最小值
建立一个包含所有N个元素的二叉堆
重复N次从堆中取出最小值，即可得到有序序列
时间复杂度O(NlogN)
void heap_sort(vector<int>& a, int n) { priority_queue<int> q; for(int i = 0; i < n; i++) { q.push(-a[i]); } for(int i = 0; i < n; i++) { a[i] = -q.top(); q.pop(); } }
希尔排序 (不太重要)
希尔排序(Shell Sort)是对插入排序的优化——增量分组插入排序
希尔排序的时间复杂度取决于增量序列（步长序列)的选取目前已知的最好序列可以做到o(N4/3)或o(Nlog2N)
归并排序
归并排序(Merge Sort)是一个基于分治的算法
时间复杂度O(NlogN)
原问题:把数组排序
子问题:把数组前一半、后一半分别排序
然后再合并左右两半（两个有序数组）就可以了
public static void mergeSort(int[] arr, int l, int r) { // sort arr[l..r] if (l >= r) return; int mid = (l + r) >> 1; // (l + r) / 2 mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // int i = left, j = mid + 1; for (int k = 0; k < temp.length; k++) { // if (j > right || (i <= mid && arr[i] <= arr[j])) temp[k] = arr[i++]; else temp[k] = arr[j++]; } for (int k = 0; k < temp.length; k++) { // arr[left + k] = temp[k]; } }
快速排序
快速排序(Quick Sort)也是一个基于分治的算法
- 从数组中选取中轴元素pivot
- 将小元素放在pivot左边，大元素放在右边
- 然后分别对左边和右边的子数组进行快排
快速排序和归并排序具有相似性，但步骤顺序相反
- 归并排序:先排序左右子数组，然后合并两个有序数组
- 快速排序:先调配出左右子数组，然后对左右子数组分别进行排序
随机选取pivot，期望时间复杂度O(NlogN)
快速排序可以通过适当的交换来原地实现数组调配，避免占用额外空间最经典和高效的调配方式叫作 Hoare Partition
public static void quickSort(int[] arr, int l, int r) { if (l >= r) return; int pivot = partition(arr, l, r); quickSort(arr, l, pivot); quickSort(arr, pivot + 1, r); } static int partition(int[] a, int l, int r) { int pivot = l + (int)(Math.random() * (r - l + 1)); int pivotVal = a[pivot]; while (l <= r) { while (a[l] < pivotVal) l++; while (a[r] > pivotVal) r--; if (l == r) break; if (l < r) { int temp = a[l]; a[l] = a[r]; a[r] = temp; l++; r--; } } return r; }
void quickSort(vector<int>& arr, int l, int r) { if (l >= r) return; int pivot = partition(arr, l, r); quickSort(arr, l, pivot); quickSort(arr, pivot + 1, r); } int partition(vector<int>& a, int l, int r) { int pivot = l + rand() % (r - l + 1); int pivotVal = a[pivot]; while (l <= r) { while (a[l] < pivotVal) l++; while (a[r] > pivotVal) r--; if (l == r ) break; if (l < r) { swap(a[l++] ,a[r--]); } } return r; }
非比较类排序
计数排序(Counting Sort)
计数排序要求输入的数据必须是有确定范围的整数。将输入的数据作为key存储在额外的数组中，然后依次把计数大于1的填充回原数组
时间复杂度O(N+M)，N为元素个数，M为数值范围
桶排序( Bucket Sort)
桶排序假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能使用别的排序算法，或是以递归方式继续使用桶排序)
时间复杂度O(N)~o(N^2)
基数排序（Radix Sort)
基数排序把数据切割成一位位数字（O-9)，从低位到高位对每一位分别进行计数排序时间复杂度O(NK)，K为数字位数
排序的稳定性
对于序列中存在的若干个关键字相等的元素
如果排序前后它们的相对次序一定保持不变，就称排序算法是稳定的否则就称排序算法是不稳定的
插入、冒泡、归并、计数、基数和桶排序是稳定的
选择、希尔、快速、堆排序是不稳定的
排序阵营九宫格
实战
912.排序数组
https://leetcode.cn/problems/sort-an-array/
class Solution { public: vector<int> sortArray(vector<int>& nums) { heap_sort(nums,nums.size()); //quickSort(nums ,0 ,nums.size() - 1); //sort(nums.begin(),nums.end()); return nums; } void heap_sort(vector<int>& a, int n) { priority_queue<int> q; for(int i = 0; i < n; i++) { q.push(-a[i]); } for(int i = 0; i < n; i++) { a[i] = -q.top(); q.pop(); } } void quickSort(vector<int>& arr, int l, int r) { if (l >= r) return; int pivot = partition(arr, l, r); quickSort(arr, l, pivot); quickSort(arr, pivot + 1, r); } int partition(vector<int>& a, int l, int r) { int pivot = l + rand() % (r - l + 1); int pivotVal = a[pivot]; while (l <= r) { while (a[l] < pivotVal) l++; while (a[r] > pivotVal) r--; if (l == r ) break; if (l < r) { swap(a[l++] ,a[r--]); } } return r; } };
class Solution { public int[] sortArray(int[] nums) { //mergeSort(nums,0 ,nums.length - 1); quickSort(nums,0 ,nums.length - 1); return nums; } // void heap_sort(int a[], int n) { // priority_queue<int> q; // for(int i = 0; i < n; i++) { // q.push(-a[i]); // } // for(int i = 0; i < n; i++) { // a[i] = -q.top(); // q.pop(); // } // } public static void mergeSort(int[] arr, int l, int r) { // sort arr[l..r] if (l >= r) return; int mid = (l + r) >> 1; // (l + r) / 2 mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // int i = left, j = mid + 1; for (int k = 0; k < temp.length; k++) { // if (j > right || (i <= mid && arr[i] <= arr[j])) temp[k] = arr[i++]; else temp[k] = arr[j++]; } for (int k = 0; k < temp.length; k++) { // arr[left + k] = temp[k]; } } public static void quickSort(int[] arr, int l, int r) { if (l >= r) return; int pivot = partition(arr, l, r); quickSort(arr, l, pivot); quickSort(arr, pivot + 1, r); } static int partition(int[] a, int l, int r) { int pivot = l + (int)(Math.random() * (r - l + 1)); int pivotVal = a[pivot]; while (l <= r) { while (a[l] < pivotVal) l++; while (a[r] > pivotVal) r--; if (l == r) break; if (l < r) { int temp = a[l]; a[l] = a[r]; a[r] = temp; l++; r--; } } return r; } }
1122.数组的相对排序
https://leetcode.cn/problems/relative-sort-array/
比较类排序
- 利用哈希表对arr2建立数值到索引的映射
- 自定义比较函数
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { unordered_map<int, int> arr2orders; for (int i = 0;i < arr2.size(); i++) { arr2orders[arr2[i]] = i; } sort(arr1.begin(), arr1.end(), [&](int x, int y) { int xPos = arr2orders.find(x) != arr2orders.end() ? arr2orders[x] : arr2.size(); int yPos = arr2orders.find(y) != arr2orders.end() ? arr2orders[y] : arr2.size(); return xPos < yPos || (xPos == yPos && x < y); }); return arr1; } };
非比较类排序计数排序
- 第一遍把计数数组中出现在arr2的数值填充回arr1
- 第二遍把剩下的填充回arr1
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { vector<int> count(1001, 0); for (int val : arr1) { count[val]++; } vector<int> ans; for (int val : arr2) { while (count[val] > 0) { ans.push_back(val); count[val]--; } } for (int val = 0; val <= 1000; val++) { while (count[val] > 0) { ans.push_back(val); count[val]--; } } return ans; } };
56.合并区间
https://leetcode.cn/problems/merge-intervals/
方法一:对区间进行双关键字排序（左右端点)
然后扫描合并（排序后能合并的区间一定是连续的)
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]); }); vector<vector<int>> ans; int farthest = -1; int start = -1; for(const vector<int>& intervals : intervals) { int left = intervals[0]; int right = intervals[1]; if (left <= farthest) { farthest = max(farthest,right); }else { if (farthest != -1) { ans.push_back({start, farthest}); } start = left; farthest = right; } } ans.push_back({start, farthest}); return ans; } };
方法二:差分思想、关键事件思想
把每个区间[lr]看作一次+1的覆盖，进一步转化为“l处+1”、“r+1处-1”两个事件
把2n个事件排序、扫描，用一个计数变量记录覆盖次数，0变1、1变0时就找到了合并后的区间端点
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<pair<int, int>> events; for (const vector<int>& interval : intervals) { events.push_back({interval[0], 1}); events.push_back({interval[1] + 1, -1}); } sort(events.begin(), events.end()); int covering = 0; int start; vector<vector<int>> ans; for (const pair<int, int>& event : events) { if (covering == 0) start = event.first; covering += event.second; if (covering == 0) { ans.push_back({start, event.first - 1}); } } return ans; } };
215.数组中的第K个最大元素
https://leetcode.cn/problems/kth-largest-element-in-an-array/
class Solution { public: int findKthLargest(vector<int>& nums, int k) { // sort(nums.begin(), nums.end()); // return nums[nums.size() - k]; return quickSort(nums, 0, nums.size() - 1, nums.size() - k); } private: int quickSort(vector<int>& arr, int l, int r, int index) { if (l >= r) return arr[l]; int pivot = partition(arr, l, r); if (index <= pivot) return quickSort(arr, l, pivot, index); else return quickSort(arr, pivot + 1, r, index); } int partition(vector<int>& a, int l, int r) { int pivot = l + rand() % (r - l + 1); int pivotVal = a[pivot]; while (l <= r) { while (a[l] < pivotVal) l++; while (a[r] > pivotVal) r--; if (l == r) break; if (l < r) { swap(a[l++], a[r--]); } } return r; } };
104.货仓选址
https://www.acwing.com/problem/content/description/106/
在一条数轴上有N家商店，它们的坐标分别为A~An。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。1 ≤N≤ 100000
#include<bits/stdc++.h> using namespace std; int a[100005]; int main() { int n; long long ans = 0; cin >> n; for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); int pos = a[n / 2]; for (int i = 0; i< n; i++) ans += abs(pos - a[i]); cout << ans << endl; }
493.翻转对
https://leetcode.cn/problems/reverse-pairs/
class Solution { public int reversePairs(int[] nums) { ans = 0; mergeSort(nums, 0, nums.length - 1); return ans; } void mergeSort(int[] arr, int l, int r) { // sort arr[l..r] if (l >= r) return; int mid = (l + r) >> 1; // (l + r) / 2 mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); calculate(arr, l, mid ,r); merge(arr, l, mid, r); } void calculate(int[] arr, int left, int mid, int right) { int j = mid; for (int i = left; i <= mid; i++) { while (j < right && arr[i] > 2l * arr[j + 1]) j++; ans += j - mid; } } void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // int i = left, j = mid + 1; for (int k = 0; k < temp.length; k++) { // if (j > right || (i <= mid && arr[i] <= arr[j])) temp[k] = arr[i++]; else temp[k] = arr[j++]; } for (int k = 0; k < temp.length; k++) { // arr[left + k] = temp[k]; } } int ans; }
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
