标签：fas   ast   快速   算法   using   条件   ==   荷兰国旗问题   空间   

常用的排序算法总结

交换排序

冒泡排序

通过数组相邻两个数之间的比较和位置的交换，使得关键字最小的记录如气泡一样冒出水面

#include 
using namespace std;

const int N = 100010;
int n;
int a[N];

void bubble_sort(int a[], int n)
{
    for(int i = 0; i  i; j--)
        {
            if(a[j] > n;
    for(int i = 0; i > a[i];
    
    bubble_sort(a, n);
    for(int i = 0; i 

快速排序

每次从待排序的数字中选择一个数字（基准），将其插入到数组合适的位置中。左边的数都比它小，右边都比它大。在对左右两边的元素执行相同的操作，直到整个数组有序。

容易出错的点：

26行，边界[l, j] [j + 1, r]

19行，do while循环不是if

#include 

using namespace std;

const int N = 100010;
int a[N];
int n;

void quick_sort(int a[], int l, int r)
{
    //递归终止条件
    if(l >= r) return ;
    //选择基准
    int x = a[(r + l) >> 1], i = l - 1, j = r + 1;
    //将基准插入到合适的位置  双指针 i在头部  j在尾部
    while(i  x);
        //交换两个元素的位置
        if(i > n;
    for(int i = 0; i > a[i];
    quick_sort(a, 0, n - 1);
    for(int i = 0; i 

归并排序

将多个有序的数组合并到一起

容易写错的地方：

1. 20行，循环的终止条件
2. 31行，边界[l,r]

#include 
using namespace std;
const int N = 100010;
int q[N];
int a[N];
int n;

void merge_sort(int a[], int l, int r)
{
    //递归终止条件
    if(l >= r) return ;
    //确定分界点，排序左右两边
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
    //合并两个有序数组
    int k = 0;
    //i和j分别是每个数组的起点
    int i = l, j = mid + 1;
    
    while(i > n;
    for(int i = 0; i > a[i];
    
    merge_sort(a, 0, n - 1);
    
    for(int i = 0; i 

选择排序

每次从待排序的记录中选出关键字最小的记录，顺序放到以及那个排好序的数组的最后，直到全部排完。

直接选择排序

#include 

using namespace std;

const int N = 100010;

int a[N];
int n;

void select_sort(int a[], int n)
{
    for(int i = 0; i  a[j]) k = j;
        //将最小的数交换到有序区
        if(k != i) swap(a[k], a[i]);
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i > a[i];
    
    select_sort(a, n);
    
    for(int i = 0; i 

堆排序

插入排序

每次将待排序中的一个记录，按照其关键字大小插入到前面已经排好序的子表的适当位置，直到全部记录插入完成为止。

直接插入排序

#include 

using namespace std;

const int N = 100010;

int a[N];
int n;

void insert_sort(int a[], int n)
{
    for(int i = 1; i = 0 && tmp > n;
    for(int i = 0; i > a[i];
    
    insert_sort(a, n);
    
    for(int i = 0; i 

折半插入排序

利用二分查找找出插入位置

#include 

using namespace std;

const int N = 100010;

int a[N];
int n;

void mid_insert_sort(int a[], int n)
{
    for(int i = 1; i > 1;
            if(tmp = r + 1; j--)
            a[j + 1] = a[j];
        a[r + 1] = tmp;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i > a[i];
    
    mid_insert_sort(a, n);
    
    for(int i = 0; i 

希尔排序

1. 取一个小于n的整数d1作为第一个增量，将数组分成d1个组，索引为d1的倍数的数放在同一个组，在各组内进行直接插入排序
2. 取第二个增量d2，重复上述分组和排序，直到dt = 1;所有数在同一组进行直接插入排序为止；

#include 

using namespace std;

const int N = 100010;

int a[N];
int n;

void shell_insert(int a[], int n)
{
    int gap = n / 2;
    while(gap > 0)
    {
        //对所有索引相距gap位置的所有元素进行排序
        for(int i = gap; i = 0 && tmp > n;
    for(int i = 0; i > a[i];
    
    shell_insert(a, n);
    
    for(int i = 0; i 

计数排序

统计数组中每个值i出现的次数，存入数组C的第i项；根据C[i]的值，整理排序结果

基数排序

STL中Sort的用法

剑指offer

45. 把数组排成最小的数

题目链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

class Solution {
public:
    string minNumber(vector& nums) {
        auto compare = [](string &sa, string &sb){return sa + sb  tmp;
        for(auto n: nums) tmp.push_back(to_string(n));

        sort(tmp.begin(), tmp.end(), compare);
        string ans = "";
        for(auto s:tmp) ans += s;
        return ans; 
    }
};

51. 数组中的逆序对

题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

暴力解法

简直太暴力

class Solution {
public:
    int reversePairs(vector& nums) {
        int res = 0;
        for(int i = 0; i  nums[j]) res++;
            }
        }
        return res;
    }
};

归并排序

分治的思想

class Solution {
public:

    int merge_sort(vector &nums, int l, int r)
    {
        if(l >= r) return 0;
        int mid = ( l + r) >> 1;
        long long res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);

        
        
        int k = 0; 
        int i = l, j = mid + 1;
        /*合并两个有序数组*/
        vector tmps(r - l + 1);
        while(i & nums) {
        return merge_sort(nums, 0, nums.size() - 1);
    }
};

61. 扑克牌中的顺子

题目链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

class Solution {
public:
    bool isStraight(vector& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i 

leetcode

56. 合并区间

题目链接：https://leetcode-cn.com/problems/merge-intervals/submissions/

class Solution {
public:
    vector> merge(vector>& intervals) {
        //所有区间按照left排序
        //比较区间的右端点r1和下一个区间l2的做端点，
        //如果r1 > res;
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i 

75. 颜色分类（荷兰国旗问题）

题目链接：https://leetcode-cn.com/problems/sort-colors/

p0 0的最右边位置 p2 2的最左边 cur当前元素。

初始化: p0 = 0 p2 = n - 1 cur = 0

沿着cur遍历数组，若nums[cur] = 0，将其与nums[p0]交换；若nums[cur] = 2，将其与nums[p2]交换

时间复杂度为O(n)

空间复杂度为O(1)

class Solution {
public:
    void sortColors(vector& nums) {
    // 对于所有 idx  p2 : nums[idx > p2] = 2
    // curr 是当前考虑元素的下标
        int p0 = 0, cur = 0, p2 = nums.size() - 1;
        while(cur 

148. 排序链表

题目链接：https://leetcode-cn.com/problems/sort-list/

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* pre = head, *slow = head, *fast = head;
        while(fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        return mergeTwoList(sortList(head), sortList(slow));
    }
    ListNode* mergeTwoList(ListNode* h1, ListNode* h2) {
        if(!h1) return h2;
        if(!h2) return h1;
        if(h1->val val) {
            h1->next = mergeTwoList(h1->next, h2);
            return h1;
        }
        else {
            h2->next = mergeTwoList(h1, h2->next);
            return h2;
        }
    }
};

253. 会议室II

题目链接：https://leetcode-cn.com/problems/meeting-rooms-ii/

排序

1. 分别将开始时间和结束时间存进两个数组。
2. 分别对开始时间和结束时间进行排序。请注意，这将打乱开始时间和结束时间的原始对应关系。它们将被分别处理。
3. 考虑两个指针：st_idx 和 end_idx ，分别代表开始指针和结束指针。开始指针遍历每个会议，结束指针帮助我们跟踪会议是否结束。
4. 当考虑 st_idx 指向的特定会议时，检查该开始时间是否大于 end_idx 指向的会议。若如此，则说明 st_idx 开始时，已经有会议结束。于是我们可以重用房间。否则，我们就需要开新房间。
5. 若有会议结束，换而言之，start[st_idx] >= end[end_idx ] ，则自增 end_idx 。
6. 重复这一过程，直到st_idx处理完所有会议。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution {
public:
    int minMeetingRooms(vector>& intervals) {
        if(intervals.empty()) return 0;

        int res = 0;
        int len = intervals.size();

        vector start, end;
        for(int i = 0; i = end[end_idx])
            {
                res -= 1;
                end_idx += 1;
            }
            res += 1;
            st_idx += 1;
        }
        return res;
    }
};

215. 数组中的第K个最大元素

题目链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

快速排序

class Solution {
public:
    void quick_sort(vector &nums, int l, int r)
    {
        if(l >= r) return;
        
        int x = nums[(l + r) >> 1], i = l - 1, j = r + 1;

        while(i  x);
            do j--; while(nums[j] & nums, int k) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums[k - 1];
    }
};

堆排序

借助STL

class Solution {
public:
    int findKthLargest(vector& nums, int k)
    {
        priority_queue, greater> pq;
        for (auto& n : nums)
        {
            if (pq.size() >= k && pq.top() >= n) continue;
            pq.push(n);
            if (pq.size() > k)
            {
                pq.pop();
            }
        }
        return pq.top();
    }

};

自己实现down

class Solution {
public:
    void down(vector& a, int u, int n)
    {
        int t = u;
        if(u * 2  a[t]) t = u * 2;
        if(u * 2 + 1  a[t]) t = u * 2 + 1;
        if(u != t) swap(a[u], a[t]), down(a, t, n);
    }

    int findKthLargest(vector& nums, int k) {
        int n = nums.size();
        nums.push_back(nums[0]);

        for(int i = n/2; i; i--) down(nums, i, n);

        int m = n;
        int res = 0;
        while(m-- && k--)
        {
            cout 

【算法】排序问题总结

标签：fas   ast   快速   算法   using   条件   ==   荷兰国旗问题   空间   

原文地址：https://www.cnblogs.com/Trevo/p/12987496.html