[answerer的算法课堂]简单描述4种排序算法（C语言实现）
[answerer的算法课堂]简单描述4种排序算法（C语言实现）
这是我第一次写文章，想要记录自己的学习生活，写得不好请包涵or指导，本来想一口气写好多种，后来发现，写太多的话反而可读性不强，而且，我文笔，知识有限呐。慢慢来吧
目录
| 名称 | 冒泡排序 | 直接选择排序 | 直接插入排序 | 希尔排序 |
|---|---|---|---|---|
| 时间复杂度 | O(n^2) | O(n^2) | O(n^2) | O(n^(1.3—2)) |
ps.没有讲到稳定性和空间复杂度。
冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
摘自百度百科
时间复杂度大约为O(n^2),可进行一些优化
这应该是c语言课程里头第一次讲到的排序算法，可以说得上是所有排序算法里头最简单的算法了。
思想：按一定的顺序，比如要求从大到小进行排序，那么第一位到最后一位（也可从最后一位到第一位）依次进行多次比较
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
代码实现(未优化版本）
这里按从小到大排序
- for(int i=0;i<n;i++)//比较n轮
- for(int j=0;j<n,j++)//n轮中每一轮比较n次
- {
- if(a[j]>a[j+1])
- {
- temp=a[j];
- a[j]=a[j+1];
- a[j+1]=temp;
- }
- }
代码实现(优化版本）
- for(int i=0;i<n;i++)//比较n轮
- for(int j=0;j<n-i;j++)//每一轮比较n-j次
- {
- if(a[j]>a[j+1])
- {
- temp=a[j];
- a[j]=a[j+1];
- a[j+1]=temp;
- }
- }
忽略我的排版，确实很糟糕，我会努力去改的
为什么可以这样优化呢？这就需要从机理来研究了，由于冒泡是每一次选出的是每一轮中的最大(小)的数，那么下轮开始，我们就不需要再将未排序的数再与已经排序的数进行比较了！
这里希望大家重视一下优化的版本，优化过后，时间复杂度会低些，这样程序运行时间就会减少，虽然在冒泡这里体现并不明显，但随着学习的深入，你会逐渐发现，算法的优劣（时间复杂度&&空间复杂度），对一个程序而言很重要，特别是在信息学竞赛中(才不会用冒泡这种低端算法呢）
02.直接选择排序
直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
摘自百度百科
ps.其实并不一定是从小到大，也可从大到小。
选择排序的时间复杂度也是O(n^2)
思想：也是和冒泡一样，进行多轮比较，但不一样的地方在于，经过每一次比较之后，每一轮会确定一个最小（大）的数对应的位置，最后才进行一次交换，相比之下，冒泡是一直在交换，事实上，冒泡和直接选择排序一样，比较低端，能不用尽量不用，尤其对长度较大的数组。
代码实现
- int temp;
- for(int i=0;i<n-1;i++)
- {
- int k=i;
- for(int j=i+1;j<n;j++)
- if(a[j]<a[k])
- k=j;//每一轮中选出最小的数组元素对应的下标
- temp=a[k];
- a[k]=a[i];
- a[i]=temp;
- }
动态图解
03.直接插入排序
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
摘自百度百科
直接插入排序的时间复杂度还是O(n^2)
思想：每次选择一个元素，将这个元素与数组中该元素之前所有的元素进行比较，然后将它插到合适的位置。
代码实现
- int i,j,temp;
- for ( i = 1; i < n; i++) {
- temp = a[i];//每一轮选出一个元素
- for ( j = i; j > 0 && a[j - 1] > temp; j--) {
- a[j] = a[j - 1];//与前面的元素比较大小，然后插进去，后面的元素退一位
- }
- a[j] = temp;
- }
动态图解
04.希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
摘自百度百科
在某些极端情况下，希尔排序的时间复杂度会达到O(n^2)
希尔排序的平均时间复杂度是O(n^(1.3—2))
思想：直接插入排序要进行多次的比较交换，如果说，一个数组中大部分元素都处于有序的状态下，那么就不需要进行多次的交换了。那么就需要先对数组进行一定的处理。
代码实现
以下是希尔增量下的希尔排序，关于希尔排序的增量，有很多种选择，例如Hibbard增量，这些增量有些是通过数学证明得到的，有些则是还没有得到证明的，人们确信正确的经验得出的。。个人感觉有点像孪生素数猜想那样的吧，但证明难度应该没有那么高。
- for (int gap= n/2; gap > 0; gap /= 2)//分组
- {
- for (int i = gap; i < n; i ++ )
- {
- int temp = a[i];
- int j; //这里基本上和插入排序差不多
- for (j = i; j >= gap && a[j - gap] > temp; j -= gap)
- a[j] = a[j - gap];
- a[j] = temp;
- }
- }
图解
ps.希尔排序的动图我在网上找不到，只能用图片代替了 对于这样的一个数组，进行分组，gap=n/2，然后每分好之后，再gap/=2，一直到gap=1，这个过程使得数组的整体有序性提高，从而使直接插入排序的工作量减少很多.
对于其它增量实现的，这里不贴出来了，因为，我不会写唉(逃