安科网

【算法】排序问题总结

Oudasheng

Oudasheng

2020-05-29

关注 关注

常用的排序算法总结

交换排序

冒泡排序

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

#include <iostream>
using namespace std;

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

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


int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    bubble_sort(a, n);
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
        
    return 0;
    
}

快速排序

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

容易出错的点：

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

19行，do while循环不是if

#include <iostream>

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 < j)
    {
        //i一直往后移动，直到找到第一个大于等于x的数 
        do i++; while(a[i] < x);  
        //j一直往后移动，直到找到第一个小于等于x的数
        do j--; while(a[j] > x);
        //交换两个元素的位置
        if(i < j) swap(a[i], a[j]);
    }
    //递归处理左右两边 边界问题，容易出错
    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    quick_sort(a, 0, n - 1);
    for(int i = 0; i < n; i++) cout <<a[i] <<" ";
    cout << endl;
    return 0;
}

归并排序

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

容易写错的地方：

  1. 20行，循环的终止条件
  2. 31行，边界[l,r]
#include <iostream>
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 <= mid && j <= r)
    {
        if(a[i] < a[j]) q[k++] = a[i++];
        else q[k++] = a[j++];
    }
    //处理未排序完的
    while(i <= mid) q[k++] = a[i++];
    while(j <= r) q[k++] = a[j++];
    
    //将排好序的结果放到a中 
    //合并的范围是从[l, r]，所以将q中的数组放到a[l, r]的位置上
    for(int i = l, k = 0; i <= r; i++, k++) a[i] = q[k];
}


int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    merge_sort(a, 0, n - 1);
    
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

选择排序

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

直接选择排序

#include <iostream>

using namespace std;

const int N = 100010;

int a[N];
int n;

void select_sort(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        int k = i; // 有序区的终点
        //每次挑选无序区最小的
        for(int j = i + 1; j < n; j++)
            if(a[k] > a[j]) k = j;
        //将最小的数交换到有序区
        if(k != i) swap(a[k], a[i]);
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    select_sort(a, n);
    
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    
    return 0;
    
}

堆排序

插入排序

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

直接插入排序

#include <iostream>

using namespace std;

const int N = 100010;

int a[N];
int n;

void insert_sort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        //无序区首个元素
        int tmp = a[i];
        int j = i - 1;
        //将无序区的第一个元素插入到有序区合适的位置
        while(j >= 0 && tmp < a[j]) a[j + 1] = a[j], j--;
        a[j + 1] = tmp;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    insert_sort(a, n);
    
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    
    return 0;
    
}

折半插入排序

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

#include <iostream>

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 < n; i++)
    {
        int tmp = a[i]; //无序区第一个元素
        int l = 0, r = i - 1;
        //使用二分确定要插入的位置
        while(l <= r) 
        {
            int mid = (l + r) >> 1;
            if(tmp < a[mid]) r = mid - 1;
            else l = mid + 1;
        }
        //顺序移动进行插入
        for(int j = i - 1; j >= r + 1; j--)
            a[j + 1] = a[j];
        a[r + 1] = tmp;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    mid_insert_sort(a, n);
    
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    
    return 0;
    
}

希尔排序

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

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 < n; i++)
        {
            int tmp = a[i];
            int j = i - gap;
            while(j >= 0 && tmp < a[j])
            {
                a[j + gap] = a[j];
                j = j - gap;
            }
            a[j + gap] = tmp;
            j -= gap;
        }
        gap /= 2;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    shell_insert(a, n);
    
    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    
    return 0;
    
}

计数排序

统计数组中每个值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<int>& nums) {
        auto compare = [](string &sa, string &sb){return sa + sb < sb + sa;};
        vector<string> 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<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(nums[i] > nums[j]) res++;
            }
        }
        return res;
    }
};

归并排序

分治的思想

class Solution {
public:

    int merge_sort(vector<int> &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<int> tmps(r - l + 1);
        while(i <= mid && j <= r)
        {
            if(nums[i] <= nums[j])  tmps[k++] = nums[i++];
            else 
            {
                tmps[k++] = nums[j++];
                //由于两个数组目前都有序，所以逆序对的个数 = 第一个数组的i之后的元素个数 mid - i + 1
                res += mid - i + 1;
            }
        }
        while(i <= mid ) tmps[k++] = nums[i++];
        while(j <= r) tmps[k++] = nums[j++];
        for(int i = l, k = 0; i <= r; i++, k++) nums[i] = tmps[k];
        return res;
    }
    int reversePairs(vector<int>& 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<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); i++)
            if(nums[i] && nums[i] == nums[i - 1])
                return false;
        
        for(auto x : nums)
            if(x) return nums.back() - x <= 4;
        
        return false;
    }
};

leetcode

56. 合并区间

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //所有区间按照left排序
        //比较区间的右端点r1和下一个区间l2的做端点，
        //如果r1 < l2, 合并
        //否则，插入数组
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < intervals.size(); i++)
        {
            int l = intervals[i][0], r = intervals[i][1];
            if(!res.size() || res.back()[1] < l) res.push_back({l, r});
            else res.back()[1] = max(res.back()[1], r);
        }
        return res;
    }
};

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<int>& nums) {
    // 对于所有 idx < p0 : nums[idx < p0] = 0
    // 对于所有 idx > p2 : nums[idx > p2] = 2
    // curr 是当前考虑元素的下标
        int p0 = 0, cur = 0, p2 = nums.size() - 1;
        while(cur <= p2)
        {
            if(nums[cur] == 0) swap(nums[cur++], nums[p0++]);
        //因为curr左边的值已经扫描过了，所以curr要++继续扫描下一位，而与p2交换的值，curr未扫描，要停下来扫描一下，所以curr不用++。
            else if(nums[cur] == 2) swap(nums[cur], nums[p2--]);
            else 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 < h2->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<vector<int>>& intervals) {
        if(intervals.empty()) return 0;

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

        vector<int> start, end;
        for(int i = 0; i < len; i++)
        {
            start.push_back(intervals[i][0]);
            end.push_back(intervals[i][1]);
        }
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int st_idx = 0, end_idx = 0;
        while(st_idx < len)
        {
            if(start[st_idx] >= 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<int> &nums, int l, int r)
    {
        if(l >= r) return;
        
        int x = nums[(l + r) >> 1], i = l - 1, j = r + 1;

        while(i < j)
        {
            do i++; while(nums[i] > x);
            do j--; while(nums[j] < x);
            if(i < j) swap(nums[i], nums[j]);
        }

        quick_sort(nums, l, j);
        quick_sort(nums, j + 1, r);
    }
    int findKthLargest(vector<int>& nums, int k) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums[k - 1];
    }
};

堆排序

借助STL

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int, vector<int>, greater<int>> 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<int>& a, int u, int n)
    {
        int t = u;
        if(u * 2 <= n && a[u * 2] > a[t]) t = u * 2;
        if(u * 2 + 1 <= n && a[u * 2 + 1] > a[t]) t = u * 2 + 1;
        if(u != t) swap(a[u], a[t]), down(a, t, n);
    }

    int findKthLargest(vector<int>& 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 << nums[1] << " ";
            res = nums[1];
            nums[1] = nums[n];
            n--;
            down(nums, 1, n);
        }
        cout << endl;
        return res;
    }
};

排序算法总结

Oudasheng

Oudasheng

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

排序算法总结

int[] p = partition;//等于区域的左边界和右边界

troysps 2020-06-05

常用排序算法总结（基于算法 第四版）

，其中每个元素有个主键，将主键按照某种方式排列。在java中元素通常都是对象，对主键描述往往通过comparable接口。即先找出最小元素调整位置，往复。private static boolean isSorted {//检测是否有序。public st

shawsun 2020-01-12

算法之排序算法总结

这样比较一趟，可以把最大的数放在末尾。依次循环，直到排序完成。算法思想: 分解：1.将一个数组分成两个数组。

清溪算法 2019-12-06

前端的排序算法总结

典型的排序方法，命名来自鱼呼吸时吹出的气泡，上层的气泡总是最大的。思路：两层循环，内层循环对比相邻两个数据，假设j > j + 1则交换元素位置。外层循环为长度限制，在内层第一次循环完成后减少长度1. 加一个标志位flag，如果没有进行交换，将标志位

YUAN 2019-11-17

三、排序算法总结（C++版本）

　　对于各种排序算法也算是有了一定的了解，所以这里做一个总结。这是比较经典的排序算法，主要是通过内外两层的循环比较，使得乱序变为顺序。cout << "the number is " << L[j] <&l

lixiaotao 2019-11-15

各种排序算法总结

排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。今天，来总结下各种排序算法。冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间

风和日丽 2019-11-03

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

HeavyIndustry 2014-11-25

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

风吹夏天 2014-04-07

八大排序算法总结

先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。

WalkMoreSlowly 2012-10-25

排序算法总结

冒泡排序是一种简单的排序方法，算法如下：1.首先将所有待排序的数字放入工作列表中。用C语言实现如下：

rioalian 2017-07-13

排序算法总结

内部排序以下为基于比较的排序。第一个元素已经是有序序列，然后比较外围的元素和序列的最后一个元素，判断是否需要插入，如果小，则插入。时间复杂度：最优 O 最差 O(n^2)是否稳定：是public void insertSort {. 不过在交换时需要注

算法改变人生 2019-06-27

常用排序算法总结

排序定义排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。输入：n个数：a1,a2,a3,…,an输出：n个数的排列:a1’,a2’,a3’,…,an’，使得a1’<=a2’<=a3’<=…关于时

代码之神 2019-06-27

部分排序算法总结

关于排序通常所说的排序是指内部排序，即在内存里进行排序。相对应的有外部排序，当待排序数据比较多时，排序过程需要使用闪存。排序算法大体可分为两种：一种是比较排序，时间复杂度O ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序

代码之神 2019-06-25

Java排序算法总结（八）：基数排序

基数排序则是属于“分配式排序”，基数排序法又称“桶子法”或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O ，其中r为所采取的基数，而m为堆数，在某些时

韦一笑 2011-04-20

Java排序算法总结（七）：快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序

hang0 2011-04-20

Java排序算法总结（六）：堆排序

堆积排序是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O， 最坏时间复杂度为O，堆排序的堆序的平均性能较接近于最坏性能。堆排序利用了大根堆堆顶记录的关键字最大(或最小)这

WindChaser 2011-04-20

Java排序算法总结（五）：归并排序

归并排序是将两个有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序

hugebawu 2011-04-20

Java排序算法总结（四）：希尔排序

希尔排序 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O的额外空间，时间复杂度为O。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。

RememberMePlease 2011-04-20

Java排序算法总结（三）：冒泡排序

冒泡排序是计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O，但是有两个优点：。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大则交换两数。

MrA 2011-04-20

Java排序算法总结（二）：选择排序

选择排序的基本操作就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。算法不稳定，O的额外的空间，比较的时间复杂度为O(n^2)，交换的时间复杂度为O，并不是自适应的。在大多数情况下都不推

韦一笑 2011-04-20
Oudasheng

Oudasheng

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号