数据结构C语言--三种以上的排序算法

快速排序：
void QSort(int a[], int l, int r) //单关键字交换法快排
{
int i = l, j = r, mid = (i + j) / 2; //二分[i,j]区间

while (i <= j) //让a[mid]左边都比a[mid]小，右边都比a[mid]大
{
while (a[i] < a[mid]) //找到一个元素a[i]比a[mid]小
i++;
while (a[j] > a[mid]) //找到一个元素a[j]比a[mid]大
j--;
if (i <= j) //交换a[i]和a[j]，并让指针向中间靠拢
Swap(a[i++], a[j--]);
}

if (i < r)
QSort(a, i, r); //对右区间[i,r]递归排序
if (l < j)
QSort(a, l, j); //对左区间[l,j]递归排序
}

归并排序：
void Merge(int a[], int l, int m, int r) //将a中区间[l, r]合并为有序
{
int x[101], y[101]; //循环变量
int i, j, k;
int l1 = m - l + 1, l2 = r - m; //l1表示区间[l, m]的长度，l2表示区间[m + 1, r]的长度

for (i = 1; i <= l1; i++) //将a中区间[l, m]复制到x中
{
x[i] = a[l + i - 1];
}

for (i = 1; i <= l2; i++) //将a中区间[m + 1, r]复制到y中
{
y[i] = a[m + i];
}

x[l1 + 1] = MaxInt; //设置一个很大的数作为结束标志
y[l2 + 1] = MaxInt;
i = 1;
j = 1;

for (k = l; k <= r; k++) //将两个区间合并成为一个有序区间
{
if (x[i] <= y[j])
{
a[k] = x[i++];
}
else
{
a[k] = y[j++];
}
}
}

void MergeSort(int a[], int l, int r) //对a数组的[l, r]区间排序
{
int m;

if (l < r)
{
m = (l + r) / 2; //二分区间[l, r]

MergeSort(a, l, m); //递归二分区间[l, m]
MergeSort(a, m + 1, r); //递归二分区间[m + 1, r]

Merge(a, l, m, r); //合并区间[l, m]和[m + 1, r]
}
}

二叉排序树排序：
struct BinaryTree //二叉树结构
{
int data, p, l, r; //data数值域，p父节点编号，l左儿子编号，r右儿子编号
};

int root = 0;

void Init(BinaryTree a[], int &n) //读入数据域，并初始化树
{
cin >> n;

for (int i = 1; i <= n; i++)
{
cin >> a[i].data;
a[i].p = a[i].l = a[i].r = -1;
}
}

void Insert(BinaryTree a[], int i) //在二叉查找树中插入编号为 i 的节点
{
int parent = -1, x = a[1].p; //parent 始终指向 x 的父节点编号

while (x != -1) //向下搜索，直到找到最下一层
{
parent = x;
if (a[i].data < a[x].data)
x = a[x].l;
else
x = a[x].r;
}

a[i].p = parent; //把第 i 号节点的父亲指向parent
if (parent != -1) //判断树是否为空
{
if (a[i].data < a[parent].data) //向父节点插入儿子
a[parent].l = i;
else
a[parent].r = i;
}
else //为空就以 i 节点为根节点
a[root].p = i;
}

void BuildTree(BinaryTree a[], int n) //建立二叉查找树
{
root = 1;
for (int i = 1; i <= n; i++) //依次插入 n 个节点到二叉查找树
{
Insert(a, i);
}
a[root].p = -1;
}

void Sort(BinaryTree a[], int i) //中序遍历输出
{
if (a[i].l > -1) //递归遍历左儿子
Sort(a, a[i].l);
cout << a[i].data << " "; //输出节点
if (a[i].r > -1) //递归遍历右儿子
Sort(a, a[i].r);
}

堆排序：
void Heap(int a[], int n, int p) //维护最大（最小）堆，维护以P为根的堆
{
int l = p * 2, r = l + 1, t = p; //左儿子编号为2P，右儿子为2P+1，初始化根节点P为最大

if ((l <= n) && (a[l] > a[p])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = l;
if ((r <= n) && (a[r] > a[t])) //找一个最大的数，维护最大堆（改为<就是维护最小堆）
t = r;
if (p != t) //如果根节点不是最大，和最大的交换，再递归维护堆
{
Swap(a[p], a[t]);
Heap(a, n, t);
}
}

void HeapSort(int a[], int n)
{
int i;

for (i = n / 2; i >= 1; i--) //n / 2开始必然是根节点，依次调用Heap，建立一个最大堆
Heap(a, n, i);

for (i = n; i >= 2; i--) //每次将堆顶和当前堆最后一个节点(i)交换，然后将[1, i - 1]重新堆化
{
Swap(a[i], a[1]);
Heap(a, i - 1, 1);
}
}

插入排序：
void InsertionSort(int a[], int l, int r) //对区间[l, r]执行插入排序
{
int i, j, t;

for (i = l + 1; i <= r; i++)
{
j = i - 1;
t = a[i];

while ((j >= l) && (a[j] > t)) //后移操作，并找到正确的位置
{
a[j + 1] = a[j];
j--;
}

a[j + 1] = t;
}
}

以上所有的Swap函数的意思都是交换两个变量。

百度百科上有。
排序：http://baike.baidu.com/view/58783.htm?fr=ala0_1
快排：http://baike.baidu.com/view/115472.htm

... ...