排序算法

#include <stdio.h>
#include <stdlib.h>
// 记录最大数为20
#define MAXSIZE 20

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 设置关键字为整型
typedef int KeyType;
// 设置其他数据项
typedef char InfoType;

// 定义每个记录的结构
typedef struct {
	// 关键字
	KeyType key;
	// 其他数据项
	InfoType otherinfo;
}RedType;

// 定义顺序表的结构
typedef struct {
	// 定义存储数据表的向量，r[0]位置用来设置缓冲区或者哨兵
	RedType r[MAXSIZE + 1];
	// 顺序表的长度
	int length;
}SqList;

// 直接插入排序
void InsertSort(SqList& L) {
	int i, j = 0;
	for (i = 2; i < L.length; i++) {
		// 若<,则要将L.r[i].key插入到有序子表中
		if (L.r[i].key < L.r[i - 1].key) {
			// 设置哨兵
			L.r[0] = L.r[i];
			// 查找插入位置，并将大于哨兵的数依次向后移动
			for (j = i - 1; L.r[j].key > L.r[0].key; j--) {
				L.r[j + 1] = L.r[j];
			}
			// 插入正确位置
			L.r[j + 1] = L.r[0];
		}
	}
}

// 折半插入排序
void BInsertSort(SqList& L) {
	int i, j = 0;
	// 依次插入第2~第n个元素
	for (i = 2; i < L.length; i++) {
		// 将当前元素存入“哨兵”位置
		L.r[0]= L.r[i];
		// 设置折半的顶部下标和底部下标
		int low = 1, high = i - 1;
		// 采用二分查找法查找插入位置
		while (high >= low) {
			int mid = (high + low) / 2;
			if (L.r[mid].key > L.r[0].key) high = mid - 1;
			else low = mid + 1;
		}// 循环结束，high + 1为插入位置
		// 将high + 1位置后的元素后移
		for (j = i - 1; j >= high + 1; j--) {
			L.r[j + 1] = L.r[j];
		}
		// 将元素插入到high + 1位置
		L.r[high + 1] = L.r[0];
	}
}

// 希尔排序
void ShellSort(SqList& L, int dlta[], int t) {
	// 按增量序列dlta[0....t-1]对顺序表进行希尔排序
	for (int k = 0; k < t; k++) {
		ShellInsert(L, dlta[k]);
	}
}

// 从i = dk+1（i依次加一）位置开始，和i - dk位置比较大小，直到i = L.length
void ShellInsert(SqList& L, int dk) {
	// 对顺序表L进行一趟增量为dk的shell排序，dk为步长因子
	for (int i = dk + 1; i < L.length; i++) {
		// 顺序表中相隔dk的前一个元素>后一个元素时，交换两个元素
		if (L.r[i - dk].key > L.r[i].key) {
			// 将下标为i的数据存到下标为0的位置
			L.r[0] = L.r[i];
			// 将前一个元素存储到后一个元素
			L.r[i] = L.r[i - dk];
			// 将暂存的元素存储到前一个元素位置
			L.r[i - dk] = L.r[0];
		}
	}
}

// 冒泡排序
void bubble_sort(SqList& L) {
	// flag作为是否有交换的标记
	int i, j, flag = 1, n = L.length;
	// 定义临时变量
	RedType x;
	// 总共有n - 1趟
	for (i = 1; i < n && flag == 1; i++) {
		flag = 0;
		// 每一趟比较n - i次
		for (j = 1; j < n - i; j++) {
			// 发生逆序，交换数据
			if (L.r[j].key > L.r[j + 1].key) {
				// 发生交换，flag置为1，未发生交换，flag保持0
				flag = 1;
				x = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = x;
			}
		}
	}
}

// 快速排序
void Qsort(SqList& L, int low, int high) {
	// （子）表的长度大于1
	if (low < high) {
		// pivotloc是枢纽元素排好序的位置
		int pivotloc = Partition(L, low, high);
		// 通过pivotloc将表L.r[low...high]一分为二
		// 对枢纽元素之前的子表进行排序
		Qsort(L, low, pivotloc - 1);
		// 对枢纽元素之后的子表进行排序
		Qsort(L, pivotloc + 1, high);
	}
}

int Partition(SqList& L, int low, int high) {
	// 将表中第一个元素作为枢纽元素
	L.r[0] = L.r[low];
	KeyType pivotkey = L.r[low].key;
	// 循环执行
	while (low < high) {
		// 如果high上的值大于或者等于枢纽元素，high--
		while (low < high && L.r[high].key >= pivotkey) high--;
		// 小于，则将值赋值给low
		L.r[low] = L.r[high];
		// 如果high上的值小于枢纽元素，low++
		while (low < high && L.r[low].key < pivotkey) low++;
		// 大于或者等于，则将值赋值给high
		L.r[high] = L.r[low];
	}
	// 将枢纽元素赋值给pivotloc位置
	L.r[low] = L.r[0];
	// 将枢纽位置返回
	return low;
}

// 简单排序算法
void SelectSort(SqList& L) {
	RedType t;
	// 从首元素开始循环
	for (int i = 1; i < L.length; i++) {
		// 令最小值下标为循环开始下标
		int k = i;
		// 从循环开始的下一个下标开始，和循环开始下标进行对比，找到最小值的下标
		for (int j = i + 1; j < L.length; j++) {
			if (L.r[j].key < L.r[k].key) k = j;
		}
		// 如果循环开始的元素不是最小值，则交换
		if (k != i) {
			t = L.r[k];
			L.r[k] = L.r[i];
			L.r[i] = t;
		}
	}
}

int main() {
	SqList L;
	Qsort(L, 1, L.length);
}