C语言经典排序方法及动图演示

#include "sort.h" #include "math.h" #define EXCHANGE(num1, num2) { num1 = num1 ^ num2; num2 = num1 ^ num2; num1 = num1 ^ num2;} void swap( int* a, int* b ) { int t; t = *a; *a = *b; *b = t; } /* 一.冒泡排序 冒泡排序原理很容易理解，就是重复地走访过要排序的元素列，依次比较两个相邻的元素，顺序不对就交换，直至没有相邻元素需要交换，也就是排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 冒泡排序是一种稳定排序算法。 时间复杂度:最好情况(初始情况就是正序)下是o(n),平均情况是o(n2) */ void bubbleSort( int num[], int count ) { for( int i = 0; i < count - 1; i++ ) { for( int j = 0; j < count - i - 1; j++ ) { if( num[j] > num[j + 1] ) { //EXCHANGE( num[j], num[j + 1] ); //通过宏定义交换两个值 swap( &num[j], &num[j + 1] ); //通过函数交换两个值 } } } } /* 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。 由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。 */ void bubbleSort_1( int num[], int count ) { int i = count - 1; //初始时,最后位置保持不变 while( i > 0 ) { int pos = 0; //每趟开始时,无记录交换 for( int j = 0; j < i; j++ ) { if( num[j] > num[j + 1] ) { pos = j; //记录交换的位置 EXCHANGE( num[j], num[j + 1] ); } } i = pos; //为下一趟排序作准备 } } /* 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值, 我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。 */ void bubbleSort_2( int num[], int count ) { int low = 0; int high = count - 1; //设置变量的初始值 int j; while( low < high ) { for( j = low; j < high; ++j ) //正向冒泡,找到最大者 { if( num[j] > num[j + 1] ) { EXCHANGE( num[j], num[j + 1] ); } } --high; //修改high值, 前移一位 for( j = high; j > low; --j ) //反向冒泡,找到最小者 { if( num[j] < num[j - 1] ) { EXCHANGE( num[j], num[j - 1] ); } } ++low; //修改low值,后移一位 } } /* 二、选择排序 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素， 存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。 比较次数O(n2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次； 最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快 选择排序是不稳定的排序方法。 时间复杂度：最好和平均情况下都是O(n2） */ void selectSort( int num[], int count ) { for( int i = 0; i < count; i++ ) { int min = i; for( int j = i; j < count; j++ ) { if( num[j] < num[min] ) { min = j; } } if( i != min ) { EXCHANGE( num[i], num[min] ); //可以看出，最多交换count - 1次 } } } /* 三、二元选择排序 简单选择排序，每趟循环只能确定一个元素排序后的定位。 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置, 从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可. */ void selectSortBinary( int num[], int count ) { int i, j, max, min; //下标min max 指向最小和最大元素 int maxtmp = 0, mintmp = 0; for( i = 0; i < count / 2; i++ ) //i跑 n/2趟排序就会排序完成 { min = max = i; //先将max和min都指向待排序的第一个元素 for( j = i; j < count - i; j++ ) { if( num[j] < num[min] ) //用j找出最大值和最小值,分别让max 和min指上来 { min = j; continue; } if( num[j] > num[max] ) { max = j; } } maxtmp = num[max]; //备份当前最大值和最小值 mintmp = num[min]; num[min] = num[i]; // 队首元素放在最小值下标处 num[max] = num[count - i - 1]; //队尾元素放在最大值下标处 num[i] = mintmp; //最小值放到队首 num[count - i - 1] = maxtmp; //最大值放到队尾 } } /* 四、直接插入排序 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序， 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止 直接插入排序是稳定的排序算法。 时间复杂度：最好情况(初始情况就是正序)下是o(n),平均情况是o(n2) --------------------- */ void insertSort( int num[], int count ) { int i, j; for( i = 1; i < count; i++ ) { if( num[i] < num[i - 1] ) { int temp = num[i]; for( j = i; j > 0; j-- ) //num[i] 前面的每一个数字和num[i]比较 { if( num[j - 1] > temp ) //如果num[i]前面的值比num[i]大 { num[j] = num[j - 1];//将大的值向后挪一位 } else { break; } } num[j] = temp; //将num[i]位置的值放到最后一次挪位置的地方 } //也就是将比num[i]大的值依次向后挪一位,将num[i]直接放到前面 } } /* 五、二分插入排序 由于在插入排序过程中，待插入数据左边的序列总是有序的，针对有序序列，就可以用二分法去插入数据了，也就是二分插入排序法。适用于数据量比较大的情况。 二分插入排序的算法思想： 算法的基本过程： （1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间， 反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半； （2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方； （3）确定位置之后，将整个序列后移，并将元素插入到相应位置。 二分插入排序是稳定的排序算法。 时间复杂度：最好情况(刚好插入位置为二分位置)下是o(nlogn),平均情况和最坏情况是o(n2) */ void insertSortBinary( int num[], int count ) { int i, j; for( i = 1; i < count; i++ ) { if( num[i] < num[i - 1] ) { int temp = num[i]; int left = 0, right = i - 1; while( left <= right ) { int mid = ( left + right ) / 2; if( num[mid] < temp ) { left = mid + 1; } else { right = mid - 1; } } //只是比较次数变少了，交换次数还是一样的 for( j = i; j > left; j-- ) { num[j] = num[j - 1]; } num[left] = temp; } } } /* 六、希尔(插入)排序 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序完成。 希尔排序是非稳定排序算法。 时间复杂度：O(n^（1.3—2）) */ void