草庐IT

【排序算法】归并排序与快速排序

林 子 2023-04-11 原文

       🔥🔥 欢迎来到小林的博客！！
      🛰️博客主页：✈️小林爱敲代码
      🛰️博客专栏：✈️ 算法训练笔记
      🛰️社区 :✈️ 进步学堂
      🛰️欢迎关注：👍点赞🙌收藏✍️留言

前言

今天给大家分享两种排序，一种是快排，一种是归并。它们的时间复杂度都是 O(n * logn)，而归并要求的空间复杂度是O(N)。归并具有稳定性，快排不具备稳定性。

快速排序

快速排序我们需要借助一个key值，我们拿升序排序来举例。 我们在数组中随机取一个key值，随后用两个指针，一个指针从最左端开始。另一个指针从最右端开始，左指针先走，遇到比key大的值停下。随后右指针也相继往前走，遇到小于key的值停下。随后交换这两个值，走完一遍就完成了单趟排序，随后我们再把这段数组分割成两部分重复以上步骤。我们的key值就取数组的中间值。

随后我们再把数组从 key值所在的下标划分为两半，继续重复先前的步骤，最后即可完成排序。

快排代码模板：

#include<iostream>
using namespace std;

const int N = 1e6;
int q[N];
int n;

void sort_quick(int q[],int l , int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1,x = q[(l+r)/2];
    while(i < j)
    {
        do i++;while(q[i] < x); //找到的值>= x
        do j--;while(q[j] > x); //找到的值<= x
        if(i<j) swap(q[i],q[j]);//两个值进行交换
    }
    sort_quick(q,l,j); // l - j这段区间继续排
    sort_quick(q,j+1,r); // j + 1 - r这段区间继续排
}
int main()
{
    scanf("%d",&n);
    for(int i = 0 ;i < n ; i++) scanf("%d",&q[i]);
    sort_quick(q,0,n-1);
    for(int i = 0 ;i < n ; i++) printf("%d ",q[i]);
    return 0;
}

归并排序

归并排序，我们需要额外借助一个和排序数组一样长的tmp数组。然后取一个mid点，为数组的中点，数组的l - mid 为一个区域， mid + 1 - r 为一个区域。对这两个区域的值进行比较，把较小(降序取较大)的值放入tmp数组中。而归并的情况必须保证2个数组是有序的，所以我们先递归，再归并。递归的最后一层只有2个数进行比较。

归并排序前半部分过程：

后面半部分和前面半部分逻辑完全相同。到最后一次归并的时候，我们就可以保证mid左右两边是有序的。

最后一次归并时的数组：

最后一次归并过程：

归并排序代码模板：

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int n;
int q[N],tmp[N];

void Merge_sort(int q[],int l ,int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    Merge_sort(q,l,mid),Merge_sort(q,mid+1,r); //先对左右两边进行归并
    int i = l,j = mid + 1, k = 0;
    while(i <= mid && j <= r) //有一边到达末尾结束循环
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++]; //如果 i - mid 数组中还有元素，放进tmp
    while(j <= r) tmp[k++] = q[j++]; //如果 j - r 数组中还有元素，放进tmp
    for( i = l , j = 0; i <= r ; i++,j++)q[i] = tmp[j]; //把tmp里的元素导进数组
}


int main()
{   
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++) scanf("%d",q+i);
    Merge_sort(q,0,n-1);
    for(int i = 0 ; i < n ; i++) printf("%d ",q[i]);
    return 0;
}

总结：

归并排序和快速排序思想相同，只不过归并排序有严格mid点，必须从中间开始分裂。而快排不需要，快排只需要把两个坐标相遇的点当成划分点即可。相比于快排，归并的空间复杂度更高，因为需要一个额外的数组来存储排序后的值。而归并的稳定性也是优于快排，归并是稳定的，而快排是不稳定的。

排序归并排序quotspanclass

有关【排序算法】归并排序与快速排序的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  2. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  3. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  4. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  5. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

  6. ruby - 如何以表格格式快速打印 Ruby 哈希值？ - 2

    有没有办法快速将表格格式的ruby​​哈希打印到文件中？如:keyAkeyBkeyC...1232343451253474456...其中散列的值是不同大小的数组。还是使用双循环是唯一的方法？谢谢 最佳答案 试试我写的这个gem(在表中打印散列、ruby对象、ActiveRecord对象):http://github.com/arches/table_print 关于ruby-如何以表格格式快速打印Ruby哈希值？，我们在StackOverflow上找到一个类似的问题：

  7. ruby-on-rails - 如何对对象数组进行排序？ - 2

    我有一个对象如下:[{:id=>2,:fname=>"Ron",:lname=>"XXXXX",:photo=>"XXX"},{:id=>3,:fname=>"Dain",:lname=>"XXXX",:photo=>"XXXXXXX"},{:id=>1,:fname=>"Bob",:lname=>"XXXXXX",:photo=>"XXXX"}]我想按fname排序，不区分大小写，所以它会导致编号:1,3,2我该如何排序？我正在尝试:@people.sort!{|x,y|y[:fname]x[:fname]}但这没有任何效果。 最佳答案

  8. ruby - 使用自定义排序首选项对数组进行排序？ - 2

    有人可以告诉我如何根据自定义字符串对嵌套数组进行排序吗？比如有没有办法排序:[['Red','Blue'],['Green','Orange'],['Purple','Yellow']]“橙色”、“黄色”，然后是“蓝色”？最终结果如下所示:[['Green','Orange'],['Purple','Yellow'],['Red','Blue']]它不是按字母顺序排序的。我很想知道我是否可以定义要排序的值以实现上述目标。 最佳答案 sort_by对于这种排序总是非常方便:a=[['Red','Blue'],['Green','Ora

  9. Ruby 将对象插入现有的已排序对象数组 - 2

    我有以下现有的Dog对象数组，它们按age属性排序:classDogattr_accessor:agedefinitialize(age)@age=ageendenddogs=[Dog.new(1),Dog.new(4),Dog.new(10)]我现在想插入一条新的狗记录，并将它放在数组中的正确位置。假设我想插入这个对象:another_dog=Dog.new(8)我想把它插入到数组中，让它成为数组中的第三项。这是一个人为的示例，旨在演示我特别想如何将一个项目插入到现有的有序数组中。我意识到我可以创建一个全新的数组并重新对所有对象进行排序，但这不是我的目标。谢谢!

  10. ruby - 如何排序不是简单的哈希(哈希的哈希) - 2

    我有一个这样的哈希{55=>{:value=>61,:rating=>-147},89=>{:value=>72,:rating=>-175},78=>{:value=>64,:rating=>-155},84=>{:value=>90,:rating=>-220},95=>{:value=>39,:rating=>-92},46=>{:value=>97,:rating=>-237},52=>{:value=>73,:rating=>-177},64=>{:value=>69,:rating=>-167},86=>{:value=>68,:rating=>-165},53=>{:va

随机推荐