二.冒泡排序

定义

冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

过程

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

经过i次扫描后，数列的末尾i项必然是最大的i项，因此冒泡排序最多需要扫描n-1遍数组就能完成排序。

性质

稳定性

冒泡排序是一种稳定的排序算法。

时间复杂度

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 。

在最坏情况下，冒泡排序要执行(n-1)*n/2次交换操作，时间复杂度为 。

冒泡排序的平均时间复杂度为  。 

代码实现

void bubble_sort(int *a,int n){bool flag=true;while(flag){flag=false;for(int i=1;ia[i+1]){flag=true;int t=a[i];a[i]=a[i+1];a[i+1]=t;}}}
}

三.插入排序 

本页面将简要介绍插入排序。

定义

插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。

性质

稳定性

插入排序是一种稳定的排序算法。

时间复杂度

插入排序的最优时间复杂度为 ，在数列几乎有序时效率很高。 

插入排序的最坏时间复杂度和平均时间复杂度都为 。 

代码实现

void insertion_sort(int* a,int n){for(int i=2;i<=n;++i){int key=a[i];int j=i-1;while(j>0&&a[j]>key){a[j+1]=a[j];--j;}a[j+1]=key;}
}

 四.计数排序

Warning

本页面要介绍的不是基数排序

定义

计数排序（英语：Counting sort）是一种线性时间的排序算法。

过程

计数排序的工作原理是使用一个额外的数组C ，其中第i个元素是待排序数组 A中值等于i 的元素的个数，然后根据数组C来将A中的元素排到正确的位置。

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的 前缀和；
3. 利用出现次数的前缀和，从右至左计算每个数的排名。

计算前缀和的原因

阅读本章内容只需要了解前缀和概念即可

直接将C中正数对应的元素依次放入A中不能解决元素重复的情形。

我们通过为额外数组C中的每一项计算前缀和，结合每一项的数值，就可以为重复元素确定一个唯一排名：

额外数组C中每一项的数值即是该 key 值下重复元素的个数，而该项的前缀和即是排在最后一个的重复元素的排名。

如果按照A的逆序进行排列，那么显然排序后的数组将保持A的原序（相同 key 值情况下），也即得到一种稳定的排序算法。

性质

稳定性

计数排序是一种稳定的排序算法。

时间复杂度

计数排序的时间复杂度为 ，其中w代表待排序数据的值域大小。

代码实现

const int N=100010;
const int W=100010;
int n,w,a[N],cnt[W],b[N];
void counting_sort(){memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;++i) ++cnt[a[i]];for(int i=1;i<=w;++i) cnt[i]+=cnt[i-1];for(int i=n;i>=1;--i) b[cnt[a[i]]--]=a[i];
}

 五.基数排序

定义

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。

过程

基数排序的工作原理是将待排序的元素拆分为k个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 k关键字进行稳定排序，再对第k-1关键字进行稳定排序，再对第k-2关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

性质

稳定性

基数排序是一种稳定的排序算法。

时间复杂度

一般来说，如果每个关键字的值域都不大，就可以使用 计数排序 作为内层排序，此时的复杂度为 ，其中为第i关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的排序而无需使用基数排序了。

空间复杂度

基数排序的空间复杂度为 。

算法实现

const int N=100010;
const int W=100010;
const int K=100;
int n,w[K],k,cnt[W];
struct Element{int key[K];bool operator<(const Element& y)const{for(int i=1;i<=k;++i){if(key[i]==y.key[i])continue;return key[i]=1;--i) b[cnt[a[i].key[p]]--]=a[i];memcpy(a,b,sizeof(a));
}
void radix_sort(){for(int i=k;i>=1;--i){counting_sort(i);}
}

 本来已经准备好的动图他突然传不上来了,只好在baike.baidu.com上面寻找(复制).所以对于萌新来说比较难理解(我就是萌新).