@Author: 张海拔
@Update: 2014-01-11
@Link: http://www.cnblogs.com/zhanghaiba/p/3514440.html
1 /* 2 *Author: ZhangHaiba 3 *Date: 2014-1-10 4 *File: basic_sort_algorithm.c 5 * 6 *a demo of basic sort algorithm including: 7 *bubble sort 8 *select sort 9 *insert sort 10 */ 11 12 #include <stdio.h> 13 #define N 512 14 15 //public 16 void bubble_sort(int*, int); 17 void select_sort(int*, int); 18 void insert_sort(int*, int); 19 void insert_sort2(int*, int); 20 void set_array(int*, int); 21 void show_array(int*, int); 22 //private 23 void swap(int*, int*); 24 25 int array[N]; 26 27 int main(void) 28 { 29 int n; 30 31 scanf("%d", &n); 32 set_array(array, n); 33 //basic sort algorithm 34 insert_sort(array, n); 35 show_array(array, n); 36 return 0; 37 } 38 39 void bubble_sort(int *a, int n) 40 { 41 int i, j; 42 43 for (i = 0; i < n-1; ++i) 44 for (j = 0; j < n-1-i; ++j) 45 if (a[j] > a[j+1]) 46 swap(&a[j], &a[j+1]); 47 } 48 49 void select_sort(int *a, int n) 50 { 51 int i, j, min_idx; 52 53 for (i = 0; i < n-1; ++i) { 54 min_idx = i; 55 for (j = i; j < n; ++j) 56 if (a[j] < a[min_idx]) 57 min_idx = j; 58 swap(&a[i], &a[min_idx]); 59 } 60 } 61 62 void insert_sort(int *a, int n) 63 { 64 int i, j, key; 65 66 for (i = 1; i < n; ++i) { 67 key = a[i]; 68 for (j = i-1; j >= 0 && a[j] > key; --j) 69 a[j+1] = a[j]; 70 a[j+1] = key; 71 } 72 } 73 74 //a simple and concise implementation of insert_sort 75 void insert_sort2(int *a, int n) 76 { 77 int i, j; 78 79 for (i = 1; i < n; ++i) 80 for (j = i-1; j >= 0 && a[j] > a[j+1]; --j) 81 swap(&a[j], &a[j+1]); 82 } 83 84 void set_array(int *a, int n) 85 { 86 int i; 87 88 for (i = 0; i < n; ++i) 89 scanf("%d", a+i); 90 } 91 92 void show_array(int *a, int n) 93 { 94 int i; 95 96 for (i = 0; i < n; ++i) 97 printf(i == n-1 ? "%d\n" : "%d ", a[i]); 98 } 99 100 void swap(int *a, int *b) 101 { 102 int tmp = *a; 103 *a = *b; 104 *b = tmp; 105 }
冒泡排序(bubble_sort)：
外层循环控制比较的轮数，只需比较n-1轮。因为——
内层循环控制每一轮的排序：比如第一轮，范围[0,n-1)中元素两两比较，使较大的在右边，最终最大的会在最右边。
而第二轮，显然遍历范围是[0, n-1-1)，此时i也刚好是1。所以有n-1-i。
简单选择排序(select_sort):
i从[0, n-1)，每次从i到n-2选出当前最小的元素，与i位置交换，显然i == n-1时，不需要再选择（剩下的毫无疑问是最大的）
因此，外层循环n-1次，内层循环从i到n-2中选择最大的元素保存其下标，然后将此元素与下标为i的元素交换
直接插入排序(insert_sort)：
思想是，只有一个元素时肯定是有序的。外层循环一次就能使有序元素多一个，怎么做到多一个呢？
通过插入即可，但插入会导致一些元素往后移，所以从后往前遍历。
若当前元素a[j]>key往后移动一个位置（第一次会覆盖掉自身，所以先保存这个key)，
否则（或者已经遍历完成，此时i == -1）在当前位置的后一个位置插入key。
因此i从[1, n)，选择a[i]作为待插入的关键字key，然后层次循环找到适合的位置的同时移动了比key大的那些元素，最后插入。
三个算法的比较：
我的实现中，冒泡排序和直接插入排序都可以用三行代码写完，简单选择排序则长了点。
而性能方面，虽然三者最坏情况都是O(n^2)，但冒泡排序和直接插入排序最好情况是O(n)，简单选择排序最好情况也是O(n^2)
最关健的是，冒泡排序和直接插入排序显然是稳定的，而简单选择则是不稳定的。举个例子(2, 2, 1)，一次排序后是(1, 2, 2)，显然2的相对次序改变了。
Hint:算法的稳定性是指：原始数据中相同的关键字的相对次序在排序后没有改变，则称这种排序算法是稳定的。
综合来看：简单选择排序比较挫了（代码长度、最好情况、稳定性都劣势），冒泡排序居中，直接插入排序对于数据“基本有序”则表现很好。
三个算法的改进：
（1）快速排序的基于冒泡排序来改进的，不过这次冒的泡不是最轻的，而是期望这个泡重量夹在中间，这样可以通过分治法使效率提升到O(n*logn)，但这种改进丢失冒泡稳定的特性。
（2）堆排序是基于选择排序改进，首先堆是指二叉堆这个数据结构，这个数据结构可以以O(logn)的效率求出最值，从而使选择选择排序效率提升到O(n*logn)，这种改进也丢失了简单选择稳定的特性。
（3）希尔排序是基于简单选择排序的改进，改进的基本原理是：当数组“基本有序”时，直接插入效率接近O(n)，然后通过隔空进行直接插入排序减小问题规使得相对效率提升，而随着隔空距离的减小，数据的“基本有序”的程序却在增大。通过数学证明，平均情况下希尔排序的效率提升到了O(n^(1.3))。
最后，对排序算法来个分类——
（1）交换类排序：冒泡排序、快速排序
（2）选择类排序：简单选择排序、堆排序
（3）插入类排序：直接插入排序、希尔排序
（4）归并类排序：归并排序