今天开始了对《啊哈算法》这本书的学习。概括来讲，这本书算是算法界的小白书，语言很通俗，介绍的算法也比较简单，现在回来看简单的东西会不会显得浪费时间呢？不然，笔者最近感觉竞赛并不是终极之道，学习的方向也改为以书为对象(《具体数学》一栏的设立便可以看出)，开始慢慢完善专业知识的体系，并慢慢做一些实用性的东西。
对于排序问题，是算法需要解决的基本问题，而排序也有很多种，其不同的方法也决定了其不同的效率，下面我们来看几种常见的排序方法。
桶排序：
给出一组样例：将5、8、3、1、7从小到大的排序。
桶排序基于一维数组，给出这样排序方法：初始化数组a[10] = 0,然后a[5]++、a[8]++、a[3]++、a[1]++、a[7]++。随后我们控制循环语句，访问a[i],并将i输出a[i]次，最终我们便会得到由小到大的排列。而这个过程，也像其名字所描述的，将数据i扔到了下标为i的数组元素a[i]这个桶里。
桶排序巧妙的把数i当做一维数组的下标，而用a[i]记录i出现的次数，利用下标自小到大的排列顺序完成了对数据的排列。其优点是简易明了，但是缺点也很明显，我们所开的数组长度是受内存空间限制的，因此随着数据的扩大，该排序便显得捉襟见肘了。
下面我们来简单的实现一下这个桶排序。
#include<cstdio> int main() { int a[11] , i , j , t; for(i = 0;i <= 10;i++) a[i] = 0; for(i = 1;i <= 5;i++) { scanf("%d",&t); a[t]++; } for(i = 0;i <= 10;i++) for(j = 1;j <= a[i];j++) printf("%d ",i); return 0; }
冒泡排序：
对于一个需要由小到大排列的序列a[]，我们通过比较相邻的两位a[i]、a[i+1]，如果a[i+1] < a[i]，则将a[i]与a[i+1]交换位置，此时排在序列末尾中又较小的数字就像气泡一样一点点向上冒，但问题在于每次这种交换较小的数字只向上冒了一格，而如果我们遍历了区间上所有相邻的情况，则在这一次遍历中，这个最小的数字将会升到序列的最前面(或者最大的数字沉到序列的最后面，这取决于从序列的头部还是尾部开始)。那么很显然，如果进行n - 1次遍历，我们便可以完成对n个数字的排序。
由上面的算法分析我们不难看出，冒泡排序的时间复杂度是O(n^2)，它虽然避免了桶排序浪费内存的弊端，但是其算法效率显得不是很客观。
简单的代码实现如下。
#include<cstdio> using namespace std; int main() { int a[100] , i , j , t , n; scanf("%d",&n); for(i = 1;i <= n;i++) scanf("%d",&a[i]); for(i = 1;i <= n-1;i++) for(j = 1; j <= n - 1;j++) { if(a[j] < a[j+1]) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } for(i = 1;i <= n;i++) printf("%d ",a[i]); return 0; }
快速排序：
首先我们限定，排序方式是从小到大。
快速排序基于一个精妙的二分思想，使得其排序效率非常快。假设给定一个序列a[1]到a[n]，我们从下标为[1,n]开始，以a[1]为一个参考量，分别从左边和右边扫下标为[1,n]这个区间段，我们设置i记录从左边开始扫的下标，j表示从右边开始扫的下标，一旦发现a[i] > a[1]并且a[j] < a[1]，则交换a[i]和a[j]，直到两边的指针汇集到了一处，即i = j ， 此时将a[i]与a[1]交换，则此时的序列顺序满足第i个元素的左边都是小于a[i]的，第i个元素的右边都是大于a[j]的。但是a[i]左边区间和右边区间的顺序仍然不符合要求，因此我们利用相同的方法，对左区间和右区间进行排序。显然，这不断地将区间一分为二然后分别排序，这呈现出一种类似于dfs回溯的方式，能够遍历到整个大区间的小区间，即完成对所有小区间的排序，也就完成了对整个区间上数字的排序。
基于对快排的简单介绍，我们便可以进行编程实现了。
#include<cstdio> int a[101] , n; void quicksort(int left , int right) { int i , j , t , temp; if(left > right) return; temp = a[left]; i = left; j = right; while(i != j) { while(a[j] >= temp && i < j) j--; while(a[i] <= temp && i < j) i++; if(i < j) { t = a[i]; a[i] = a[j]; a[j] = t; } } a[left] = a[i]; a[i] = temp; quicksort(left , i - 1); quicksort(i + 1, right); } int main() { int i , j , t; scanf("%d",&n); for(i = 1;i <= n;i++) scanf("%d",&a[i]); quicksort(1 , n); for(i = 1;i <= n;i++) printf("%d ",a[i]); return 0; }