排序的基本概念
假设含有n个记录的序列为｛r1,r2,……,rn｝,其相应的关键字分别为｛k1,k2,……,kn｝,需确定1，2，……,n的一种排序p1,p2,……,pn,使其相应的关键字满足kp1≤kp2≤……≤kpn非递减（或非递增）关系，即使得序列称为一个按关键字有序的序列｛rp1,rp2,……,rpn｝,这样的操作就称为排序。
排序的稳定性
假设ki=kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中ri领先于rj(即i<j)。如果排序后ri仍领先于rj,则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。
内排序是在排序的整个过程中，待排序的所有记录全部被放置在内存中，外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外寸之间多次交换数据才能进行。
冒泡排序（Bubble Sort)，一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
/* 对顺序表L作交换排序（冒泡排序初级版） */ void BubbleSort0(SqList *L) { int i,j; for(i=1;i<L->length;i++) { for(j=i+1;j<=L->length;j++) { if(L->r[i]>L->r[j]) { swap(L,i,j);/* 交换L->r[i]与L->r[j]的值 */ } } } }
这段代码严格意义上说，不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”的冒泡。
/* 严格的冒泡算法 */ void BubbleSort(SqList *L) { int i,j; Status flag=TRUE; /* flag用来作为标记 */ for(i=1;i<L->length && flag;i++) /* 若flag为true说明有过数据交换，否则停止循环 */ { flag=FALSE; /* 初始为False */ for(j=L->length-1;j>=i;j--) { if(L->r[j]>L->r[j+1]) { swap(L,j,j+1); /* 交换L->r[j]与L->r[j+1]的值 */ flag=TRUE; /* 如果有数据交换，则flag为true */ } } } }
冒泡排序算法的时间复杂度为O(n2)。
简单选择排序法（Simple Selection Sort)就是通过n-i次关键字之间的比较，从n-i+1个记录总选择出关键字最小的记录，并和第i(1≤i≤n）个记录交换之。
/* 对顺序表L作简单选择排序 */ void SelectSort(SqList *L) { int i,j,min; for(i=1;i<L->length;i++) { min = i; /* 将当前下标定义为最小值下标 */ for (j = i+1;j<=L->length;j++)/* 循环之后的数据 */ { if (L->r[min]>L->r[j]) /* 如果有小于当前最小值的关键字 */ min = j; /* 将此关键字的下标赋值给min */ } if(i!=min) /* 若min不等于i，说明找到最小值，交换 */ swap(L,i,min); /* 交换L->r[i]与L->r[min]的值 */ } }
时间复杂度依然为O(n2)。
直接插入排序(Straight Insertion Sort)的基本操作是讲一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
/* 对顺序表L作直接插入排序 */ void InsertSort(SqList *L) { int i,j; for(i=2;i<=L->length;i++) { if (L->r[i]<L->r[i-1]) /* 需将L->r[i]插入有序子表 */ { L->r[0]=L->r[i]; /* 设置哨兵 */ for(j=i-1;L->r[j]>L->r[0];j--) L->r[j+1]=L->r[j]; /* 记录后移 */ L->r[j+1]=L->r[0]; /* 插入到正确位置 */ } } }
时间复杂度依然是O(n2)。
虽然时间复杂度均为O(n2),但上述三种排序算法，在性能上还是略有差异，一般来说，直接插入排序法略优于简单选择排序，简单选择排序略优于冒泡排序。
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
希尔排序的关键并不是随便分组后各自排序，而是将相隔某个”增量“的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
/* 对顺序表L作希尔排序 */ void ShellSort(SqList *L) { int i,j,k=0; int increment=L->length; do { increment=increment/3+1;/* 增量序列 */ for(i=increment+1;i<=L->length;i++) { if (L->r[i]<L->r[i-increment])/* 需将L->r[i]插入有序增量子表 */ { L->r[0]=L->r[i]; /* 暂存在L->r[0] */ for(j=i-increment;j>0 && L->r[0]<L->r[j];j-=increment) L->r[j+increment]=L->r[j]; /* 记录后移，查找插入位置 */ L->r[j+increment]=L->r[0]; /* 插入 */ } } printf(" 第%d趟排序结果: ",++k); print(*L); } while(increment>1); }
增量的选择是希尔排序的重要部分。只要最终增量为1任何增量串行都可以工作。算法最开始以一定的增量进行排序。然后会继续以一定增量进行排序，最终算法以增量为1进行排序。当增量为1时，算法变为插入排序，这就保证了数据一定会被排序。
步长即增量。
排序 之 冒泡排序 简单选择排序 直接插入排序 希尔排序,布布扣,bubuko.com
原文：http://www.cnblogs.com/xingchenfeng/p/3726364.html