各种排序算法综合

都是算法程序

复习排序算法2007-06-22 01:06以练习为目的将数据结构书上排序算法写了一遍。
包括：
1.1. 直接插入排序
1.2. 折半插入排序
1.3. 2-路插入排序
1.4. SHELL排序
1.5. 表插入排序

2.1. 起泡排序
2.2. 快速排序

3.1. 简单选择排序
3.2. 树形选择排序
3.3. 堆排序

4.1. 基数排序
--------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM 8
/***BEGIN**1.5.表插入用数据结构*************/
#define TABLESIZE 20
typedef struct
{
int rc;//记录项
int next;//指针项
} SLNode;
typedef struct
{
SLNode r[TABLESIZE];
int length;//链表当前长度
} SLinkListType;//静态链表类型
/***END****1.5.表插入用数据结构*************/

/***BEGIN**3.2.树形选择排序用数据结构*******/
#define MAX 0xfffFFFF
typedef struct
{
int rc;//记录项
int child;//指示继承了哪个孩子的值
} TreeNode;
/***END****3.2.树形选择排序用数据结构*******/

/******1.插入排序*************/
//1.1. 直接插入排序
void InsertSortSimple(int *a, int len);
//1.2. 折半插入排序
void InsertSortB(int *a, int len);
//1.3. 2-路插入排序
void InsertSort2path(int *a, int len);
//1.4. SHELL排序
void InsertSortShell(int *a, int len);
//以增量d进行一遍shell
void ShellOnce(int *a, int d, int len);
//1.5. 表插入排序
void InsertSortSTbl(int *a, int len);

/******2.交换排序*************/
//2.1. 起泡排序
void BubbleSort(int *a, int len);
//2.2. 快速排序
void QuickSort(int *a, int len);
void QSort(int *a, int low, int high);
int Partition(int *a, int low, int high);

/******3.选择排序*************/
//3.1. 简单选择排序
void SimpleSelectSort(int *a, int len);
//3.2. 树形选择排序
void TreeSelectSort(int *a, int len);
//3.3. 堆排序
void HeapSort(int *a, int len);
//完全二叉树中，除a[s]外，a[s+1..len]符合堆定义
//调整树，使得a[s..len]符合堆定义。
void HeapAdjust(int *a, int s, int len);

/******4.归并排序*************/
//4.1. 归并排序
void MergeSort(int *a, int len);
void MSort(int *a, int s, int n);
void Merge(int *a, int i, int m, int n);

int main(int argc, char *argv[])
{
int a[NUM] = { 49, 38, 65, 97, 76, 13, 27, 49};
int len = NUM, i;
//InsertSortSimple(a, len);
//InsertSortB(a, len);
//InsertSort2path(a, len);
//InsertSortShell(a, len);
//InsertSortSTbl(a, len);

//BubbleSort(a, len);
//QuickSort(a, len);

//SimpleSelectSort(a, len);
//TreeSelectSort(a, len);
//HeapSort(a, len);

MergeSort(a, len);
for(i = 0; i < NUM; i++)
printf("%d ", a[i]);
return 0;
}


/***********
********函数实现************************/
//1.1.直接插入排序
void InsertSortSimple(int *a, int len)
{
int i, j, tmp;
for(i = 1; i < len; i++)
{