自学内容网 自学内容网

排序 算法

八大排序算法 | 爱编程的大丙 (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;
            // 未排序部分逐个比较->swap
            for(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元素swap
            for(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=1
        for(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);
        // 有序merge
        return merge(merge_sort(head, mid),  merge_sort(mid, end));
    }
public:
    ListNode* sortList(ListNode* head) {
        return merge_sort(head, nullptr);
    }
};


原文地址:https://blog.csdn.net/qq_43855258/article/details/141267831

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!