0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

C语言动图演示十大经典排序算法(含代码)

jf_BxU6dNQb 来源:混说Linux 2023-01-29 11:34 次阅读

本文将通过动态演示+代码的形式系统地总结十大经典排序算法

排序算法

算法分类

十种常见排序算法可以分为两大类:

比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

f8fcf3d4-96d9-11ed-bfe3-dac502259ad0.png

算法复杂度

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定
插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(n*log2n) O(n2) O(log2n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定
归并排序 O(n*log2n) O(n*log2n) O(n) 稳定
希尔排序 O(n*log2n) O(n2) O(1) 不稳定
计数排序 O(n+m) O(n+m) O(n+m) 稳定
桶排序 O(n) O(n) O(m) 稳定
基数排序 O(k*n) O(n2) 稳定

1. 冒泡排序

算法思想:

比较相邻的元素。如果第一个比第二个大,就交换它们两个

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

针对所有的元素重复以上的步骤,除了最后一个;

重复步骤1~3,直到排序完成。

f91e68e8-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidbubbleSort(inta[],intn)
{
for(inti=0;i< n-1; ++i)
  {
    for(int j = 0; j < n-i-1; ++j)
    {
      if(a[j] >a[j+1])
{
inttmp=a[j];//交换
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}

2. 选择排序

算法思想:

在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末

以此类推,直到所有元素均排序完毕

f948465e-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidselectionSort(intarr[],intn){
intminIndex,temp;
for(inti=0;i< n - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    for (int k = 0; i < n; i++) {
        printf("%d ", arr[k]);
    }
}

3. 插入排序

算法思想:

从第一个元素开始,该元素可以认为已经被排序;

取出下一个元素,在已经排序的元素序列中从后向前扫描;

如果该元素(已排序)大于新元素,将该元素移到下一位置;

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置后;

重复步骤2~5。

f961bf62-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidprint(inta[],intn,inti){
cout<

算法分析:

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

4.快速排序

快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法思想:

选取第一个数为基准

将比基准小的数交换到前面,比基准大的数交换到后面

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

f99b9db8-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidQuickSort(vector&v,intlow,inthigh){
if(low>=high)//结束标志
return;
intfirst=low;//低位下标
intlast=high;//高位下标
intkey=v[first];//设第一个为基准

while(first< last)
    {
        // 将比第一个小的移到前面
        while (first < last && v[last] >=key)
last--;
if(first< last)
            v[first++] = v[last];

        // 将比第一个大的移到后面
        while (first < last && v[first] <= key)
            first++;
        if (first < last)
            v[last--] = v[first];
    }
    //
    v[first] = key;
    // 前半递归
    QuickSort(v, low, first - 1);
    // 后半递归
    QuickSort(v, first + 1, high);
}

5.堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

算法思想:

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

代码:

#include
#include
usingnamespacestd;

//堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。

voidmax_heapify(intarr[],intstart,intend){
//建立父节点指标和子节点指标
intdad=start;
intson=dad*2+1;
while(son<= end) { //若子节点在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标,选择最大的
            son++;
        if (arr[dad] >arr[son])//如果父节点大于子节点代表调整完成,直接跳出函数
return;
else{//否则交换父子內容再继续子节点与孙节点比較
swap(arr[dad],arr[son]);
dad=son;
son=dad*2+1;
}
}
}

voidheap_sort(intarr[],intlen){
//初始化,i从最后一个父节点开始调整
for(inti=len/2-1;i>=0;i--)
max_heapify(arr,i,len-1);
//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完成
for(inti=len-1;i>0;i--){
swap(arr[0],arr[i]);
max_heapify(arr,0,i-1);
}
}

intmain(){
intarr[]={3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
intlen=(int)sizeof(arr)/sizeof(*arr);
heap_sort(arr,len);
for(inti=0;i< len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

6. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法思想:

把长度为n的输入序列分成两个长度为n/2的子序列;

对这两个子序列分别采用归并排序;

将两个排序好的子序列合并成一个最终的排序序列。

f9b598da-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidprint(inta[],intn){
for(intj=0;j

7. 希尔排序

1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法思想:

选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

按增量序列个数k,对序列进行k 趟排序;

每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

fa6ef032-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidshell_sort(Tarray[],intlength){
inth=1;
while(h< length / 3) {
        h = 3 * h + 1;
    }
    while (h >=1){
for(inti=h;i< length; i++) {
            for (int j = i; j >=h&&array[j]< array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

8 计数排序

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

算法思想:

找出待排序的数组中最大和最小的元素;

统计数组中每个值为i的元素出现的次数,存入数组C的第i项;

对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);

反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

fa8e68cc-96d9-11ed-bfe3-dac502259ad0.gif

代码:

#include
#include
#include

usingnamespacestd;

//计数排序
voidCountSort(vector&vecRaw,vector&vecObj)
{
//确保待排序容器非空
if(vecRaw.size()==0)
return;

//使用vecRaw的最大值+1作为计数容器countVec的大小
intvecCountLength=(*max_element(begin(vecRaw),end(vecRaw)))+1;
vectorvecCount(vecCountLength,0);

//统计每个键值出现的次数
for(inti=0;i< vecRaw.size(); i++)
        vecCount[vecRaw[i]]++;
    
    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < vecCountLength; i++)
        vecCount[i] += vecCount[i - 1];

    // 将键值放到目标位置
    for (int i = vecRaw.size(); i >0;i--)//此处逆序是为了保持相同键值的稳定性
vecObj[--vecCount[vecRaw[i-1]]]=vecRaw[i-1];
}

intmain()
{
vectorvecRaw={0,5,7,9,6,3,4,5,2,8,6,9,2,1};
vectorvecObj(vecRaw.size(),0);

CountSort(vecRaw,vecObj);

for(inti=0;i< vecObj.size(); ++i)
        cout << vecObj[i] << "  ";
    cout << endl;

    return 0;
}

9 桶排序

将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。

算法思想:

设置一个定量的数组当作空桶子。

寻访序列,并且把项目一个一个放到对应的桶子去。

对每个不是空的桶子进行排序。

从不是空的桶子里把项目再放回原来的序列中。

fac02736-96d9-11ed-bfe3-dac502259ad0.gif

代码:

voidBucket_Sort(inta[],intn,intmax){
inti,j=0;
int*buckets=(int*)malloc((max+1)*sizeof(int));
//将buckets中的所有数据都初始化为0
memset(buckets,0,(max+1)*sizeof(int));
//1.计数
for(i=0;i< n; i++) {
        buckets[a[i]]++;
        printf("%d : %d
", a[i], buckets[a[i]]);
    }
    printf("
");
    // 2.排序
    for (i = 0; i < max+1; i++) {
        while ((buckets[i]--) >0){
a[j++]=i;
}
}
}

intmain(){
intarr[]={9,5,1,6,2,3,0,4,8,7};
Bucket_Sort(arr,10,9);
for(inti=0;i< 10; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");
 
    return 0;
}

10 基数排序

一种多关键字的排序算法,可用桶排序实现。

算法思想:

取得数组中的最大数,并取得位数;

arr为原始数组,从最低位开始取每个位组成radix数组;

对radix进行计数排序(利用计数排序适用于小范围数的特点)

fb06dd8e-96d9-11ed-bfe3-dac502259ad0.gif

代码:

intmaxbit(intdata[],intn)//辅助函数,求数据的最大位数
{
intmaxData=data[0];///< 最大数
    /// 先求出最大数,再求其位数,这样有原先依次每个数判断其位数,稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >=p)
{
//p*=10;//Maybeoverflow
maxData/=10;
++d;
}
returnd;
/*intd=1;//保存最大的位数
intp=10;
for(inti=0;i< n; ++i)
    {
        while(data[i] >=p)
{
p*=10;
++d;
}
}
returnd;*/
}
voidradixsort(intdata[],intn)//基数排序
{
intd=maxbit(data,n);
int*tmp=newint[n];
int*count=newint[10];//计数器
inti,j,k;
intradix=1;
for(i=1;i<= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >=0;j--)//将所有桶中记录依次收集到tmp中
{
k=(data[j]/radix)%10;
tmp[count[k]-1]=data[j];
count[k]--;
}
for(j=0;j< n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

审核编辑:汤梓红
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92845
  • C语言
    +关注

    关注

    180

    文章

    7604

    浏览量

    136718
  • 代码
    +关注

    关注

    30

    文章

    4780

    浏览量

    68540
  • 数据结构
    +关注

    关注

    3

    文章

    573

    浏览量

    40124
  • 排序算法
    +关注

    关注

    0

    文章

    52

    浏览量

    10056

原文标题:C语言 | 动图演示十大经典排序算法(含代码)

文章出处:【微信号:混说Linux,微信公众号:混说Linux】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    展示C语言十大经典排序算法

    以前也零零碎碎发过一些排序算法,但排版都不太好,又重新整理一次,排序算法是数据结构的重要部分,系统地学习很有必要。
    发表于 11-08 09:45 599次阅读

    C语言经典排序算法总结

    本文将通过动态演示+代码的形式系统地总结十大经典排序算法
    发表于 06-05 10:56 536次阅读
    <b class='flag-5'>C</b><b class='flag-5'>语言</b><b class='flag-5'>经典</b><b class='flag-5'>排序</b><b class='flag-5'>算法</b>总结

    C语言实现十大经典排序算法

    比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序
    发表于 06-25 10:23 400次阅读
    <b class='flag-5'>C</b><b class='flag-5'>语言</b>实现<b class='flag-5'>十大经典</b><b class='flag-5'>排序</b><b class='flag-5'>算法</b>

    十大排序算法总结

    排序算法是最经典算法知识。因为其实现代码短,应该广,在面试中经常会问到排序
    的头像 发表于 12-20 10:39 1120次阅读

    C语言十大滤波算法

    C语言十大滤波算法
    发表于 08-15 18:41

    经典算法大全(51个C语言算法+单片机常用算法+机器学十大算法

    流程、伪代码等来描述算法。 本经典算法研究系列,如今己写了22篇,13个算法,包括
    发表于 10-23 14:31

    数据挖掘十大经典算法,你都知道哪些!

    的所有需求。而这三类里又包含许多经典算法。而今天,小编就给大家介绍下数据挖掘中最经典十大算法,希望它对你有所帮助。一、 分类决策树
    发表于 11-06 17:02

    电池管理中的十大经典理论

    电池管理中的十大经典理论 1、彼得原理      每个组织都是由各种不同的职位、等级或阶层的排列所组成,每个人都隶属于
    发表于 11-06 15:43 803次阅读

    数学建模十大经典算法

    电子专业单片机相关知识学习教材资料——数学建模十大经典算法
    发表于 08-08 18:20 0次下载

    10个经典C语言面试基础算法代码

    10个经典C语言面试基础算法代码
    的头像 发表于 01-16 11:09 2852次阅读

    演示C语言10大经典排序算法(代码)

    快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
    的头像 发表于 02-02 15:41 2769次阅读

    演示C语言10大经典排序算法(代码)

    本文将通过 动态演示+代码 的形式系统地总结十大经典排序算法排序
    的头像 发表于 02-07 01:24 734次阅读

    用Python实现十大经典排序算法(附)

    冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要
    的头像 发表于 03-13 09:29 1932次阅读

    常见排序算法分类

    本文将通过动态演示+代码的形式系统地总结十大经典排序算法排序
    的头像 发表于 06-22 14:49 907次阅读
    常见<b class='flag-5'>排序</b><b class='flag-5'>算法</b>分类

    单片机ADC,十大C语言滤波算法

    单片机ADC,十大C语言滤波算法
    的头像 发表于 10-24 15:53 1226次阅读