1、冒泡排序
基本思想：若从小到大排序，从头开始，两两比较，大的放在后面，将待排序元素从左到右比较一遍成为“一次冒泡”，每次冒泡都将待排序数列中最大的关键字交换到最后，直到所有元素有序为止。
算法复杂度：O(2^n)
改进方法：可能排序几次后，数列已经有序，但是还没有进行完n次循环。可以在交换的代码段中设置一个标志位，如果该标志位改变说明有交换（还未有序），否则用break退出循环。
//1、冒泡排序//注意数组下标溢出void Bubble(int *array, int n){ int temp = 0; for (int i=0; i array[j]) { temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } } for (int m=0; m //改进冒泡排序：可能在第i次后，已经有序，则在j循环中设置标志//如果该次没有交换,说明已经有序void BubbleAdvanced(int *array, int n){ int temp = 0; int i; bool exchange_flag = true; for (i=0; i array[j]) { temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; exchange_flag = true; } } if (exchange_flag == false) { break; } } for (int m=0; m //修改外层循环，不用n-ivoid Bubble(int *array, int n){ int temp = 0; for (int m = n-1; m >0; --m) { for (int j=0; j array[j]) { temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } } for (int m=0; m
2、快速排序
基本思想：递归
（1）从数列中取出一个数，作为基准数；（基准数一般取：左边第一个元素/中间的元素/最大和最小数的平均值）
（2）分成两部分：将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；
（3）｛左边小｝基准数｛右边大｝，再对左右两边重复第二步，直到各区间只有一个数。
快速排序是一种不稳定的算法，不稳定：在排序过程中，对关键字a排序会改变其他关键字的顺序，不稳定出现在有相同数字时。
如：27(a)，23，27(b)，3
以第一个27(a)为基准值，则27(a)与3交换，变成3，23，27(b)，27(a)
两个27原来的顺序改变了，所以不稳定。
void QuickSort(int array[], int left, int right){ int i = left; int j = right; int midValue = array[(left+right)/2]; int temp; do { //找出左边第一个比基准值大的数 while(i left && array[j]>midValue) { --j; } //上面找出的两个数交换 if (i<=j) { temp = array[i]; array[i] = array[j]; array[j] = temp; ++i; j--; } //交换以后继续上述过程，再交换 }while(i left) { QuickSort(array, left, j); } if (i （在快速排序编程中，出现的问题：与基准值比较是否取“=”，i与j比较是否取“=”，实在搞不清。）
快速排序复杂度：O(n*lgn) （以2为底）
每次调用该函数：需要遍历该数组，复杂度是O(n);
递归调用该函数：调用lgn次（以2为底），所以O(n)*O(lgn)=O(n*lgn) 。
快速排序算法的递推公式：F(n)=2*F(n/2)+n
F(n)=2*F(n/2)+n =2*(2*F(n/4)+n/2)+n =4*F(n/2)+2*n =…… =k*F(1) +lgn*n
快速排序复杂度参考资料：http://book.51cto.com/art/201108/287089.htm
http://zhidao.baidu.com/link?url=
QAD5ZIcnFZ5MkQiFvg03EZMOxkdbU45K99vBHM3s48zmiT3zhfyt2jlUy3WmVcIxSyIXrqtA0S2NuxfVfKfIadfm3RljFXWUQVgtT7QVJMK
快速排序参考资料：http://blog.csdn.net/liuchen1206/article/details/6954074