Fork me on GitHub

C 语言实现各排序算法

面试官:“ 先手写一个快速排序吧!”

最近整理了一些排序算法,并记录下实现过程!作为备忘笔记。主要有:快速排序堆排序归并排序插入排序冒泡排序选择排序等。

前言

  • 算法是程序的灵魂。无论程序多么的复杂,只要我们能够抓住程序的主要“矛盾”,就能够适时地解决这些问题,而算法就是其主要矛盾。
  • 排序算法是算法的基础。我们需要学习算法,就必然需要打好自己学习的基石,排序算法作为最基本易懂的算法,我们不精通它又怎么能驾驭得了其他高级算法呢?
  • C 语言:本文选择 C 作为实现语言,主要是本人在看 Linux 下的 C 编程一书,于是就顺便直接在 Linux 系统下开写了!我想 C 语言是每个人都能看得懂的语言,并且其特殊性很少,几乎完全能转化为其他各式语言 ( Java, Php, Python 等 ),因此这也是 C 的好处。

排序算法说明

一、快速排序 / FastSort

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序方法,其核心是分治法。

实现过程:

从数列中选取一个作为 基准数 ( 不妨就选第一个,通常也都是选择第一个 );然后进行分区,将比它小的数放在它左边,比其大的则放在右边;然后对 左右区间进行相同操作 ( 也就是递归 ),直到各个区间只剩一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void quicksort(int array[],int startIndex,int endIndex){
if(startIndex<endIndex){
//x作为基准数
int i=startIndex,j=endIndex,x=array[startIndex];
//下面进行分区
while(i<j){
while(i<j&&array[j]>=x){
j--;
}
if(i<j){
array[i++]=array[j];
}
while(i<j&&array[i]<x){
i++;
}
if(i<j){
array[j--]=array[i];
}
array[i]=x;
}
//左右区间进行相同操作
quicksort(array,startIndex,i-1);
quicksort(array,i+1,endIndex);
}
}

二、堆排序 / HeapSort

堆排序是 Robert W.FloydJ.Williams 在 1964 年共同发明的,其核心是堆数据结构的运用。

堆:是一种数据结构,属于树类,它是 一棵完全二叉树 ( 也就是二叉树的儿子要么没有要么一定要有左儿子,不会出现只有右儿子的情况 ),并且通常父亲要大于其两个儿子 ( 也就是大堆 )。

实现过程:首先将数组建成堆数据结构,然后将堆的根结点与最后结点交换,再对前 n-1 个数再进行调整堆,从而根结点又是 n-1 个数中最大的,与最后结点再次交换,如此循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//本函数功能是:根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength){
int nChild;
int nTemp;
for(;2*i+1<nLength;i=nChild){
//子节点的位置=2*(父节点位置)+1
nChild=2*i+1;
//得到子节点中较大的节点
if(nChild<nLength-1&&array[nChild+1]>array[nChild]){
++nChild;
}
//如果较大的子节点大于父节点那么把较大的子节点往上移动,替换它的父节点
if(array[i]<array[nChild]){
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}else{
break;//否则退出循环
}
}
}
//堆排序算法
void HeadSort(int array[],int length){
int i,temp;
//调整序列的前半部分元素,调整完之后第一个元素是序列的最大元素
//length/2-1是最后一个非叶节点,(length为下标加1)
for(i=length/2-1;i>=0;--i){
HeapAdjust(array,i,length);
}
//从最后一个元素开始对序列进行调整,不断缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i){
temp=array[0];
array[0]=array[i];
array[i]=temp;
//不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}

三、归并排序 / MergeSort

归并排序核心也是 分治法

实现过程:首先是申请变量空间,归并排序是这些算法中空间占用最大的算法,然后循环将数组分为两个子序列,再将两子序列合并为有序段。

归并排序的算法我们通常用递归实现,先把待排序区间 [s,t] 以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//将两个有序数列合并成一个有序数列
//sourceArr为待合并数列,tempArr为合并后序列,仅仅作为中转操作存储
//startIndex,midIndex,endIndex分别为sourceArr中分为两序列的前中后下标
void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){
int i=startIndex,j=midIndex+1,k=startIndex;
//分别从两个序列的起始开始,逐一比较两个序列中元素大小
while(i!=midIndex+1 && j!=endIndex+1){
if(sourceArr[i]>sourceArr[j]){
//较小的存入合并序列
tempArr[k++]=sourceArr[j++];
}else{
//较小的存入合并序列
tempArr[k++]=sourceArr[i++];
}
}
//将未合并的直接放到合并序列里
while(i!=midIndex+1){
tempArr[k++]=sourceArr[i++];
}
while(j!=endIndex+1){
tempArr[k++]=sourceArr[j++];
}
//最后将合并序列在放入原始数列中
for(i=startIndex;i<=endIndex;i++){
sourceArr[i]=tempArr[i];
}
}
//sourceArr为原待排序列,tempArr为合并后序列,作为临时存放区
//startIndex为数组开始下标,endIndex为结束下标
void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex){
int midIndex;
if(startIndex<endIndex){
//将原序列二分为两个序列
midIndex=(startIndex+endIndex)/2;
//分别对两个序列,再进行二分
MergeSort(sourceArr,tempArr,startIndex,midIndex);
MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
//对每个二分序列进行合并
Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
}
}

四、插入排序 / InsertSort

插入排序是将未排序的数插入到已经排好序的数组里,使得新生成的数列也是有序的。

实现过程:将第一个数作为已经排好的序列,然后从后面开始循环插入到第一个数列中,插入的方法是从第一个序列的最后一位开始循环与待插入的数对比,如果比其大则往后移动,直至小于等于其大小或则循环到第一个数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//两层循环,外循环从下标+1处开始到结束
//内层循环,将外层循环中的数与其前面的所有数对比插入。
void insertsort(int array[],int startIndex,int endIndex){
int i,j,item;
if(endIndex>startIndex){
for(j=startIndex+1;j<=endIndex;j++){
item=array[j];
i=j-1;
while(i>=startIndex&&item<array[i]){
//i>=startIndex为防止i--越界
array[i+1]=array[i];//将比item大的数依次后移
i--;
}
array[i+1]=item;
}
}
}

五、冒泡排序 / BubbleSort

冒泡排序应该是最简单的排序算法了,它的实现过程就是利用两层数组循环,逐一将两个数进行对比,将小数放前面,大数放后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
//冒泡排序--顺序比较
//array为数组,startIndex为开始下标(>=0),endIndex为结束下标
void bubblesort(int array[],int startIndex,int endIndex){
int i,j;
for(i=startIndex;i<endIndex;i++){
//将最大值放在最后面
for(j=startIndex;j<endIndex-i;j++){
if(array[j]>array[j+1]){
swap(&array[j],&array[j+1]);
}
}
}
}

六、选择排序 / SelectSort

选择排序其实现过程是通过两层循环,每次找出剩余序列中的最小值,最终得到排序好的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//每次选择剩余中的最小值,依次到结束
void selectsort(int array[],int startIndex,int endIndex){
int i,j,minIndex;
for(i=startIndex;i<endIndex;i++){
minIndex=i;
//选出最小下标,放在最前面
for(j=i+1;j<=endIndex;j++){
if(array[minIndex]>array[j]){
minIndex=j;
}
}
if(minIndex!=i){
swap(&array[i],&array[minIndex]);
}
}
}

总结

项目实现

  1. C实现排序项目地址:https://github.com/jiyiren/CSort

  2. Android图形化排序地址:https://github.com/jiyiren/JYSort

归并排序和堆排序、快速排序的比较

  • 若从空间复杂度来考虑:首选堆排序,其次是快速排序,最后是归并排序
  • 若从稳定性来考虑,应选取归并排序,因为堆排序和快速排序都是不稳定的。
  • 若从平均情况下的排序速度考虑,应该选择快速排序

参考资料