一、排序基本概念
排序是处理数据的一种最常见的操作，所谓排序就是将数据按某字段规律排列，所谓的字段就是数据节点的其中一个属性。比如一个班级的学生，其字段就有学号、姓名、班级、分数等等，我们既可以针对学号排序，也可以针对分数排序。
1、稳定性
在一组无序数据中，若两个待排序字段一致的数据，在排序前后相对位置不变，则称排序算法是稳定的，否则是不稳定的。
2、内排序与外排序
如果待排序数据量不大，可以一次性全部装进内存进行处理，则称为内排序，若数据量大到无法一次性全部装进内存，而需要将数据暂存外存，分批次读入内存进行处理，则称为外排序。
3、性能分析
不同的排序算法性能不同，详细性能数据如下表所示： 
从表中可以得到一些简单的指导思路：
- 选择排序、插入排序和冒泡排序思路简单，但时间效率较差，只适用于数据样本较小的场合，这几种算法的好处是不需要额外开辟空间，空间复杂度是常量。
- 希尔排序是插入排序的改进版，在平均情况下时间效率要比直接插入法好很多，也不需要额外开辟空间，要注意的是希尔排序是不稳定排序。
- 快速排序是所有排序算法中时间效率最高的，但由于快排是一种递归运算，对内存空间要求较高，当数据量较大时，会消耗较多的内存。
二、插入排序
1、思路
假设前面已经有i节点是有序的，那么就从第i+1个节点开始，插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的，因此从第2个开始，不断插入前面的有序序列，直到全部排列完毕。
2、时间复杂度分析
假设总共有n个节点，那么总共需要将n−1个节点插入到有序序列中，而插入节点时需要找到合适的位置，显然这个查找的过程时间复杂度是O(n−i)，因此插入排序的时间复杂度是O(n−1)(n−i)，即O(n^2)
3、示例代码
#include <stdio.h> #include <stdbool.h> int swap_count = 0; int comp_count = 0; void show(int data[], int len) { int i; for(i=0; i<len; ++i) { printf("%d\t", data[i]); } printf("\n"); } //小到大排序 void insertionSort(int data[], int len) { if(len <= 1) return; int i, j; for(i=1; i<len; i++) { int tmp = data[i]; for(j=i-1; j>=0; j--) { comp_count++; if(data[j] < tmp) { break; } else { swap_count++; data[j+1] = data[j]; } } swap_count++; data[j+1] = tmp; } } int main(int argc, char **argv) { srand(time(NULL)); int i, data[100]; for(i=0; i<100; ++i) { data[i] = rand() % 1000; } printf("随机序列: "); show(data, 100); printf("插入排序: "); insertionSort(data, 100); show(data, 100); printf("总共比较次数: %d\n", comp_count); printf("总共移动次数: %d\n", swap_count); return 0; }
4、代码分析
三、冒泡排序
1、概念
冒泡排序基于这样一种简单的思路：从头到尾让每两个相邻的元素进行比较，顺序就保持位置不变，逆序就交换位置。可以预料，经过一轮比较，序列中具有“极值”的数据，将被挪至序列的末端。
2、时间复杂度
假如序列中有n个数据，那么在最极端的情况下，只需要经过n−1轮的比较，则一定可以将所有的数据排序完毕。冒泡法排序的时间复杂度是O(n2)
最好:12345678
最坏(完全逆序): 87654321
3、思路
总思路先把最大的往右边挤,把第二大往最右边第二位置挤…
逐对比较,并交换
4、示例代码
#include <stdio.h> int comp_count = 0; // 数据比较次数 int swap_count = 0; // 数据交换次数 void show(int data[], int len) { int i; for(i=0; i<len; ++i) { printf("%d\t", data[i]); } printf("\n"); } void swap(int *a, int *b) { swap_count++; int tmp; tmp = *a; *a = *b; *b = tmp; } void bubbleSort(int data[], int len) { int k=0; while(1) { bool done = true; int i; for(i=0; i<len-1-k; i++) { comp_count++; if(data[i] <= data[i+1]) { continue; } swap(&data[i], &data[i+1]); done = false; } if(done) break; k++; } } int main(int argc, char **argv) { srand(time(NULL)); int i, data[100]; for(i=0; i<100; ++i) { data[i] = rand() % 1000; } printf("随机序列: "); show(data, 100); bubbleSort(data, 100); // 按升序排列 printf("冒泡排序: "); show(data, 100); printf("总共比较次数: %d\n", comp_count); printf("总共交换次数: %d\n", swap_count); return 0; }
5、代码分析
注意：
上述冒泡排序中，对算法做了优化，主要有两点：
- 由于每一趟比较后，都至少有1个“极值”被移至末端，因此第i趟比较只需n−i次 对比次数优化
- 当发现某一趟比较中全部为顺序时，则意味着序列已经有序，则可以提前退出 轮次优化
四、快速排序
1、概念
快排是一种递归思想的排序算法，先比较其他的排序算法，它需要更多内存空间，但快排的语句频度是最低的，理论上时间效率是最高的。
2、思路
在待排序序列中随便选取一个数据，作为所谓“支点”，然后所有其他的数据与之比较，以从小到大排序为例，那么比支点小的统统放在其左边，比支点大的统统放在其右边，全部比完之后，支点将位与两个序列的中间，这叫做一次划分。
一次划分之后，序列内部也许是无序的，但是序列与支点三者之间，形成了一种基本的有序状态，接下去使用相同的思路，递归地对左右两边的子序列进行排序，直到子序列的长度小于等于1为止。
3、示例代码
#include <stdio.h> int comp_count = 0; int swap_count = 0; void show(int data[], int len) { int i; for(i=0; i<len; ++i) { printf("%d\t", data[i]); } printf("\n"); } void swap(int *a, int *b) { swap_count++; int tmp; tmp = *a; *a = *b; *b = tmp; } int partition(int data[], int len) { if(len <= 1) return 0; int i = 0; int j = len-1; while(i < j) { // 从右向左比较，顺序j--，逆序交换 comp_count++; while(data[i]<=data[j] && i<j) j--; swap(&data[i], &data[j]); // 从左向右比较，顺序i++，逆序交换 comp_count++; while(data[i]<=data[j] && i<j) i++; swap(&data[i], &data[j]); } return i; } void quickSort(int data[], int len) { if(len <= 1) return; int pivot = partition(data, len); quickSort(data, pivot); quickSort(data+pivot+1, len-pivot-1); } int main(int argc, char **argv) { srand(time(NULL)); int i, data[100]; for(i=0; i<100; ++i) { data[i] = rand() % 1000; } printf("随机序列: "); show(data, 100); printf("快速排序: "); quickSort(data, 100); show(data, 100); printf("总共比较次数: %d\n", comp_count); printf("总共交换次数: %d\n", swap_count); return 0; }
五、希尔排序
1、比较插入排序和希尔排序
插入排序:
逐步的局部有序到全局有序
希尔排序:
从整体宏观上有序逐步细节到局部的有序
2、概念
希尔排序是一种改进版的插入排序，普通的插入排序算法中，是从第2个节点开始，依次插入到有序序列中，这种做法虽然“一次成形”，但研究发现时间效率上这么做并不划算，更“划算”的做法是这样的：不严格一个个插入使之有序，而是拉开插入节点的距离，让它们逐步有序
3、示例代码
#include <stdio.h> #include <math.h> int comp_count = 0; int swap_count = 0; void show(int data[], int len) { int i; for(i=0; i<len; ++i) { printf("%d\t", data[i]); } printf("\n"); return; } // 起点 节点个数 间距 void insert_sort(int data[], int len, int delta) { if(len <= 1) return; for(int i=delta; i<len*delta; i+=delta) { int j, tmp = data[i]; for(j=i-delta; j>=0; j-=delta) { comp_count++; if(data[j] < tmp) break; swap_count++; data[j+delta] = data[j]; } data[j+delta] = tmp; } } void shell_sort(int data[], int len) { if(len <= 1) return; for(int delta=len/2; delta>0; delta/=2) { for(int i=0; i<delta; ++i) { // 起点 节点个数 间距 insert_sort(data+i, len/delta, delta); } } } int main(void) { // 准备产生一些随机数 srand(time(NULL)); int i, data[100]; for(i=0; i<100; i++) { int exp = (int)pow(10, rand()%3+3); data[i] = rand()%exp; } printf("随机序列: "); show(data, 100); printf("希尔排序: "); shell_sort(data, 100); show(data, 100); printf("总共比较次数: %d\n", comp_count); printf("总共移动次数: %d\n", swap_count); return 0; }
