本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/%e5%b8%b8%e8%a7%81%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e6%80%bb%e7%bb%93/
希尔排序算法 1） 希尔排序原理： 首先取一个小于n的增量gap（一般选择数组长度的一半）,将待排数据分成n/gap个组，其中距离为gap的数据分在同一个组内。在组内进行直接插入排序，取第二个增量gap/2重复上述的分组和排序，直至所取的增量gap=1，即所有记录放在同一组中进行直接插入排序为止。 2） 希尔排序算法语言描述：
void shellsort(int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2) //步长
for (i = 0; i < gap; i++) //直接插入排序
{
for (j = i + gap; j < n; j += gap)
if (A[j] < A[j - gap])
{
int temp = A[j];
int k = j - gap;
while (k >= 0 && A[k] > temp)
{
A[k + gap] = A[k];
k -= gap;
}
A[k + gap] = temp;
}
}
}
3）希尔排序算法的性能分析 希尔排序算法是一个时间复杂度为O(n*n)的排序算法，但是一种不稳定的排序算法。希尔排序的空间复杂度为O(1)。希尔排序的执行时间依赖于增量序列。
桶排序算法 1）桶排序算法原理： 首先将这个序列划分成M个的子区间(桶)，本程序将序列划分为n/10个桶，每个桶中有10个元素 。第n个元素映射到第n/10的桶中。对每个桶中的所有元素进行插入排序。然后依次枚举输出A[0]….A[n/10]中的全部内容即是一个有序序列。 桶采用vector数组的结构实现，插入查找方便高效，并支持动态增长。 2）桶排序算法语言描述：
void bucket_sort(int len)
{
vector v[10001];//模拟链表
int i, j, temp, l, index;
for(i = 0; i < len; i++) { l = A[i] / 10; v[l].push_back(A[i]); //放入桶中该区间最后位置 if(v[l].size() > 1) {
//对新加入的数排序
for(j = v[l].size()-1; j > 0; j--) {
if(v[l][j] >= v[l][j-1])
break;
temp = v[l][j];
v[l][j] = v[l][j-1];
v[l][j-1] = temp;
}
}
}
index = 0;
for(i = 0; i < len/10 + 1; i++) {//搜集数据
for(j = 0; j < v[i].size(); j++) {
A[index++] = v[i][j];
}
}
}
3）桶排序算法的性能分析 桶排序的平均时间复杂度为O(n+k)，最差情况下时间复杂度为O(nn)。桶排序的最好空间复杂度为O(n)，最差空间复杂度为O(nk)。桶排序是一种稳定的排序算法。 桶排序是排序算法中性能较好的排序算法。数据显示出桶排序只比快速排序和合并排序慢。
冒泡排序算法 1） 冒泡排序原理： 循环两两比较相邻待排序数据元素的大小，若发现两个数据元素是逆序的则进行交换，直到没有逆序的数据为止。为了避免双重循环中的无用执行步骤，设置哨兵进行标记，若一趟扫描以后没有交换，则哨兵不变，可以退出程序。 2） 冒泡排序算法语言描述：
void BubbleSort(int n)
{
int j,i;
bool flag = true;
int temp;
for (i = 0;i < n && flag ; i++)
{
flag = false;
for (j = 1; j < n - i ; j++) if (A[j - 1] > A[j])
{
temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
flag = true;
}
}
}
5）冒泡排序算法的性能分析 冒泡排序是一个时间复杂度为O(nn)的排序算法。在最好情况下时间复杂度为O(n),在最坏情况下时间复杂度为O(nn)。冒泡排序的空间复杂度为O(1),而且冒泡排序是一种稳定的排序算法。 数据显示出：当数据量比较少时，冒泡排序性能比较差，在数据量较大时冒泡排序的速度慢的让人无法接受。当数据量特别大时，冒泡排序性能差到惨绝人寰！
合并排序算法 1）合并排序的原理： 遵循分治法的模式。在分解阶段分解: 将待排序的 n 个元素的序列分解成各具n/2个元素的两个子序列。解决: 使用归并排序对两个子序列进行递归排序。合并: 合并两个已经排好序的子序列,生成排序答案。 2）合并排序代码描述如下：
void Merge(int *A,int p,int q,int r){
int n1,n2,i,j,k;
n1=q-p+1;
n2=r-q;
for(i=1;i<=n1+1;i++){
L[i]=0;
}
for(j=1;j<=n2+1;j++){
R[j]=0;
}
for(i=1;i<=n1;i++){
L[i]=A[p+i-1];
}
for(j=1;j<=n2;j++){
R[j]=A[q+j];
}
L[n1+1]=MAX;
R[n2+1]=MAX;
i=1;
j=1;
for(k=p;k<=r;k++){
if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
j++;
}
}
}
void Merge_Sort(int *A,int p,int r){
int q;
if(p<r){
q=(p+r)/2;
Merge_Sort(A,p,q);
Merge_Sort(A,q+1,r);
Merge(A,p,q,r);
}
}
3）合并排序算法的性能分析 合并排序是一个时间复杂度为O(nlgn)的排序算法，而且是一种稳定的排序算法。在最好和最坏情况下的时间复杂度都是O(nlgn)，而合并排序的空间复杂度为O(n);
插入排序算法 1）插入排序原理： 该算法原址排序输入的数，依次将待排的数据插入到已经排好的数组中合适的位置，并通过平移元素使数组依然是有序的，直到所有待排数据都插入完毕，则此时的数组就是有序的。 2）插入排序算法代码描述：
void isort3(int l , int u)
{
int j;
for(int i = l ; i <= u ;i++){
int t = A[i];
for(j = i ; j > 0 && A[j-1] > t ;j--)
A[j] = A[j-1];
A[j] = t;
}
}
3）插入排序算法的性能分析 插入排序是一个时间复杂度为O(n*n)的排序算法，而且是一种稳定的排序算法。插入排序的空间复杂度为O(1)。在最好情况下，待排数据为升序排列好的数据，此时插入算法只要进行的比较操作需（n-1）次即可，最坏况下，待排数据为逆序，此时需要进行的比较共有n(n-1)/2次。 数据显示：在数据数量较大时，插入排序只优于冒泡排序算法。而在数据数量较少时，插入排序性能很好，这也是快速排序可以采用插入排序进行小粒度时优化的原因。
