• 10-千奇百怪的排序算法

    千奇百怪的排序算法

    排序算法分类

    基于比较的排序
    通过比较大小来决定元素间的相对次序
    可以证明时间复杂度下界为O(NlogN)——不可能突破这个复杂度达到更快

    非比较类排序
    不通过比较大小来决定元素间的相对次序
    时间复杂度受元素的范围以及分布等多种因素影响，不单纯取决于元素数量N

    请添加图片描述

    基于比较的排序

    初级排序算法

    选择排序(Selection Sort)——“该放哪个数了?“
    每次从未排序数据中找最小值，放到已排序序列的末尾

    插入排序(Insertion Sort)——“这个数该放哪儿?”
    从前到后依次考虑每个未排序数据，在已排序序列中找到合适位置插入

    冒泡排序（Bubble Sort)
    不断循环扫描，每次查看相邻的元素，如果逆序，则交换

    平均时间复杂度均为O(N2)

    堆排序

    堆排序(Heap Sort)是对选择排序的优化——利用二叉堆高效地选出最小值
    建立一个包含所有N个元素的二叉堆
    重复N次从堆中取出最小值，即可得到有序序列
    时间复杂度O(NlogN)

    void heap_sort(vector<int>& a, int n) {
        priority_queue<int> q;
        
        for(int i = 0; i < n; i++) { 
            q.push(-a[i]);
        }
        for(int i = 0; i < n; i++) { 
            a[i] = -q.top();
            q.pop();
        } 
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    希尔排序 (不太重要)

    希尔排序(Shell Sort)是对插入排序的优化——增量分组插入排序

    希尔排序的时间复杂度取决于增量序列（步长序列)的选取目前已知的最好序列可以做到o(N4/3)或o(Nlog2N)

    归并排序

    归并排序(Merge Sort)是一个基于分治的算法
    时间复杂度O(NlogN)

    原问题:把数组排序
    子问题:把数组前一半、后一半分别排序
    然后再合并左右两半（两个有序数组）就可以了

    public static void mergeSort(int[] arr, int l, int r) { // sort arr[l..r]
        if (l >= r) return;
        int mid = (l + r) >> 1; // (l + r) / 2
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; //
        int i = left, j = mid + 1;
        for (int k = 0; k < temp.length; k++) { //
        if (j > right || (i <= mid && arr[i] <= arr[j]))
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) { //
            arr[left + k] = temp[k];
        } 
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    快速排序

    快速排序(Quick Sort)也是一个基于分治的算法

    • 从数组中选取中轴元素pivot
    • 将小元素放在pivot左边，大元素放在右边
    • 然后分别对左边和右边的子数组进行快排

    快速排序和归并排序具有相似性，但步骤顺序相反

    • 归并排序:先排序左右子数组，然后合并两个有序数组
    • 快速排序:先调配出左右子数组，然后对左右子数组分别进行排序

    随机选取pivot，期望时间复杂度O(NlogN)

    快速排序可以通过适当的交换来原地实现数组调配，避免占用额外空间最经典和高效的调配方式叫作 Hoare Partition

    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;
        int pivot = partition(arr, l, r);
        quickSort(arr, l, pivot);
        quickSort(arr, pivot + 1, r);
    }

    static int partition(int[] a, int l, int r) {
        int pivot = l + (int)(Math.random() * (r - l + 1));
        int pivotVal = a[pivot];
        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r) break;
            if (l < r) {
                int temp = a[l]; a[l] = a[r]; a[r] = temp;
                l++; 
                r--; 
            } 
        }
        return r;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    void quickSort(vector<int>& arr, int l, int r) {
        if (l >= r) return;
        int pivot = partition(arr, l, r);
        quickSort(arr, l, pivot);
        quickSort(arr, pivot + 1, r);
    }

    int partition(vector<int>& a, int l, int r) {
        int pivot = l + rand() % (r - l + 1);
        int pivotVal = a[pivot];

        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r ) break;
            if (l < r) {
                swap(a[l++] ,a[r--]);
            }
        }

        return r;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    非比较类排序

    计数排序(Counting Sort)
    计数排序要求输入的数据必须是有确定范围的整数。将输入的数据作为key存储在额外的数组中，然后依次把计数大于1的填充回原数组
    时间复杂度O(N+M)，N为元素个数，M为数值范围

    桶排序( Bucket Sort)
    桶排序假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能使用别的排序算法，或是以递归方式继续使用桶排序)
    时间复杂度O(N)~o(N^2)

    基数排序（Radix Sort)
    基数排序把数据切割成一位位数字（O-9)，从低位到高位对每一位分别进行计数排序时间复杂度O(NK)，K为数字位数

    排序的稳定性

    对于序列中存在的若干个关键字相等的元素

    如果排序前后它们的相对次序一定保持不变，就称排序算法是稳定的否则就称排序算法是不稳定的
    插入、冒泡、归并、计数、基数和桶排序是稳定的
    选择、希尔、快速、堆排序是不稳定的

    排序阵营九宫格

    在这里插入图片描述

    实战

    912.排序数组
    https://leetcode.cn/problems/sort-an-array/

    class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heap_sort(nums,nums.size());
        //quickSort(nums ,0 ,nums.size() - 1);
        //sort(nums.begin(),nums.end());
        return nums;
    }

    void heap_sort(vector<int>& a, int n) {
        priority_queue<int> q;
        
        for(int i = 0; i < n; i++) { 
            q.push(-a[i]);
        }
        for(int i = 0; i < n; i++) { 
            a[i] = -q.top();
            q.pop();
        } 
    }

    void quickSort(vector<int>& arr, int l, int r) {
        if (l >= r) return;
        int pivot = partition(arr, l, r);
        quickSort(arr, l, pivot);
        quickSort(arr, pivot + 1, r);
    }

    int partition(vector<int>& a, int l, int r) {
        int pivot = l + rand() % (r - l + 1);
        int pivotVal = a[pivot];

        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r ) break;
            if (l < r) {
                swap(a[l++] ,a[r--]);
            }
        }

        return r;
    }
    
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    class Solution {
    public int[] sortArray(int[] nums) {

        //mergeSort(nums,0 ,nums.length - 1);
        quickSort(nums,0 ,nums.length - 1);
        return nums;
    }

    

    // void heap_sort(int a[], int n) {
    //     priority_queue q;
    //     for(int i = 0; i < n; i++) { 
    //         q.push(-a[i]);
    //     }
    //     for(int i = 0; i < n; i++) { 
    //         a[i] = -q.top();
    //         q.pop();
    //     } 
    // }

    public static void mergeSort(int[] arr, int l, int r) { // sort arr[l..r]
        if (l >= r) return;
        int mid = (l + r) >> 1; // (l + r) / 2
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; //
        int i = left, j = mid + 1;
        for (int k = 0; k < temp.length; k++) { //
        if (j > right || (i <= mid && arr[i] <= arr[j]))
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) { //
            arr[left + k] = temp[k];
        } 
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) return;
        int pivot = partition(arr, l, r);
        quickSort(arr, l, pivot);
        quickSort(arr, pivot + 1, r);
    }

    static int partition(int[] a, int l, int r) {
        int pivot = l + (int)(Math.random() * (r - l + 1));
        int pivotVal = a[pivot];
        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r) break;
            if (l < r) {
                int temp = a[l]; a[l] = a[r]; a[r] = temp;
                l++; 
                r--; 
            } 
        }
        return r;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    1122.数组的相对排序

    https://leetcode.cn/problems/relative-sort-array/

    比较类排序

    • 利用哈希表对arr2建立数值到索引的映射
    • 自定义比较函数
    class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> arr2orders;
        for (int i = 0;i < arr2.size(); i++) {
            arr2orders[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            int xPos = arr2orders.find(x) != arr2orders.end() ? arr2orders[x] : arr2.size();
            int yPos = arr2orders.find(y) != arr2orders.end() ? arr2orders[y] : arr2.size();
            return xPos < yPos || (xPos == yPos && x < y);
        });
        return arr1;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    非比较类排序计数排序

    • 第一遍把计数数组中出现在arr2的数值填充回arr1
    • 第二遍把剩下的填充回arr1
    class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> count(1001, 0);
        for (int val : arr1) {
            count[val]++;
        }
        vector<int> ans;
        for (int val : arr2) {
            while (count[val] > 0) {
                ans.push_back(val);
                count[val]--;
            }
        }
        for (int val = 0; val <= 1000; val++) {
            while (count[val] > 0) {
                ans.push_back(val);
                count[val]--;
            }
        }
        return ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    56.合并区间
    https://leetcode.cn/problems/merge-intervals/

    方法一:对区间进行双关键字排序（左右端点)
    然后扫描合并（排序后能合并的区间一定是连续的)

    class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(),
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
            });
        vector<vector<int>> ans;
        int farthest = -1;
        int start = -1;
        for(const vector<int>& intervals : intervals) {
            int left = intervals[0];
            int right = intervals[1];
            if (left <= farthest) {
                farthest = max(farthest,right);
            }else {
                if (farthest != -1) {
                    ans.push_back({start, farthest});
                }
                start = left;
                farthest = right;
            }
        }
        ans.push_back({start, farthest});
        return ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    方法二:差分思想、关键事件思想
    把每个区间[lr]看作一次+1的覆盖，进一步转化为“l处+1”、“r+1处-1”两个事件
    把2n个事件排序、扫描，用一个计数变量记录覆盖次数，0变1、1变0时就找到了合并后的区间端点

    class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> events;
        for (const vector<int>& interval : intervals) {
            events.push_back({interval[0], 1});
            events.push_back({interval[1] + 1, -1});
        }
        sort(events.begin(), events.end());
        int covering = 0;
        int start;
        vector<vector<int>> ans;
        for (const pair<int, int>& event : events) {
            if (covering == 0) start = event.first;
            covering += event.second;
            if (covering == 0) {
                ans.push_back({start, event.first - 1});
            }
        }
        return ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    215.数组中的第K个最大元素
    https://leetcode.cn/problems/kth-largest-element-in-an-array/

    class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // sort(nums.begin(), nums.end());
        // return nums[nums.size() - k];
        return quickSort(nums, 0, nums.size() - 1, nums.size() - k);
    }
private:
    int quickSort(vector<int>& arr, int l, int r, int index) {
        if (l >= r) return arr[l];
        int pivot = partition(arr, l, r);
        if (index <= pivot) return quickSort(arr, l, pivot, index);
        else return quickSort(arr, pivot + 1, r, index);
    }

    int partition(vector<int>& a, int l, int r) {
        int pivot = l + rand() % (r - l + 1);
        int pivotVal = a[pivot];

        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r) break;
            if (l < r) {
                swap(a[l++], a[r--]);
            }
        }
        return r;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    104.货仓选址
    https://www.acwing.com/problem/content/description/106/

    在一条数轴上有N家商店，它们的坐标分别为A~An。
    现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
    为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。1 ≤N≤ 100000

    #include
using namespace std;

int a[100005];

int main() {
    int n;
    long long ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    int pos = a[n / 2];
    for (int i = 0; i< n; i++) ans += abs(pos - a[i]);
    cout << ans << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    493.翻转对
    https://leetcode.cn/problems/reverse-pairs/

    class Solution {
    public int reversePairs(int[] nums) {
        ans = 0;
        mergeSort(nums, 0, nums.length - 1);
        return ans;
    }
    
    void mergeSort(int[] arr, int l, int r) { // sort arr[l..r]
        if (l >= r) return;
        int mid = (l + r) >> 1; // (l + r) / 2
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        calculate(arr, l, mid ,r);
        merge(arr, l, mid, r);
    }

    void calculate(int[] arr, int left, int mid, int right) {
        int j = mid;
        for (int i = left; i <= mid; i++) {
            while (j < right && arr[i] > 2l * arr[j + 1]) j++;
            ans += j - mid;
        }
    }

    void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; //
        int i = left, j = mid + 1;
        for (int k = 0; k < temp.length; k++) { //
        if (j > right || (i <= mid && arr[i] <= arr[j]))
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) { //
            arr[left + k] = temp[k];
        } 
    }

    int ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

  • 相关阅读:
    LabVIEW对Table中同一行数据分多次增加
    druid在springboot中如何整合配置！
    【小5聊】使用div+css布局绘制32支球队比赛对阵图，拭目以待冠军花落谁家
    记录一些使用的工具
    JavaScript作用域的用法
    智慧公厕：提升城市形象的必备利器
    vue2 element手术麻醉信息系统源码，手术预约、手术安排、排班查询、手术麻醉监测、麻醉记录单
    计算机服务器中了locked勒索病毒怎么解密，locked勒索病毒解密流程
    基于Java+SpringBoot+vue前后端分离小徐影城管理系统设计实现
    【课程】SP Module2 辅音和元音的声学
  • 原文地址：https://blog.csdn.net/qq_46118239/article/details/126223276