围观大神十大经典排序算法（动图演示）/*9. 排序
为了讲清楚排序算法的代码，我先提供一个用于排序用的顺序表结构，此结构也将用于之后我们要讲的所有排序算法； */ #define MAXSIZE 10 typedef struct { //用于存储要排序数组，r[0]用作哨兵或临时变量 int r[MAXSIZE + 1]; //用于记录顺序表的长度 int length; } SqList; //另外，由于排序最最常用到的操作是数组两元素的交换，我们将它写成函数，在之后的讲解中会大量的用到。 //交换L中数组r的下标为i和j的值 void swap(SqList *L, int i, int j) { int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } /* 9.3 冒泡排序 冒泡排序（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]) { //交换L->r[i]与L->r[j]的值 swap(L, i, j); } } } } /* 这段代码严格意义上来说，不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录”的冒泡排序思想， 他更应该是最最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果 大则交换，这样第一位置的关键字在一次循环后一定变成最小值。 */ //正宗的冒泡排序算法 void BubbleSort(SqList *L) { int i,j; for(i=1; i < L->length; i++) { //这里j是从后往前循环,直到“最小值”将其移至第i的位置；当然你也可以让j=i从前向后循环，直到“最大值”将其移至第length-i的位置。
for(j = L->length-1; j >= i; j--) { //若前者大于后者（注意这里与上一算法差异） if(L->r[j] > L->r[j+1]) { //交换L->r[j]与L->r[j+1]的值 swap(L, j, j+1); } } } } //冒泡排序优化 void BubbleSort2(SqList *L) { int i,j; //flag用来作为标记 Status flag = TRUE; //若flag为true说明有过数据交换，否则停止循环 for(i=1; i < L->length && flag; i++) { //初始化为false flag = FALSE; for(j = L->length-1; j >= i; j--) { if(L->r[j] > L->r[j+1]) { //交换L->r[j]与r[j+1]的值 swap(L, j, j+1); //如果有数据交换，则flag为true flag = TRUE; } } } } /* 9.4 简单选择排序 简单选择排序算法（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 min = j; } //若min不等于i，说明找到最小值，交换 if(i != min) //交换L->r[i]与L->r[min]的值 swap(L, i, min); } } /* 简单选择排序复杂度分析 从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。 分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多性能上略优于冒泡排序。 */ /* 9.5 直接插入排序 直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中， 从而得到一个新的、记录数增1的有序表。 */ //对顺序表L作直接插入排序 //这个代码树上是有问题的吧？ void InsertSort(SqList *L) { int i,j; //r[0]用作哨兵或临时变量，作用是作为交换元素的中介 r[1]为第一个数值元素 for(i=2; i <= L->length; i++) { //需将L->r[i]插入有序子表 if(L->r[i] < L->r[i-1]) { //设置哨兵，为要移动的元素 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]; //交换位置 小元素前移 } } } /* 1.程序开始运行，此时我们传入的SqList参数的值为length=6，r[6]={0,5,3,4,6,2}，其中r[0]=0将用于 后面起到哨兵的作用。 2. 第4~13行就是排序的主循环。i从2开始的意思是我们假设r[1]=5已经放置好位置，后面的牌其实就是插入 到它的左侧还是右侧的问题。 3.第6行，此时i=2，L->r[i]=3比L->r[i-1]要小，因此执行第8~11行的操作。第8行我们将L->r[0]赋值为 L->r[i]=3的目的是为了起到第9~10行的循环终止的判断依据... */ /* 9.6 希尔排序 希尔排序是对直接插入排序的改进版本，改进后可以增加效率，总的来说先粗分为几组（比如3组），再直插排序。 对直接插入排序的复杂度分析可得，最好的情况，也就是要排序的表本身就是有序的；如果排序记录是随机的， 那么根据概率相同的原则，平均比较和移动次数约为(n^2)/4次。因此我们得出直接插入排序法的时间复杂度为 O(n^2)。从这里也看出，同样的O(n^2)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。 因此让数据基本有序就成了提高直接插入排序算法的关键。 */ //希尔排序算法代码如下： void ShellSort(SqList *L) { int i,j; 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[0] = L->r[i]; for(j=i-increment; j>0 && L->r[0] < L->r[j]; j-=increment) //记录后移，查找插入位置 L->r[j+increment] = L->r[j]; //j+increament就是i //插入 L->r[j+increment] = L->r[0]; } } } while (increment > 1); }