C语言中几种常用的排序算法分析

C语言中几种常用的排序算法分析

目录

摘要.................................................................1

引言.................................................................2

1.排序的含义分析..................................................2

2.C语言中几种常用的排序算法分析...............................2

2.1冒泡排序法....................................................2

2.2选择排序法....................................................4

2.3直接插入排序法................................................6

2.4希尔排序法....................................................7

2.5归并排序法...................................................10

2.6快速排序法...................................................12

2.7堆排序法.....................................................14

3.几种排序算法的比较和选择.....................................16

3.1选取排序方法需要考虑的因素...................................16

3.2编程时如何选择排序...........................................16

结束语..............................................................18

参考文献...........................................................18

摘要：基于信息与「算科学C语言作为计算机程序设计基本语言，程序设

计过程中，排序算法在数据处理领域中经常用到，它的好坏会直接影响程序运行

的快慢.因此我这次研究将C语言七种常用排序方法冒泡法排序、选择法排序、

直接插入法排序、希尔排序、归并法排序、快速法排序、堆排序从效率和稳定性

进行比较，明确排序比较的选择思路，并深入探讨基于C语言的排序应用.

关键词：C语言；程序；排序

引言

本论文为了更好更透彻的研究基于C语言的常用排序比较，我着手从C语

言排序冒泡法排序、选择法排序、直接插入法排序、希尔排序、归并法排序、快

速法排序、堆排序七种方法来探究，从文献［I］⑵⑶⑷［5］里归纳出基于C语言的

常用排序比较七种方法：冒泡法排序、选择法排序、直接插入法排序、希尔排序、

归并法排序、快速法排序、堆排序.文献［3］和［4］讲述了其中冒泡法排序和选择法

排序教学课程设计，剖析算法思想.我在结合徐春选老师和章程老师的研究中，

从而找到了文献⑴和文献［2］,讲述了七种排序方法在排序过程中自己总结了需

要进行比较的次数.

论文的正文主要以C语言七种算法思想为中心,进行计算分析排序过程中需

要进行比较的次数，进而比较得出七种常用排序的稳定性应用，掌握基于C语

言的七种常用排序算法思想为基础，在进行算法的操作会更加简单，便于之后的

分析结论总结.数学计算与C语言有着不可分割的关系，通过计算七种常用排序

方法的比较次数，利用数学公式的方法为中介会更加直观的观察到排序过程中存

在的问题.现在使用计算机来更改与管理信息是非常常见的现象了，所以我们有

时候为了提升管理效率，这个时候就需要利用科学措施方法进而提升信息更改和

交换的速度，在这样的背景下，就需要去探究寻找一种有效、优化的计算方法,

因此排序的方法就可以很好体现这样的一个需求.每种排序方式的排序程度与思

想在效率空间还有计算速度上都存在着不一样的地方，所以我这次就针对C语

言中的七种排序计算方法进行了深入探讨研究.

1

1.排序的含义分析

排序(sorting)又称分类，是数据处理领域中一种很常用的运算.排序就是

把一组被记录或着一些其他数据元素的没有顺序序列去照着某些关键字词值进

行递增或者说也就是递减顺序一种再次次序排列的过程.一般而言进行这个排序

主要目的之一就是为了在现实中进行实现快速查找想要数据.而且平时的生活经

常都会用排序去应用的事喟十分常见.就好像电话本的排序，病例还有档案的归

拢，以及一些文档目录表等，这些在很多情况下差不多都需要对一些数据库里有

顺序的信息和数据库进行实际操作去寻找.然而在C语言程序设计实际操作过程

中，往往等待排序的序列不仅仅是单个数值，大部分都是由一些记录来组成，在

这些记录里面都有一个共同有规律的关键字，它就是要进行排序的一种根据方式,

这样子的情况下，则要按照关键字去进行排序，然后去顶下排序方式，让这种排

序方式成为有序记录：如果n个待排序记录为{R「R”R3,……，，R排序记录关键

字序列为{K1.K2.K3.•,淮备排序的时候，那些要重新按照关键字进行排列的

序列，为了使这个序列去满足呈现递减或递增的关系，去达到序列具备有序性.

2.C语言中几种常用的排序算法分析

2.1冒泡排序法

2.1.1冒泡排序法思想思路

先把第1个数和第2个数进行比较，如果第2个数比第1个数小，就将两个

数互换,这样情况的时候小的数就可以被排到前面了.然后再将第2个数和第3

个数比较，如果第3个数比第3个数小，就将两个数互换，这样，第3个数也就

是3个数中最大的了.依此规律，将相邻两个数进行比较，将小的调整到前头.

2.1.2程序核心算法

#include<stdio.h>

intmain()

f

inta[10];

inti,j,t；

printf("input10nunibersAn");

for(i=0;i<10;i++)

2

scanf("%d",&a|i]);

printf(”\n")；

for(j=0;j<9;j++)

for(i=0;i<9-j;i++)

if(a[i]>a[i+l])

{t=a[i];a[i]=a[i+l];a[i+l]=t;}

printf("thesortednumbers:");

for(i=0;i<10;i++)

printf(H%d",a|i|);

printfCVn,1);

return0;

}

2.1.3运行结果如图1冒泡排序法运行结果

■1E:\新建文件夹\c语言编译'冒泡排序改.exe

input10numbers:

32445322343536262821

thesortednumbers:

21222628323435364453

Processexitedafter26.5secondswithreturnvalue0

请按任意键继续....

图1冒泡排序法运行结果

2.1.4结论

这个顺序，在nJ趟子排序过程中一步步实现冒泡排序，当运转到第i趟子

配需的过程中，就会从第一个数加到第n-1个数，要是第i个数大于后面的数,

而后就会替换成功,在这个计算过程能够看出来,冒泡排序法的计算效率比较低,

同时也会花费大批的功夫，但也存在长处就是编写容易以及稳定性高，因而这种

计算形式经常应用在运算量较小的排序算法之中.

2.2选择排序法

2.2.1选择排序法思想思路

选择排序计算办法是属于一种很直观的排序计算方法，一般情况下都会先在

3

还没有进行排序的序列里面去找到一个最小的元素,然后再去把这个最小的元素

存放到这个序列的第一个位置，也就是说把第一个位置的元素和这个序列之中最

小的元素进行替换，然后在余下没有进行排序的元素里面继续排查找到一个最小

的元素，与第二个元素的位置再次进行交换.用这个办法直到所有元素都排序结

束.

2.2.2程序核心算法

#include<stdio.h>

intmain()

(

inta|10|={32,44,53,2234,35,36,26,28,21);

intij,k,temp,n=10;

printf("input10numbers:\n");

for(i=0;i<IO;i++)

printf(M%dH,a|i|);

printf(,,\n,');

fbr(i=0;i<n-l;i++)

(

k=i;

for(j=i+l；j<n;j++)

if(a[k]>a[jj)

k=j;

if(k!=i){

temp=a[ij;

a[i]=a[k];

a[k]=temp;

}

1

printf("\n");

printf("thesortednumbers:\n");

for(i=0;i<n;i++)

4

printf(H%d",a[ij);

printfCAn");

return0;

)

2.2.3运行结果如图2选择排序法运行结果

■'IE:\新建文件夹\c语言编译\选择排序.exe

input10numbers:

32445322343536262821

thesortednumbers:

21222628323435364453

Processexitedafter0.02088secondswithreturnvalue0

储按任意键继续...

图2选择排序法运行结果

2.2.4结论

进行选择排序这个方式通常一般都需n-i次比较，无论最开始的状态是怎么

样的，每次进行排序都需加次比较，所以这个计算方法的比较次数可以归纳为

n-i次，如果序列最开始的时候是有顺序的话，这样就是最小的交换记录数为0,

如果最开始的时候是逆序的序列的话，这样每次比较都要有交换记录，那么移动

次数可以大致的去归纳为3n-1),所以平均选择排序算法大致要用到的时间复杂

度为n2.在整个计算过程之中仅仅用到一个额外的空间用来便于交换.选择排

序每次排序进行辅助存储空间为O⑴.同时可以很明确的看出来选择排序算法是

不具有稳定性的，效率也相对的低下.

2.3直接插入排序法

2.3.1直接插入排序法思想思路

直接插入排序法的思想思路是在一组要去进行排序的元素里面，按照一定的

顺序来取出一个元素，去把这个元素根据之前所排列好的大小插入排好顺序的序

列里面，最终排列出一个全新具有顺序的总元素数目加一的序列表，当所有的元

素都插入这个有序表里面再中止继续插入这一操作.

2.3.2程序核心算法

#include<stdio.h>

5

intmain()

inta|IO]={32,44,53,2234,35,36,26,28,21);

inti,j,temp,n=10;

printf("input10numbers:\n");

for(i=0;i<10;i++)

printf(H%d",a[i]);

printf(”\n”)；

for(i=0;i<n-l;i++)

for(j=i+l;j<n;j++)

if(a|i|>a|j|)

(

temp=a[i];

a[i]=a|j];

a|j]=temp;

)

printfCVn");

printf("thesortednumbers:\n");

for(i=0;i<n;i++)

printf("%dM,a[i]);

printf(H\n");

return0;

)

2.3.3运行结果如图3直接插入排序法运行结果

6

■'E:\新建文件夹\c语言编译函接插入排序.exe

input10numbers:

32445322343536262821

thesortednumbers:

21222628323435364453

Processexitedafter0.02022secondswithreturnvalue0

请按任意键继续...

图3直接插入排序法运行结果

23.4结论

直接插入排序法在理想状况的时候,也就是需要排列的序列是有顺序的时候,

那么整个计算过程总共需要进行n-1趟比较，如果计算序列为逆序的时候，也就

是最差的情况之下，在第i趟插入的时候就需要进行M次比较，所以整个排序

过程需进行n(n-l)旗比较，直接插入排序法的时间开销即时间复杂度即为O(n)

算法中仅用一个附加的空间，因此这个算法所需要的辅助存储空间为O⑴；直接

排序法是稳定的.

2.4希尔排序法

2.4.1希尔排序法思想思路

希尔排序法也被称为缩小的向量方法.首先我们需要选择一个正整数d1<n去

作为整个序列的一个间隔，这样做的目的是为了把全部的记录去分别拆开成为

dl个子序列，然后再把所有距离是dl倍数的记录都放到一个子序列里面去，又

需要在每个子序列之中进行这个操作不断重复；最后就是缩小间隔让d2<dl,通

过了不断重复之前对子序列划分和排序的操作，当间隔di=l就停止操作，也就

是说把所有的记录都放到一个一样的序列里面的时候排序才会停止继续.

2.4.2程序核心算法

#includc<stdio.h>

voidShc)lSort(inta[],intn)

inti,j,temp;

intflag,gap=n;

7

while(gap>l)

gap=gap/2;

flag=l;

while(flag)

(

flag-0;

for(i=0;i<n-gap;i++)

(

j=i+gap;

if(a[i]>a[j])

(

temp=a[i|;

a[i]=a[j];

a[j]=temp;

11ag=l;

1

1

)

}

}

main()

(

inta[10],i;

printf("pleaseinput10numbers:\n");

for(i=0;i<10;i++)

scanf("%d",&a[ij);

for(i=0;i<IO;i++)

ShellSort(aJO);

printf("thesortednumbers:\n");

8

for(i=0;i<10;i++)

printf(,,%-4d",a|i]);

printf(n\n");

)

2.4±运行结果如图垂尔排序法运行结手

■।E:\新建文件夹\c语言编译'希尔10.exe

pleaseinput10numbers:

32445322343536262821

(thesortednumbers:

21222628323435364453

Processexitedafter10.15secondswithreturnvalue0

储按任意键继续...

圈4希尔排序法运行结果

2.4.4结论

希尔排序计算方法的时间复杂度分析都比较复杂，所有计算过程中元素进行

比较的次数和进行移动的次数都会因为所选择的增量不同而存在有比较大的差

异.因为希尔算法中常常会被我们使用得到一个额外的辅助存储空间，它所存在

辅助存储空间分别为O⑴.所以希尔排序算法实际上是一种不稳定的计算方式，

这一优势和特点在它的计算程序代码中也可以清晰地看得出来，当我们进行分组

时两个元素的排序都相同，所对应的位置都很有可能会发生变化.

2.5归并排序法

2.5.1归并排序法思想思路

归并排序计算方法就是把超过两个以上的序列里面数据都合为新的有顺序

的一个序列，这种办法可以把很多数据合成一个新的序列，并且在解决问题的时

候，能够将待排序的序列拆开变成具有差异性的待排列子数列，完成每个排序工

作之后的时候，就能够把序列去放到起变成有顺序的序列.

2.5.2程序核心算法

#include<stdio.h>

#include<stdlib.h>

9

#defineN10

voidmerge(intarr||,intlow,intmid,inthigh){

inti,k;

int*tmp=(int*)malloc((high-low+l)*sizeof(int));

intlefUow=low;

intleft_high=mid;

intright」ow-mid+1;

intrighl_high=high;

for(k=0;left_low<=lefl_high&&right_low<=right_high;k++)

(

if(arr[leftjow|<=arr|rightjow])

{tmp|k|=arr|left_low+4-];}

else{tmp[k]=arr[right_low++];}

}

if(left_low<=ieft_high)

(

for(i=left_low;i<=left_high;i++)

tmplk++]=arr[i];

)

if(righ1」ow<=righi_high)

(

for(i=right_low;i<=right_high;i++)

tmplk++]=arr[i];

)

for(i=0;i<high-low+l;i++)

arr[low+i]=tmp(ij;

free(tmp);

return;

1

voidmerge_sort(intarr[],unsignedintfirst,unsignedintlast){

io

intmid=0;

if(first<last)

mid=(first+last)/2;

merge_sort(arr,first,mid);

merge_sort(arr,mid+ljast);

merge(arr,first,mid,last);

}

return0;

1

intmain()

(

inti;

inta[N]={32,44,53,22,34,35,36,26,28,21);

merge_sort(a,0,N-l);

for(i=0;i<N;i++)

printfC'%d';ali]);printf("\n");

system("pause");

return0;

)

2.5.3运行结果如图5归并排序法运行结果

(1E:\新建文件夹\c语言编译、归并排序终.exe

21222628323435364453

请按任意键继续...

Processexitedafter2.072secondswithreturnvalue0

请按任意键继续...■

图5归并排序法运行结果

11

2.5.4结论

归并排序计算方法的算法复杂度是。(nbg：放种计算的方法速度主要在于

快速排序，这个方法常常会被采用在总体或者字序列有序的数列问题里面.

2.6快速排序法

261快速排序法思想思路

快速排序计算方式是根据冒泡排序计算方法进而产生的一种计算法，应用这

种计算方法的时候往往需在序列之中设置一些有关的基准数，再使用排序法将需

要排序的数据去拆分成为两个范围，一个部分需要去小于另外一个部分的数据,

在完成之后，这样就能够月这个方式去对两部分数据进行排序，然而这个过程存

在一种递归的性质，最终就会把数据排列成为有顺序的序列.

2.6.2程序核心算法

#include<stdio.h>

#include<stdlib.h>

#defineBUF_SIZE10

voiddisplay(intarray[],intmaxlen)

(

inti;

for(i=0;i<maxlen;i++)

{printf(“％-3d”，array[i]i;)

printf("\n");

return0;

)

voidQuickSort(int*arr,intlow,inthigh)

(

if(low<high)

(

inti=low;

intj=high;

intk=arr[iowj;

while(i<j)

while(i<j&&arr|j|>=k)

{j-；l

if(i<j)

{arr[i++]=arrU];)

while(i<j&&arr|i|<k)

(i++；)

if(i<j)

(arrlj-]=arr|i]:|

)

arr[i]=k;

QuickSort(arr,low,i-1);

QuickSort(arr,i+Lhigh);

}

)

intmain()

{intarray[BUF_SIZE]=[32,44,53,22,34,35,36,26,28,21);

intmaxlen=BUF_SIZE;

QuickSort(array,0,maxlen-1);

display(array,maxlen);

return0;)

2.6.3运行结果如图6快速排序法运行结果

■E:\新建文件夹\c语言编浮\快速改.exe

21222628323435364453

Processexitedafter0.0126secondswithreturnvalue0

请按仔意键继续....

图6快速排序法运行结果

2.6.4结论

13

通常这样状况，快速排序计算方式它的时间复杂度是0(nbg：)哪怕在最坏

的时候，这个计算方式的时间复杂度也是。(尸由此可见快速排列计算方式可

以有效率地去大大减少计算的时间，这样子这个计算方式就能够在很多的架构状

况里面，内部循环率达到理想程度，所以通常比较适合在没有顺序的序列里面排

序时采用，这个算法是不稳定的.

2.7堆排序法

2.7.1堆排序法思想思路

堆排序这种计算方法属于一种树形选择的方法，并且还是一种跟直接选择排

序在一起相比较会更加有效率的一种改良办法.然而堆排序其实就是一个里面包

含有n个元素的序列：hl,h2,...h,n)这条件时当且仅满足：hi>=h2Lhi>=2i+1)

或hi<=h2i,hi<=2i+1)(i=12的陋模就会被叫做堆.但是这次排序方法中只需要

去讨论满足其中前者条件的堆.根据堆的定义能够总结得出，堆顶元素也能够说

是其中的第一个元素就能够变成最大的，然而完全二叉树能够非常直接去反映出

堆的结构，把堆顶看作一人根，其它部分就完全可以被分成左子树和右子树两个

部分.在最开始的时候就能够让需排序的数想想成为一棵由顺序去存储的二叉树,

然后再去调整整个顺序，最终能够让它变成一个堆.结果就是堆本身根节点的数

会变成最大的，继续使根节点和最末端的一个节点位置相互改变一下，再去把之

前n-1个数全部进行调整最终再次组成一个新的堆.按照这个方法最终只会含有

两个节点，然后在对它们进行交换处理直到会得到一个含有n个节点的有顺序的

序列.

2.7.2程序核心算法

#include<stdio.h>

#include<stdlib.h>

voidBuildMaxHeap(int*heap,in(len)

(

inti;

inttemp;

for(i=len/2-1;i>=0;i--)

{if((2*i+1)<len&&heap[i]<he叩[2*i+1])

14

temp=heap|i|;

heap|i|=heap[2*i+l];

heap|2*i+l|=temp;

if((2*(2*i+l)+l<len&&heap[2*i+l|<heap|2*(2*i+l)+I|)||

(2*(2*i+l)+2<len&&heap[2*i+1]<heap[2*(2*i+1)+2]))

(BuildMaxHeap(heap,len);)

)

if((2*i+2)<len&&heap[i]<heap[2*i+2])

(

temp=heapji];

heap|i|=heap[2*i+2];

heap|2*i+2|=temp;

if((2*(2*i+2)+l<len&&heap|2*i+2|<heap|2*(2*i+2)+I|)||

(2*(2*i+2)+2<len&&heap[2*i+2|<heap|2*(2*i+2)+2|)i

(BuildMaxHeap(heap,len);}

)

)

)

voidSwap(in(*heap,intlen)

{

inttemp;

temp=heap[OJ;

heap[0]=heap[len-l];

heapllen-1J=temp;

1

intmain()

(

inta[10]={32,44,53,22,34,35,36,26,28,21};

intlen=10;inti;

15

for(i=len;i>0;i")

{BuildMaxHeap(a,i);Swap(a,i);)

for(i=0;i<len;i++)

{printf("%d';a|i]);)

return0;

)

2.7.3运行结果如图7堆排序法运行结果

《■।E:\新建文件夹\c语言编译'堆排序改.exe

21222628323435364453

processexitedafter0.02846secondswithreturnvalue0

倩按任意键继续...

图7堆排序法运行结果

2.7.4结论

堆排序法一般总共得进行两个过程，首先第一部建立一个堆，其次第二部就

要将堆顶和堆放到末端的一个元素互相换下位置.由此可得出堆排序总共需要有

两个函数构建组成，先是需要去建立一个有关于堆的渗透函数，然后再是反复的

去调用渗透函数最终去实现函数.从这个计算的原理之中就可以明显看出堆排序

n

是一个不稳定的排序方法，这种计算的算法时间复杂度是O(nlog2.)

3.几种排序算法的比较和选择

3.1选取排序方法需要考虑的因素

首先是要去考虑等待排序里面元素数目n;然后再根据元素自己信息量有多

大；去进行观察关键字本身存在的结构和它分布状况；同时还要去考虑到语言相

关工具所具备的条件能否满足计算，不仅如此还有辅助空间的大小等相关因素都

需要进行考虑.

3.2编程时如何选择排序

如果存在元素数目n较