排序算法

八大算法>排序算法 | 爱编程的大丙 (subingwen.cn)

冒泡排序

best: O(n), worst O(n^2)
* 数组的相邻两个元素进行比较：nums[i] > nums[i+1] -> swap(nums[i], nums[i+1])
* 一次遍历后，最大元素移至数组末尾

* n长度数组，进行n-1次排序，每次排序遍历的数组长度-1

选择排序

* best: O(n^2), worst: O(n^2)
* -将数组分为已排序部分与未排序部分（初始为空）
* -遍历未排序部分，找到当前的max元素坐标 --> max_index
* -将nums[max_index]与未排序部分的第一个元素nums[head_index]交换 --> swap(nums[max_index], nums[head_index])
* -n长度数组，进行n-1次排序，每次排序遍历后，未排序数组的长度-1，即遍历起始点+1

插入排序

* best: O(n), worst：O(n^2)
* -将数组分为已排序部分与未排序部分（初始为数组头元素）
* -每次排序，取未排序部分的头元素tmp=nums[i] 从已排序部分的末尾nums[j]=nums[i-1]开始遍历比较
* if tmp < nums[j], nums[j+1]=num[j]
* else if tmp <= nums[j], nums[j+1]=tmp
* n长度的数组，要n次排序，每次排序后，未排序数组长度-1，遍历起始点+1

希尔排序（优化-分组插入排序）

* best: O(n), worst：O(n^2)
* -step1.将原数组分为间隔为gap的数组
* eg: [1, 2, 3, 4, 5] --> [1*, 2, 3* ,4, 5*] 原数组以gap=2,分为两个交叉数组
* -step2.各分组数组内进行插入排序(在已排序部分比较时，以gap移位)
* -step3.逐步缩小gap至1，进行一次gap=1的插入排序

快排（递归分支-二叉树前序递归）

*best：O(nlogn) , worst：O(n^2)

* 分治思想：大问题拆分为小问题
* -在数组中随机选择一个数作为当前数组的基准mid(eg:mid=nums[left])
* -通过双指针(left=nums_begin,right=nums_end)：将数组分为[小于基准部分, mid, 大于基准部分]
* -递归：继续分治[小于基准部分],[大于基准部分] (until 分支数组元素为1)

归并排序（递归分支-二叉树后序递归）

* best: O(nlogn), worst: O(nlogn)
* -先将数组按中间点mid=(left+right)>>1拆分为两个子数组
* -压栈：递归重复上一步，直至子数组元素为1
* -出栈：在当前递归层，有序合并两个有序子数组[left, mid-1]与[mid, right]
* -回到初始层级时，整个数组即有序

class Solution {
public:/* 1. 冒泡   ** best: O(n), worst O(n^2)* -数组的相邻两个元素进行比较：nums[i] > nums[i+1] -> swap(nums[i], nums[i+1])* -一次遍历后，最大元素移至数组末尾* -n长度数组，进行n-1次排序，每次排序遍历的数组长度-1*/void pubble_sort(vector<int>& nums){// 排序次数for(int i=0; i<nums.size()-1; i++){int swap_flag = false;// 未排序部分逐个比较->swapfor(int j=0; j<nums.size()-i-1; j++){if( nums[j] > nums[j+1] ){swap(nums[j], nums[j+1]);swap_flag = true;}}if(!swap_flag){break; }}}/* 2.选择  ** best: O(n^2), worst: O(n^2)* -将数组分为 已排序部分 与 未排序部分（初始为空）* -遍历未排序部分，找到当前的max元素坐标 --> max_index* -将nums[max_index]与未排序部分的第一个元素nums[head_index]交换 --> swap(nums[max_index], nums[head_index])* -n长度数组，进行n-1次排序，每次排序遍历后，未排序数组的长度-1，即遍历起始点+1*/void select_sort(vector<int>& nums){int tmp_index;// 排序次数for(int i=0; i<nums.size()-1; i++){tmp_index = i;// 未排序部分比较->find min/max -> 与未排序部分的1st元素swapfor(int j=i+1; j<nums.size(); j++){tmp_index = nums[tmp_index] > nums[j] ? j : tmp_index;}if(tmp_index != i)swap(nums[tmp_index], nums[i]);}}/* 3. 插入排序-1 ** best: O(n), worst：O(n^2)* -将数组分为 已排序部分 与 未排序部分（初始为数组头元素）* -每次排序，取未排序部分的头元素tmp=nums[i] 从已排序部分的末尾nums[j]=nums[i-1]开始遍历比较*    if tmp < nums[j], nums[j+1]=num[j] *    else if tmp <= nums[j], nums[j+1]=tmp* n长度的数组，要n次排序，每次排序后，未排序数组长度-1，遍历起始点+1*/void insert_sort(vector<int>& nums){// 未排序部分 gap=1for(int i=1; i<nums.size(); i++){int tmp = nums[i];int j = i - 1;// 已排序部分while(j>=0 && nums[j] > tmp){nums[j+1] = nums[j];j--;}nums[j+1] = tmp;}}/*4. 希尔排序-优化的插入排序  ** best: O(n), worst：O(n^2)* -step1.将原数组分为间隔为gap的数组*    eg:  [1, 2, 3, 4, 5]  --> [1*, 2, 3* ,4, 5*]   原数组以gap=2,分为两个交叉数组* -step2.各分组数组内进行插入排序(在已排序部分比较时，以gap移位)* -step3.逐步缩小gap至1，进行一次gap=1的插入排序*/void shell_sort(vector<int>& nums){// 以gap分组for(int gap=nums.size()/2; gap>0; gap/=2){// 未排序部分for(int i=gap; i<nums.size(); i++){int tmp = nums[i];int j=i-gap;// 已排序部分while(j>=0 && nums[j]>tmp){nums[j+gap] = nums[j];j -= gap;}nums[j+gap] = tmp;}}}/*5. 快排（递归分治-二叉树前序递归） ** best：O(nlogn) , worst：O(n^2)* 分治思想：大问题拆分为小问题* -在数组中随机选择一个数作为当前数组的基准mid(eg:mid=nums[left])* -通过双指针(left=nums_begin,right=nums_end)：将数组分为[小于基准部分, mid, 大于基准部分]* -递归：继续分治[小于基准部分],[大于基准部分] (until 分支数组元素为1)*/void quick_sort(vector<int>& nums, int left, int right){//if(left >= right) return;//int mid = nums[left];int begin=left, end=right;while(left < right){while(left < right && nums[right] >= mid) right--;if(left!=right) nums[left] = nums[right];while(left < right && nums[left] <= mid) left++;if(left!=right) nums[right] = nums[left];}nums[left] = mid;quick_sort(nums, begin, left-1);quick_sort(nums, right+1, end);}/* 6.归并排序 （递归分支-二叉树后序递归）* best: O(nlogn), worst: O(nlogn)* -先将数组按中间点mid=(left+right)>>1拆分为两个子数组* -压栈：递归重复上一步，直至子数组元素为1* -出栈：在当前递归层，有序合并两个有序子数组[left, mid-1]与[mid, right]* -回到初始层级时，整个数组即有序*/void merge_sort(vector<int>& nums, int left, int right){if(left >= right) return ;// 递归分组int mid = (right + left) >> 1;merge_sort(nums, left, mid);merge_sort(nums, mid+1, right);// 有序合并当前层的2个有序数组[left, mid-1]与[mid, right]int l = left, r = mid+1;vector<int> tmp;while(l<=mid && r<=right){if(nums[l] < nums[r]) tmp.push_back(nums[l++]);else tmp.push_back(nums[r++]);}while(l <= mid) tmp.push_back(nums[l++]);while(r <= right) tmp.push_back(nums[r++]);for(int i=left, k=0; i<=right; i++,k++){nums[i] = tmp[k];}}vector<int> sortArray(vector<int>& nums) {quick_sort(nums, 0, nums.size()-1);return nums;}
};

(归并排序)以O(nlogn）时间复杂度解决链表排序问题

148. 排序链表 - 力扣（LeetCode）

step1.快慢指针找到链表的中间节点

step2.归并排序：有序合并两个链表数组

/*** 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 {
private:// 合并两个链表ListNode* merge(ListNode* list1, ListNode* list2){ListNode* dummyHead = new ListNode(0);ListNode* cur = dummyHead;while(list1 && list2){if(list1->val < list2->val){cur->next = list1;list1 = list1->next;}else{cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return dummyHead->next;}// 归并排序ListNode* merge_sort(ListNode* head, ListNode* end){// 叶节点if(head == nullptr) return head;if(head->next == end){head->next = nullptr;return head;}// find 链表中间结点ListNode* fast = head, *slow = head;while(fast != end){fast = fast->next;slow = slow->next;if(fast != end) fast = fast->next;}ListNode* mid = slow;// 分组// ListNode* list_left = merge_sort(head, mid);// ListNode* list_right = merge_sort(mid, end);// 有序mergereturn merge(merge_sort(head, mid),  merge_sort(mid, end));}
public:ListNode* sortList(ListNode* head) {return merge_sort(head, nullptr);}
};