计数排序：是一种基于哈希的排序算法。他的基本思想是通过统计每个元素的出现次数，然后根据统计结果将元素依次放入排序后的序列中。这种排序算法适用于范围较小的情况，例如整数范围在0到k之间
计数排序步骤：1 初始化一个长度为最大元素值加1的计数数组，所有元素初始化为0
2 遍历原始数组，将每个元素值作为索引，在计数数组中对应位置加1
3 将数组清空
4 遍历计数器数组，按照数组中的元素个数放回到元数组中
计数排序的优点和缺点：计数排序在小范围内的话，还是非常高效的。元素范围大的话，空间开销会变大（时间复杂度为0(n+k)）
代码练习 1 对应力扣 颜色分类，代码见下
class Solution {
public:
void countingSort(vector<int>& a, int m){
int n = a.size();
int *count = new int[m+1];
memset(count, 0, sizeof(int)*(m+1));
for(int i=0; i<n; ++i){
count[a[i]]++;
}
int idx = 0;
for(int v = 0; v <= m; ++v){
while(count[v] > 0){
a[idx++] = v;
count[v]--;
}
}
delete []count;
}
void sortColors(vector<int>& nums) {
countingSort(nums, 3);
}
};归并排序：主要目的是将两个已排序的序列合并成一个有序序列。归并排序有以下步骤，
1 计算中点，mid = (l + r) / 2
2 递归调用mergeSort(a[], l, mid) 和 mergeSort(a[], mid+1, r)
3 第2步中两个数组进行有序合并，在存储到a[l, r]
调用时，调用mergeSort(a, 0, n-1),就可以得到整个的排序结果了
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，归并排序的优点是稳定，相对顺序不会发生变化，并且可拓展性很强，可以便捷的整合到并行环境中，通过并行归并来提高效率。缺点便是需要额外的空间来存储归并后的结果，实现相对比较复杂。
代码练习 1 对应力扣，排序数组，代码见下
class Solution {
void merge(vector<int>& a, int l, int m, int r){
int n1 = m - l + 1;
int n2 = r - m;
int temp[n1 + n2];
for(int i=0; i<n1; ++i){
temp[i] = a[l + i];
}
for(int j = 0; j<n2; ++j){
temp[n1+j] = a[m + 1 + j];
}
int i=0, j=n1, k=l;
while(i < n1 && j < n1+n2){
if(temp[i] <= temp[j]){
a[k++] = temp[i++];
}else{
a[k++] = temp[j++];
}
}
while(i < n1){
a[k++] = temp[i++];
}
while(j < n1+n2){
a[k++] = temp[j++];
}
}
void mergeSort(vector<int>& a, int l, int r){
if(l >= r){
return;
}
int m = (l + r)/2;
mergeSort(a, l, m);
mergeSort(a, m+1, r);
merge(a, l, m, r);
}
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size()-1);
return nums;
}
};代码练习 2 对应力扣，排序链表，代码见下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
ListNode* mergeSort(ListNode* a, ListNode* b){
a = sortList(a);
b = sortList(b);
ListNode* head = new ListNode();
ListNode* tail = head;
while(a || b){
if(a == NULL){
tail->next = b;
break;
}else if(b == NULL){
tail->next = a;
break;
}else if(a->val < b->val){
tail->next = a;
a = a->next;
}else{
tail->next = b;
b = b->next;
}
tail = tail->next;
tail->next = NULL;
}
return head->next;
}
public:
ListNode* sortList(ListNode* head) {
if(head == NULL){
return NULL;
}else if(head->next == NULL){
return head;
}
ListNode* fast = head;
ListNode* slow = head;
ListNode* prev = NULL;
while(fast){
prev = slow;
slow = slow -> next;
fast = fast -> next;
if(fast){
fast = fast->next;
}
}
prev->next = NULL;
return mergeSort(head, slow);
}
};快速排序是一种分而治之的算法。她通过选一个基准元素，将数组分为两部分，一部分元素都比基准小，另一部分的元素都比基准大，然后对这两部分进行快速排序
算法步骤：
1 选择基准元素，从数组中选择一个元素作为基准
2 分割数组：选择基准小的元素放在基准的左边，比基准大的放在基准右边
3 递归排序：对基准左边和右边的子数组分别进行快速排序
时间复杂度，最快的时间复杂度为O(nlogn)，最坏情况的时间复杂度为O(n^2)，最坏情况是选择的基准元素是最大或最小元素值
空间复杂度：快速排序的空间复杂度为O(logn)，因为在递归调用过程中，需要通过栈来存储元素。
算法的优点是：在大多数情况下有着不错的效率、适用于各种数据的排序、不需要额外的存储空间（原地排序）。
算法的缺点是：最坏的情况，时间复杂度会很高，另外的话，数组是不稳定的，可能会改变相对顺序。
代码练习 1，对应力扣 存在重复元素，代码见下：
class Solution {
int Partition(vector<int>& a, int l, int r){
int idx = l + rand() % (r - l + 1);
swap(a[l], a[idx]);
int i = l, j = r;
int x = a[i];
while(i < j){
while(i < j && a[j] > x){
j--;
}
if(i < j){
swap(a[i], a[j]), ++i;
}
while(i < j && a[i] < x){
i++;
}
if(i < j){
swap(a[i], a[j]), --j;
}
}
return i;
}
void QuickSort(vector<int>& a, int l, int r){
if(l > r){
return;
}
int proix = Partition(a, l, r);
QuickSort(a, l, proix-1);
QuickSort(a, proix+1, r);
}
public:
bool containsDuplicate(vector<int>& nums) {
int n = nums.size();
QuickSort(nums, 0, n-1);
for(int i = 1; i < n; ++i){
if(nums[i] == nums[i-1]){
return true;
}
}
return false;
}
};代码 2 对应力扣，多数元素 代码见下
class Solution {
int Partition(vector<int>& a, int l, int r){
int idx = l + rand() % (r - l + 1);
swap(a[l], a[idx]);
int i = l, j = r;
int x = a[i];
while(i < j){
while(i < j && a[j] > x){
j--;
}
if(i < j){
swap(a[i], a[j]), ++i;
}
while(i < j && a[i] < x){
i++;
}
if(i < j){
swap(a[i], a[j]), --j;
}
}
return i;
}
void QuickSort(vector<int>& a, int l, int r){
if(l > r){
return;
}
int proix = Partition(a, l, r);
QuickSort(a, l, proix-1);
QuickSort(a, proix+1, r);
}
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
QuickSort(nums, 0, n-1);
return nums[n/2];
}
};