常用的排序算法(二)

这篇具有很好参考价值的文章主要介绍了常用的排序算法(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

四、归并排序(Merge Sort)

归并排序的时间复杂度为O(nlogn),在使用递归程序时,其额外空间复杂度为O(nlogn)

归并排序使用了一种叫做分而治之(Divide and conquer)的策略,将原本很庞大的数组排序问题分割成更小的子问题,在每一个子问题得到解决后,再合并它们。下面我们以数组arr[8]={9,2,4,6,3,0,8,7}为例,研究归并排序的解决思路:

我们首先将数组对半分开。分成两个大小为4的数组:

9 2 4 6 3 0 8 7

然后将大小为4的数组分开,分成大小为2的数组:

9 2 4 6 3 0 8 7

最后分成大小为1的数组,这样,每一个数组都保持有序(单一数据必有序)

9 2 4 6 3 0 8 7

接下来,我们要处理的便是将两个有序的子数组合并为一个有序数组的问题:

我们另外取一个例子,将arr1[4]={2,5,6,8}和arr2[4]={1,3,7,9}合并为大小为8的有序数组:

常用的排序算法(二),排序算法,算法,数据结构

我们新开一个数组,大小为两个数组大小的和。维护3个指针i,j,k,分别指向arr1,arr2和新开数组的首地址。因为两个数组有序,所以所有数字的最小值一定在arr1[i]和arr2[j]中取到。我们只需比较arr1[i]和arr2[j]的大小,若arr1[i]较小,则将arr1[i]的值赋值给merge_arr[k],随后i右移,k右移即可。当然,arr2[j]较大的情况也是同理。

常用的排序算法(二),排序算法,算法,数据结构

当其中一个数组遍历完后,另外一个数组还没有被遍历完,只需要把没有遍历完的数组剩余的元素平移至merge_arr中的剩余空位中即可。

常用的排序算法(二),排序算法,算法,数据结构

用上面的方法,我们就可以将两个有序的数组合并成一个有序的数组。

归并排序,就是拆分-合并的思路。

代码实现:

#include<stdio.h>
void Merge(int* arr,int start,int mid,int end){//合并两个有序数组
    if(start>=end){
        return;
    }
    int i=start;int j=mid+1;
    int k=0;//维护3个指针
    int size=end-start+1;
    int tmp[size];//新开一个数组,用来存放归并后的元素
    while(i<=mid&&j<=end){
        if(arr[i]<=arr[j]){
            tmp[k]=arr[i];
            i++;
            k++;
        }
        else{
            tmp[k]=arr[j];
            j++;
            k++;
        }
    }
    if(i==mid+1){
        while(j<=end){
            tmp[k]=arr[j];
            k++;
            j++;
        }
    }
    else if(j==end+1){
        while(i<=mid){
            tmp[k]=arr[i];
            i++;
            k++;
        }
    }//平移剩余元素
    k=0;
    i=start;
    while(i<=end){
        arr[i++]=tmp[k++];
    }//将归并后的元素一一赋值回原数组中
}
void Merge_Sort(int * arr,int start,int end){
    if(start>=end)return;
    int mid=(start+end)/2;//二分策略
    Merge_Sort(arr, start, mid);
    Merge_Sort(arr,mid+1,end);//左右两个数组依次归并
    Merge(arr,start,mid,end);//合并两个有序数组
}
int main(){
    int numsSize;
    scanf("%d",&numsSize);
    if(numsSize<=0){
        return 0x7fffffff;
    }//非法输入,直接返回
    int arr[numsSize];
    for(int i=0;i<numsSize;i++){
        scanf("%d",&arr[i]);
    }
    Merge_Sort(arr,0,numsSize-1);
    for(int i=0;i<numsSize;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

在归并排序的逻辑下,每一次问题的规模都会减半。于是递归的深度为O(logn),同一深度的递归所处理的元素个数之和为O(n)(因为数组的大小是固定的,你只是把它拆成一块一块的,或者两半,或者四部分,等等,但是加起来还是那么多数。这里停下来好好想一想),总的时间复杂度为O(nlogn)。

每个递归函数都要占用它排序的两个子数组的空间之和(因为它要开一个新的数组)。在递归结束之前,所有未执行完的函数所占用的额外空间都不会被释放。所以额外的空间复杂度为O(nlogn)。

其实,用循环代替递归是实现归并排序的一个好办法,它可以将空间复杂度降到O(n),这个知识点不再涉及。(我不会

五、快速排序(Quick Sort)

快速排序的平均时间复杂度为O(nlogn),最坏时间复杂度为O(n^2),递归程序中每次执行都要花费常数时间复杂度(用于交换元素),空间复杂度O(logn).

快速排序可以借助C语言的内置函数qsort()来实现,需要包含 stdlib.h 头文件。

qsort函数原型为:qsort(void* _Base,size_t_NumofElement,Size_OfElements, int (*_PtFuncCompare)(const void*,const void*))

一共有4个参数,第一个为要排序的数组,第二个为数组中待排元素的个数,第三个是数组中元素所占的字节数,第四个是表示排序原则的函数(递增还是递减)。

代码实现:

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b){
    return *(int*)a-*(int*)b;
}
int main(){
    int numsSize;
    scanf("%d",&numsSize);
    int arr[numsSize];
    for(int i=0;i<numsSize;i++){
        scanf("%d",&arr[i]);
    }
    qsort(arr,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;i++){
        printf("%d ",arr[i]);
    }
}

 当然,仅仅掌握快速排序的代码实现是不够的。快速排序也借助了分而治之的思想,但快速排序是借助数组中的一个“主元”将数组中的元素拆分成为两部分:一部分比它小,另一部分比它大。然后对两部分再次进行上述操作。

我们借助int arr[11]={7, 13,4,6,5,2,11,15,0,3,8}研究快速排序的逻辑原理:

常用的排序算法(二),排序算法,算法,数据结构

我们默认选取最后一个元素为主元,维护双指针i,j,分别指向arr[0]和arr[10](除去主元之外最后的元素),将i后移动找到第一个比主元大的数13,然后固定i,向前移动j找到第一个比主元小的元素3,然后互换arr[i]和arr[j]。然后再后移i,找到11,前移j,找到0,互换......重复以上步骤,直到i,j相遇,然后交换arr[i]和主元,得到主元在中,小的在左边,大的在右边的序列,然后对主元两侧的部分递归(类似归并)。

这里要留下一个问题:在题设条件下,可不可以先挪j再挪i?为什么?

如果主元选在第一个,那么应该先挪哪个?为什么?

代码实现:(自己写的,可能没那么快 bushi)

#include<stdio.h>
void change(int*x,int*y){
    int tmp=*x;
    *x=*y;
    *y=tmp;
}
void quick_sort(int* arr,int start,int end){
    if(start>=end) return;//递归出口
    if(end==start+1){
        if(arr[end]<arr[start]){
            change(&arr[start],&arr[end]);
        }
        return;
    }
    int i=start;int j=end;
    while(1){
        while(i<j&&arr[i]<=arr[end]){
            i++;
        }
        while(i<j&&arr[j]>=arr[end]){
            j--;
        }
        if(i>=j) break;
        change(&arr[i],&arr[j]);
    }
    change(&arr[i],&arr[end]);
    quick_sort(arr,start,i-1);
    quick_sort(arr,i+1,end);
}
int main(){
    int numsSize;
    scanf("%d",&numsSize);
    if(numsSize<=0) return 0x7fffffff;
    int arr[numsSize];
    for(int i=0;i<numsSize;i++){
        scanf("%d",&arr[i]);
    }
    quick_sort(arr,0,numsSize-1);
    for(int i=0;i<numsSize;i++){
        printf("%d ",arr[i]);
    }
}

这里我们研究快排的时间复杂度。快排就一定快吗?我们能否构建一种最坏情况?让快排变得很慢?其实是可以的。我们只需要让每次快排的主元(在上述情况下就是数组中最后面的值)取到整个数组的最大或者最小就好了。这样数组就无法“对半”或者“均匀”的切开,每次快排只能减少一个元素,就需要O(n)的递归深度。此时的时间复杂度就是O(n^2)。

对于这种情况,我们可以采取随机取主元的方法来解决这个问题。这里不再涉及。文章来源地址https://www.toymoban.com/news/detail-824718.html

到了这里,关于常用的排序算法(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(49)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(71)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(81)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(76)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(62)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(57)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(83)
  • 数据结构与算法-排序算法

    递归将整个函数的调用过程 调用过程 如何在CSDN博客中插入公式和各种符号 类似二叉树的后续遍历 递归行为和递归行为时间复杂度的估算 master 公式 : T ( n ) = a × T ( n b ) + O ( n d ) T(n) = a times T (frac{n}{b}) + O(n^d) T ( n ) = a × T ( b n ​ ) + O ( n d ) T ( n ) T(n) T ( n ) : 母问题的规模

    2024年02月15日
    浏览(51)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包