测试用题：https://leetcode-cn.com/problems/sort-an-array/
这题O(n2)复杂度的排序算法应该是都过不了的，不过可以用来测试下实现的对不对。
体会：写排序算法的时候，脑子里想图形用箭头表示下标，直接记一连串的下标有时会因为想不清楚而出现一些错误。
选择排序。每次选出最大值（最小值）放到前面，每次选择的时候可以从未排好序的地方开始查找最大值（最小值），依次选出最大值 即可得出结果。时间复杂度O(n2)，实际的话每一次查找需要查找的范围是依次递减的，均摊复杂度的话还是更小些，计算就不算了。
class Solution {public:void selectSort(vector<int> &nums){int len = nums.size();for(int i = 0; i < len - 1; i++){int res = i;for(int j = i + 1; j < len; j++){if(nums[j] < nums[res]){res = j;}}swap(nums[i], nums[res]);}}vector<int> sortArray(vector<int>& nums) {selectSort(nums);return nums;}};
冒泡排序。后者比前者小，则进行交换，这样一来，每一轮从头到尾的扫描，就会把最大的放到末尾，重复n-1次即可比较所有，完成排序。优化，未发生交换时则已经排好序，结束。
void bbSort(vector<int> &nums){ int len = nums.size(); bool f = false; for(int i = 0; i < len - 1; i++){ f = true; for(int j = 1; j < len - i; j++){ if(nums[j] < nums[j - 1]){ f = false; swap(nums[j], nums[j - 1]); } } if(f)break; } }插入排序。每次往前（前面一部分是排好序的，证明稍微想想就明白）找到一个合适位置插入。
附加题：https://leetcode-cn.com/problems/insertion-sort-list/
void insertSort(vector<int> & nums){
int len = nums.size();
for(int i = 1; i < nums.size(); i++){
int val = nums[i];
int j;
for(j = i - 1; j >= 0 && nums[j] > val; j--){
nums[j + 1] = nums[j];
}
nums[j + 1] = val;
}
}
附加题实现（链表问题一定要画图，思路并不难，看了下别人的题解，基本思路也一样，链表遍历只能从头结点开始）：
/**
* 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 {
public:
ListNode* insertionSortList(ListNode* head) {
if(head->next == nullptr)return head;
ListNode *pre, *p, *cur, *nxt;
// 直接从第二个开始，方便处理边界
cur = head->next;
head->next = nullptr;
while(cur){
p = head;
pre = nullptr;
nxt = cur->next;
cur->next = nullptr;
while(p){
if(p->val >= cur->val){
if(pre == nullptr){
head = cur;
}else{
pre->next = cur;
}
cur->next = p;
break;
}
if(p->next == nullptr){
p->next = cur;
p = p->next;
}
pre = p;
p = p->next;
}
cur = nxt;
}
return head;
}
};
归并排序。递归分支。(NLogN复杂度上面那题能过了)
class Solution { public: void mergeArray(vector<int> &nums, int l1, int r1, int l2, int r2){ int cnt = (r1 - l1 + 1) + (r2 - l2 + 1); vector<int> buf(cnt); int k = 0; int s1 = l1, e1 = r1, s2 = l2, e2 = r2; while(l1 <= r1 && l2 <= r2){ if(nums[l1] < nums[l2]){ buf[k++] = nums[l1++]; }else { buf[k++] = nums[l2++]; } } while(l1 <= r1)buf[k++] = nums[l1++]; while(l2 <= r2)buf[k++] = nums[l2++]; k = 0; for(int i = s1; i <= e1; i++){ nums[i] = buf[k++]; } for(int i = s2; i <= e2; i++){ nums[i] = buf[k++]; } } void mergeSort(vector<int> &nums, int left, int right){ if(left >= right){ return; } int mid = (left + right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); mergeArray(nums, left, mid, mid + 1, right); } vector<int> sortArray(vector<int>& nums) { mergeSort(nums, 0, nums.size() - 1); return nums; } };还可进行的优化：
- 合并两个数组时开辟的临时空间，可以全程使用一个公共空间，达到空间的优化
对于小区间使用插入排序，这个好像起不到优化的作用。
对于下面这个优化，似乎并不是正确的，比如递归回溯的两个部分分别为2 5 和 3 4，这个时候不进行合并就是错的。
附加题：
剑指 Offer 51. 数组中的逆序对
这道题想明白思路就很简单，只需要在原来归并排序的代码上加上几行代码即可完成。
思路：每次合并到的两个数组（必定是有序的，证明稍微想想就能明白），当后一个数据取出一个值放到结果数组中，那么前一个数组中还剩余的数一定是大于这个数的，也就是前一个数组中剩余的数的个数就是逆序对的数量，每次将后一个数组中的数放到结果数组中时就可以直接算出逆序对的数量，累加即可得到答案。
代码实现：
class Solution {
public:
int ans = 0;
void mergeArray(vector<int> &nums, int l1, int r1, int l2, int r2){
int cnt = (r1 - l1 + 1) + (r2 - l2 + 1);
vector<int> buf(cnt);
int k = 0;
int s1 = l1, s2 = l2, e1 = r1, e2 = r2;
while(l1 <= r1 && l2 <= r2){
if(nums[l1] <= nums[l2]){
buf[k++] = nums[l1++];
}else{
ans += r1 - l1 + 1;
buf[k++] = nums[l2++];
}
}
while(l1 <= r1)buf[k++] = nums[l1++];
while(l2 <= r2)buf[k++] = nums[l2++];
k = 0;
for(int i = s1; i <= e1; i++){
nums[i] = buf[k++];
}
for(int i = s2; i <= e2; i++){
nums[i] = buf[k++];
}
}
void mergeSort(vector<int> &nums, int l, int r){
if(l >= r){
return;
}
int mid = (l + r) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
mergeArray(nums, l, mid, mid + 1, r);
}
int reversePairs(vector<int>& nums) {
mergeSort(nums, 0, nums.size() - 1);
return ans;
}
};
附加题2：
https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
- 快速排序
想明白就很简单了，每次维护一个基准（该基准实际就是小于基准值的末位置下标），保证基准左边都是比基准值小的，右边都是比基准值大的。
优化：
选取一个随机基准，快速排序在对一个有序序列进行处理时，时间复杂度将达到On2的复杂度。 ```cpp class Solution { public: int partion(vector
&nums, int l, int r, int pivot){ swap(nums[l], nums[pivot]); int j = l, i = l + 1; for(; i <= r; i++){ if(nums[i] < nums[l]){ swap(nums[++j], nums[i]); } } swap(nums[l], nums[j]); return j;}
void qsort(vector
&nums, int l, int r){ if(l >= r)return; srand((int)time(0)); int pivot = rand() % (r - l + 1) + l; int p = partion(nums, l, r, pivot); qsort(nums, l, p - 1); qsort(nums, p + 1, r);}
vector<int> sortArray(vector<int>& nums) {
qsort(nums, 0, nums.size() - 1);
return nums;
}
}; ```
若有收获，就点个赞吧
0 人点赞
