简单排序（C语言实现）

旧城等待， 2023-01-07 12:29 132阅读 0赞

之前是学过一些排序算法，但是自己从来也没有认真整理过，正好趁着空闲写一篇笔记整理一下。

### 文章目录 ###

*  一、简介
 *  二、冒泡排序
 *  三、简单选择排序
 *  四、直接插入排序
 *  五、小结

# 一、简介 #

> 我们生活中无时无刻都在应用着排序，因为只要涉及到竞争比大小（或优劣）就必须有个先后顺序。在计算机中，“排序”更是优化其他算法所常用的一种手段，经典的排序算法有许多，如冒泡排序、选择排序以及插入排序等等，这篇笔记也主要就是实现一下这其中的一些简单的排序算法（内排序）。  
> 不过只要是算法，我们都会关注其以下几点：稳定性，时间性能，辅助空间以及算法复杂度等等，这其中的含义可能略有不同，如排序算法的稳定性和时间性能分别是指每次排序后的结果是否相同以及其比较和移动的次数。说了这么多，其实不如直接上代码可能更容易让人理解\*^\*。

# 二、冒泡排序 #

> 作为鼎鼎大名的一种排序算法，几乎所有刚开始接触计算机语言的人都会使用它，其是一种交换排序，它的基本思想是：**两两比较相邻记录**的关键字，如果反序则进行交换，直至没有反序记录。

我们经常会写出的冒泡排序可能是下面这种（我之前也一直以为是这样\*^\*）：

> main.c

#include<stdio.h>
    #include"Practice.h"
    
    int main()
    { 
    	int arr[]={ 9,2,8,3,4,5,1,0,6,7},
    		length=sizeof arr/sizeof arr[0],i;
    
    	GeneralBubbleSort(arr,length);
    	for(i=0;i<length;i++)
    	{ 
    		printf("%d ",arr[i]);
    	}
    	printf("\n");
    		
    	return 0;
    }

> Practice.h

//****************************************
    //声明部分
    //****************************************
    
    void GeneralBubbleSort(int arr[],int length);		//一般的冒泡排序
    
    //****************************************
    //定义部分
    //****************************************
    
    //一般的冒泡排序
    void GeneralBubbleSort(int arr[],int length)
    { 
    	int i,j,temp;
    	for(i=0;i<length;i++)
    	{ 
    		for(j=i+1;j<length;j++)
    		{ 
    			if(arr[i]>arr[j])
    			{ 
    				temp=arr[i];
    				arr[i]=arr[j];
    				arr[j]=temp;
    			}
    		}
    	}
    }

运行效果：  
![在这里插入图片描述][20210118101750249.png]

但是上述的一般冒泡排序却不是真正的冒泡排序，因为冒泡排序的定义是要比较**两两相邻记录**，而上面的排序过程并不是这样进行比较的，如果硬要找一个与其类似的排序，后面要实现的选择排序可能与其更为相似。那么真正的冒泡排序应该是下面这样的：

> Practice.h

//正确的冒泡排序
    void CorrectBubbleSort(int arr[],int length)
    { 
    	int i,j,temp;
    	for(i=0;i<length;i++)
    	{ 
    		for(j=length-1;j>i;j--)
    		{ 
    			if(arr[j]<arr[j-1])
    			{ 
    				temp=arr[j];
    				arr[j]=arr[j-1];
    				arr[j-1]=temp;
    			}
    		}
    	}
    }

虽然算法复杂度相较于一般的冒泡排序并没有提升，但是其排序过程更像是“水泡”向上冒出来的过程\*^\*。

> 而对于真正的冒泡排序而言，在这个过程中其实还有优化的余地，因为其每一次都会比较两两相邻的记录，那么在这个过程中是否可能发生这种情况：“排序过程还没有结束，但是已经排好序了”。举个例子，假设有5个数字，那么按照冒泡排序的过程则需要4轮排序过程就可以实现将其从小到大排序，但是在进行到第2轮时其实就已经拍好序了，所以后面的两轮排序过程其实就可以不用进行了，为了防止这样的情况发生，我们可以引入一个第三者来监视整个排序过程。代码实现如下：

//改进的冒泡排序
    void ImprovedBubbleSort(int arr[],int length)
    { 
    	int i,j,temp,flag=1;
    
    	for(i=0;i<length && flag;i++)
    	{ 
    		flag=0;		//将flag作为一个标记，如果在这个某个冒泡的过程中发生了数据交换则置为1，反之则置为0，并退出整个冒泡过程
    		for(j=length-1;j>i;j--)
    		{ 
    			if(arr[j]<arr[j-1])
    			{ 
    				temp=arr[j];
    				arr[j]=arr[j-1];
    				arr[j-1]=temp;
    				flag = 1;
    			}
    		}
    	}
    }

虽然经过优化，但该算法的最坏比较次数仍是 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2次，并做等量级的记录移动，因此其总的时间复杂度仍为 O ( n 2 ) O(n^2) O(n2)。

# 三、简单选择排序 #

> 排序的过程其实就是比较和交换的过程，如果说冒泡排序算法像一个勇士（通过不停的交换克服重重困难以实现最终的排序），那么下面这个选择排序算法则更像是一个猎人（通过不断的比较最终锁定目标以实现最终的排序，精准而又优雅）。

> 该算法的定义是：通过 n − i n-i n−i次关键字间的比较，从 n − i + 1 n-i+1 n−i\+1个记录中选出关键字最小的记录，并和第i ( 1 ≤ i ≤ n ) (1\\leq i\\leq n) (1≤i≤n)个记录交换之。实现代码如下：

//选择排序
    void SelectSort(int arr[],int length)
    { 
    	int i,j,temp,min;
    
    	for(i=0;i<length;i++)
    	{ 
    		min = i;
    		for(j=i+1;j<length;j++)
    		{ 
    			if(arr[min]>arr[j])
    			{ 
    				min = j;
    			}
    		}
    
    		if(min!=i)
    		{ 
    			temp=arr[min];
    			arr[min]=arr[i];
    			arr[i]=temp;
    		}
    	}
    
    }

不过其最坏的情况下仍会比较 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2次，交换 n − 1 n-1 n−1次，故而其总的时间复杂度仍是 O ( n 2 ) O(n2) O(n2)。尽管其与冒泡排序同为 O ( n 2 ) O(n2) O(n2)，但是其性能是略优于冒泡排序的。

# 四、直接插入排序 #

> 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

这有点类似于我们玩牌的过程，从无到有直至最终整理好所有牌，实现代码如下：

//插入排序
    void InsertSort(int arr[],int length)
    { 
    	int i,j,temp;
    
    	for(i=1;i<length;i++)
    	{ 
    		if(arr[i] < arr[i-1])
    		{ 
    			temp=arr[i];
    
    			for(j=i-1; arr[j]>temp && j>-1;j--)
    			{ 
    				arr[j+1]=arr[j];
    			}
    
    			arr[j+1]=temp;
    		}
    	}
    }

该算法虽然在最坏情况下，需要比较 ( n + 2 ) ( n − 1 ) / 2 (n+2)(n-1)/2 (n\+2)(n−1)/2次，移动 ( n + 4 ) ( n − 1 ) / 2 (n+4)(n-1)/2 (n\+4)(n−1)/2次，算法的性能是要低于冒泡与选择排序的。但是如果排序的记录是随机的，那么根据概率相同的原则，其平均比较和移动次数约为 n 2 / 4 n^2/4 n2/4，反而整体的性能是要略优于冒泡和简单排序，所以排序算法的使用要因地制宜。

# 五、小结 #

> 真正认真看了一些算法之后，才真的发现自己之前有点理想化了，这个世界上其实并没有最好、最普世的算法，它只存在着“最适合”的算法，算法的好坏与数据的分布息息相关，我们不能抛开外部因素而只关注算法本身啊\*^\*。

> 参考资料：《大话数据结构》，[【C语言描述】《数据结构和算法》（小甲鱼）][C]

[20210118101750249.png]: /images/20221119/6728c3a80d4d410a803a0f295e5f4bac.png
[C]: https://www.bilibili.com/video/BV1jW411K7yg