C++ 计数排序、归并排序、快速排序

计数排序：是一种基于哈希的排序算法。他的基本思想是通过统计每个元素的出现次数，然后根据统计结果将元素依次放入排序后的序列中。这种排序算法适用于范围较小的情况，例如整数范围在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];}
};