其实现在很多算法都是别人写好的，我们只要拿来用就行了。下面的算法部分是摘自clifford写的那本数据结构与算法分析。其中自然归并排序、快速排序、桶排序是自己写的。
template
void bubSort(Elem A[], int n)
{
for(int i =0; i for(j = n-1; j > i; j--) //bubble up i'th element
if(A[j] < A[j-1])
swap(A[j],A[j-1]);
}
（3）选择排序
算法思想：循环n-1次(每次从n-1到i，找到最小的元素的下标lowindex),交换A[i]与A[lowindex].
template
void selSort(Elem A[], int n)
{
for(int i = 0; i < n-1; i++)
{
int lowindex = i;
for(int j = n - 1; j > i; j--)
if(A[j] < A[lowindex])
lowindex = j;
swap(A[j],A[lowindex]);
}
}
2.归并排序（nlogn）
（1）一般版本（自顶向下）
算法思想：
先谈谈我个人对递归的理解，如有不妥，望指正。
递归问题一般都要假设子问题已经解决，找出这个假设下问题的解，然后将这种策略用于子问题，最终就会到达子问题的最基本的情况（这种情况很容易解决），问题解决。
现在来讲归并排序：
假设数组A被分为各自有序的两部分，(A[left]~~A[mid])和(A[mid+1]~~A[right])
我们现在的任务就是把这两个各自有序的数组合并为一个整体有序的数组。
因为A要保存最终结果，所以我们需要一个临时数组来保存A的初始值，然后每次比较左边数组最小的元素与右边数组最小的元素，取小者放到A中。不多说了，直接看代码可能更好理解。我的表达能力just so so!
template
void mergeSort(Elem A[],Elem temp[],int left, int right)
{
if(left == right)
return;
int mid = (left+right)/2;
mergeSort(A,temp,left,mid);
mergeSort(A,temp,mid+1,right);
for(int i = left;i<=right;i++)//保存A
temp[i] = A[i];
int i1= left; //左边数组的未取走的元素位置
int i2 = mid+1; //右边数组的未取走的元素位置
for(int curr = left; curr <= right; curr++)
{
if(i1==mid+1) //左边耗尽，依次取右边的即可
A[curr] = temp[i2++];
else if(i2 > right) //右边耗尽
A[curr] = temp[i1++];
else if(temp[i1] < temp[i2])
A[curr] = temp[i1++];
else
A[curr] = temp[i2++];
}
}
（2）R.Sedgewick改进的版本
这个版本和上面的完全一样，只是考虑到归并元素很少的数组效率并不可观，所以当元素个数小于某个值（THRESHOLD）时就采用插入排序。
其次，这个算法的下标安排很精巧。
template
void mergeSort2(Elem A[],Elem temp[],int left, int right)
{
if((right - left) < THRESHOLD)
{
insSort(&A[left],right-left+1);
return;
}
if(left == right)
return;
int mid = (left+right)/2;
mergeSort2(A,temp,left,mid);
mergeSort2(A,temp,mid+1,right);
int i,j;
for(i = left; i <= mid; i++)
temp[i] = A[i];
for(j = 1; j <= right -mid;j++)
temp[right - j +1] = A[j + mid];
for(int k = left,i = left,j = right; k <= right; k++)
if(temp[i] < temp[j])
A[k] = temp[i++];
else
A[k] = temp[j--];
}
（3）我写的自然归并排序
算法思想：一般来说，原数组是由很多原来就有序的部分组成，我们为什么不能把原数组划分成这些有序的段然后在归并它们呢？
比如 4 5 1 6 7 3 9
可以化为 4 5
1 6 7
3 9
用下标表示它们就是
0~1
2~4
5~6
观察一下下标1，4 刚好是出现逆序时的下标，即A[j] < A[j+1]时的 j
。
如此说来我们只需把这些逆序下标找出来(保存在R[]数组中)，然后这样对原数组划分
left ~ R[0], (R[0] + 1) ~ R[1] ... (R[k]+1) ~ R[k+1], R[k+1] + 1 ~ right
代码：
template//找出逆序下标放到reverse中，返回逆序下标个数
int getReverse(Elem A[],int left,int right,int *reverse)
{
int n = 0;
for(int i = left;i < right;i++)
if(A[i] > A[i+1]) //逆序
reverse[n++] = i;
return n;
}
template//归并两个各自有序的数组
void merge(Elem A[],Elem *temp,int left,int mid,int right)
{
int i,j,k;
for(i = left; i <= mid; i++)
temp[i] = A[i];
for(j = 1; j <= right -mid;j++)
temp[right - j +1] = A[j + mid];
for(k = left,i = left,j = right; k <= right; k++)
if(temp[i] < temp[j])
A[k] = temp[i++];
else
A[k] = temp[j--];
}
template
void nMergeSort(Elem A[],int left, int right)
{
if(left >= right) return;
int size = right - left + 1;
int *reverse = new int[size]; //如果数组刚好完全逆序，则会有size - 2 个逆序下标
int k = getReverse(A,left,right,reverse);
if(k==0) //已经有序
return;
reverse[k] = right; //看下面的循环就懂了
Elem *temp = new Elem[size];
for(int i = 0; i <= k; i++)
merge(A,temp,left,reverse[i],reverse[i+1]);
delete [] reverse;
delete [] temp;
}
（4）我写的自底向上的归并排序
算法思想：
这个算法也可以说是归并排序的迭代版本。
首先，将原数组看成有n个子数组组成的，每个子数组的元素个数都是1，当然每个子数组是有序的。
然后将每两个上面的子数组进行归并，如果n是奇数则最后会剩下一个子数组，我们先不处理它，等把其他的数组归并为一个n-1的数组时再来归并它。现在我们就会得到n/2个含有两个元素的有序子数组。
接着将上面的n/2个子数组两两归并，如果n/2是基数，则我们会得到 n/4个有序的子数组和一个含两个元素的子数组。对待它的方法同上。
当子数组的大小等于n时结束算法。
3.快速排序
算法思想：
从数组中找一个元素item（我选的是A[0],其实应该随机选取，但取随机数的代价太高！）
从right开始，如果有比item小的元素则交换两者，right++；
再从left开始，如果有比item大的元素则交换两者，letf++；
直到left >= right，说明现在item左边的元素都比他小，右边的都比他大，即item的最终位置已确定。
然后将原数组从item处断成两部分，对每部分重复上面的过程，直到这样的部分中只有一个元素，即（left==right）.
template
int partition(Elem A[],int left, int right) //right一定大于left
{
Elem temp = A[left];
do{
while((right > left)&&(A[--right] > temp));
if(left < right)
swap(A[right], A[left]);
while((left < right)&&(A[++left] < temp));
if(left < right)
swap(A[right], A[left]);
}
while(left < right);
return left;
}
template
void qSort(Elem A[],int left,int right)
{
if(left >= right)
return;
if(A[left] > A[right]) //让A[left]和A[right-1]以前的元素比较
swap(A[right], A[left]);
int k = partition(A,left,right);
qSort(A,left,k-1);
qSort(A,k+1,right);
}
4.堆排序
堆排序主要是依靠大顶堆这种数据结构的特性，root总是大于children。具体实现看代码更容易理解。
首先要实现一个大顶堆的数据结构(不要被吓到了，多是有点，其实很简单)
//该大顶堆是基于数组的
heap.h
#ifndef HEAP_H
#define HEAP_H
#include"util.h"
template
class MaxHeap
{
private:
Elem *heap; //数组指针
int size; //最大容量，即数组大小
int n; //当前堆中的元素个数
void siftDown(int);//将某个下标的元素放到对的合适位置
public:
MaxHeap(Elem *h,int num,int max)
{
heap = h;
size = max;
n = num;
buidHeap();
}
int heapSize() const
{ return n; }
bool isLeaf(int pos) const
{ return (pos >= n/2) && (pos < n); }
int leftChild(int pos) const
{ return 2*pos + 1; }
int rightChild(int pos) const
{ return 2*pos + 2; }
int parent(int pos) const
{ return (pos - 1)/2; }
bool insert(const Elem&);
bool removeMax(Elem&);
bool remove(int,Elem&);
void buidHeap()
{
for(int i = n/2 - 1;i >=0; i--)//一个大小为n的数组只需将他的n/2个元素放到堆中合适的
//位置则其他的元素自然就放好了
siftDown(i);
}
};
template
void MaxHeap::siftDown(int pos)
{
while (!isLeaf(pos))
{
int lc = leftChild(pos);
int rc = rightChild(pos);
if ((rc < n) && (heap[lc] < heap[rc]))
lc = rc; //取左和右孩子中的大者下标
if (!(heap[pos] < heap[lc]))
return;
swap(heap[pos],heap[lc]);
pos = lc;
}
}
template
bool MaxHeap::insert(const Elem &it)
{
if(n>=size)
return false;
int curr = n++;
heap[curr] = it;
while((curr!=0)&&(heap[curr] > heap[parent(curr)]))
{
swap(heap[curr],heap[parent(curr)]);
curr = parent(curr);
}
return true;
}
template
bool MaxHeap::remove(int i,Elem& it)
{
if(i < 0 || i >= n)
return false;
swap(heap[i],heap[--n]);
while((i !=0)&&(heap[i] > heap[parent(i)]))
{
swap(heap[i],heap[parent(i)]);
i = parent(i);
}
siftDown(i);
it = heap[n];
return true;
}
template
bool MaxHeap::removeMax(Elem &it)
{
if(n==0) return false;
swap(heap[0],heap[--n]);
if(n!=0)
siftDown(0);
it = heap[n];
return true;
}
#endif
堆排序代码：
template
void heapSort(Elem A[],int n)
{
Elem mval;
MaxHeap H(A,n,n);
for(int i = 0; i < n; i++)
H.removeMax(mval);
}
堆排序在你只需要找出前k个最小的数时时间复杂度仅为n + klogn.这是他比前面的算法更优秀的地方。
5.桶排序
明天继续！！
