1、插入排序与希尔排序 定理：通过交换相邻元素进行排序的任何算法平均需要Ω(N^2) 因此，冒泡、插入、选择排序平均复杂度都是Ω(N^2)
希尔排序是插入排序的改进情况，通过交换相距较远元素，每次交换就可以消除多个逆序。 因此突破了二次时间屏障。
//插入排序 static void Insertion(int data[], int len) { if (data == NULL || len == 0) return; int j; for (int i = 0; i < len; i++) { int target = data[i]; //待插入的data[i], data[0] 到data[i-1]是有序的，新加入data[i]。 for ( j = i; j > 0 ; j--) { if ( target < data[j - 1]) data[j] = data[j - 1];//比target 大的，都向后移动 else break; } data[j] = target;//data[i]插入正确位置 } }希尔排序
// 完成间隔为increment时的插入排序 static void shellInsert(int data[], int len, int increment) { int j, target; for (int i = increment; i < len; i++) { target = data[i]; //假设 0 到 i-1 的增量序列是有序，i for ( j = i; j >= increment; j = j - increment) { if (target < data[j - increment] ) data[j] = data[j - increment]; //向后挪动 else break; } data[j] = target; //data[i]插入正确位置 } } //设置增量序列，流行 static void ShellSort(int data[], int len) { if (data == NULL || len == 0) return; for (int increment = len / 2; increment > 0; increment = increment/2) { shellInsert(data, len, increment); } }2、简单选择排序 与 堆排序 选择排序思路：每次选择一个最小（大）的数，与有序序列后面的一个元素（第一个不有序的元素）做交换。 可以看出本算法： 1.简单排序算法是不稳定的。这个有点不好直接看出来，因为寻在最小值时是依次比较的，这个过程不会影响算法的稳定性，但是在交换时，由于交换位置的不确定性，会导致算法出现不稳定的情况：如{3*,3,1}–>{1,3,3*}。总之简单选择排序是不稳定的。最有一点，如果采用插入方式替换交换，那么这个算法就是稳定得了，可惜时间复杂度会上去。 2.时间复杂度，这个明显会一直是O(n^2)，两个循环会一直执行。 3.空间复杂度，O（1）保持最小或最大值.
简单选择排序
static void Selection(int data[], int len) { if (data == NULL || len == 0) return; int minIndex = 0; for (int i = 0; i < len - 1;i++) { minIndex = i;//选出最小数标号 for (int j = i+1; j < len ;j++) { if (data[j] < data[minIndex]) minIndex = j; } if (minIndex != i) {//交换 int tmp = data[minIndex]; data[minIndex] = data[i]; data[i] = tmp; } } }堆排序 堆排序是指利用堆这种数据结构所设计的一种选择排序算法。 堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
补充知识： 堆的性质： 1、结构性：堆是一棵完全二叉树 2、堆序性：任意节点都小于（大于）它的所有后裔 完全二叉树的规律： 对于数组任意位置i 上的元素，其左儿子在位置2* i 上，右儿子在 2* i + 1上，父亲在 i/2上
我们可以很容易的定义堆排序的过程：
由输入的无序数组构造一个最大堆，作为初始的无序区 把堆顶元素（最大值）和堆尾元素互换
//下滤 static void PercDown(int data[],int i,int N) { int child; int Tmp; for (Tmp = data[i]; 2 * i + 1 < N;i = child) { child = 2 * i + 1;//leftchild if (child != N - 1 && data[child + 1] > data[child]) child++; if (Tmp < data[child]) data[i] = data[child]; else break; } data[i] = Tmp; } static void HeapSort(int data[], int len) { int i; for (i = len / 2; i >= 0; i--)/*bulid Heap*/ { PercDown(data,i,len); } for (i = len - 1; i > 0;i--)/* deleteMax*/ { swap(data,0,i); PercDown(data,0,i); } }3、冒泡排序
static void BubbleSort(int data[], int len) { if (data == NULL || len == 0) return; for (int i = len-1; i > 0; i--) {//将最大值右移 for (int j = 0; j < i;j++) { if (data[j +1 ] < data[j]) {//交换 int tmp = data[j]; data[j] = data[j + 1]; data[j + 1] = tmp; } } } }