[数据结构与算法]对于给定的序列实现直接插入、折半插入、冒泡、希尔、快速、选择、堆排序

1.本代码一共实现7种常见排序，其中直接插入排序和折半插入排序思想相同，只不过在寻找插入位置的时候，折半插入排序采用了二分法，在这一步上较直接插入排序更快。

2.冒泡排序很简单，但是可以进阶一步，在内层循环 j 中加一个flag标识，判断在这一次循环中有没有发生值交换。如果发生了，那么flag的值变化。如果没发生，就直接break循环，节省时间提高效率。

3.希尔排序属于高级排序方法，采用的是缩小增量的思想。在开始正式的排序之前（这个正式的排序可以理解为直接插入排序），先对序列中的一小部分进行排序，这个一小部分数量是由增量deta来控制的，然后一步一步缩小增量，直至增量为1，即演变为直接插入排序。到真正的直接插入排序的时候，前面已经做好了铺垫，根本不需要大费周章就可以完成排序。但值得注意的是：目前还没有选择增量函数的统一的好方法，但是我们要保证的是尽量让所有的增量互质。在进行正式的希尔排序之前，我们需要创建好增量数组，并且得到在增量数组的中元素的个数，这个个数就是我们对序列排序的总次数。

4.快速排序，顾名思义是所有排序方法中平均时间最短的。对它来说，原序列越乱它就越快，如果原序列本身就是有序的，反而不适合快速排序。快速排序的中心思想是首先任取一个元素为中心点pivot，假如就是第一个元素，然后以这个元素为中心，小于它的放左边，大于它的放右边，从而形成左右两个子表。然后利用递归的思想，再对左右两个子表进行快速排序，相同的流程。关键点是如何找到我选择的这个中心点的所在位置？这里采用的是挖坑法，具体看代码

5.选择排序很简单，不再赘述。

6.堆排序首先要理解小根堆和大根堆的含义，并且掌握如何把一个无序序列构建成小根堆（大根堆），然后怎么在排序的过程中调整堆。

7个排序代码都放在一起了

上代码：

#include <iostream>
#include <algorithm>
using namespace std;

#define OK 1
#define ERROR 0
#define Status int

typedef struct {
	int* data; //存储主要信息的数组
	int length; //顺序表长度
	int listSize; //空间大小
}SqList;

//初始化顺序表
Status InitSqList(SqList& L) {
	L.data = (int *) malloc(100 * sizeof(int));
	L.length = 0;
	L.listSize = 100;
	return OK;
}

//输入值到顺序表中
void CreatSqList(SqList& L) {
	cout << "请输入序列：(以-1为结束数字)" << endl;
	int i, index = 1; //0号位置作为哨兵
	cin >> i;
	while (i != -1) {
		if (i != -1) {
			L.data[index] = i;
			index++;
			L.length++;
			cin >> i;
		}
		else
			break;
	}
}

//打印顺序表
void PrintSqList(SqList L) {
	cout << "顺序表为：" << endl;
	for (int i = 1; i <= L.length; i++) {
		cout << L.data[i] << " ";
	}
	cout << endl;
}

//直接插入排序
void DirectInsertSort(SqList& L) {
	int j;
	for (int i = 2; i <= L.length; i++) {  //i从2开始 因为0作哨兵 1是起始元素 所以从2开始比较
		if (L.data[i] < L.data[i - 1]) { //当i处的值小于i-1时才比较  否则根本不需要进行比较 这样节省了时间
			L.data[0] = L.data[i]; //把要比较的第i个元素值给哨兵
			for (j = i - 1; L.data[0] < L.data[j]; j--) {
				L.data[j + 1] = L.data[j]; //元素后移
			}
			L.data[j + 1] = L.data[0];//插入到正确位置j+1上
		}
	}
}

//折半查找排序
void HalfInsertSort(SqList& L) {
	for (int i = 2; i <= L.length; i++) { //依次插入2~n个元素 除了第一个
		int low = 1, high = i - 1;
		L.data[0] = L.data[i]; //哨兵
		while (low <= high) {
			int mid = (low + high) / 2;
			if (L.data[i] < L.data[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}//while结束后 high + 1或者low是插入位置 画图分析即可
		for (int j = i - 1; j >= high + 1; j--) { //移动元素到low
			L.data[j + 1] = L.data[j];
		}
		L.data[high + 1] = L.data[0];
	}//for
}

//进阶版冒泡排序
void BubbleSort(SqList& L) {
	int tmp; //辅助变量
	for (int i = 1; i < L.length; i++) { //注意 顺序表创建时 第一个位置没有用 所以从1开始
		int flag = 0;
		for (int j = 1; j < L.length - i + 1; j++) {
			if (L.data[j] > L.data[j + 1]) {
				tmp = L.data[j];
				L.data[j] = L.data[j + 1];
				L.data[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}

//希尔排序
void ShellInsert(SqList& L, int Increment) {
	int j;
	for (int i = Increment + 1; i <= L.length; i++) { // 一种增量对应的比较次数
		if (L.data[i] < L.data[i - Increment]) { //当这种情况下才排序
			L.data[0] = L.data[i];
			for (j = i - Increment; j > 0 && (L.data[0] < L.data[j]); j = j - Increment) {
				L.data[j + Increment] = L.data[j]; //元素后移
			}
			L.data[j + Increment] = L.data[0];
		}
	}
}

void ShellSort(SqList& L) {
	int Increment[10]; //增量序列
	int cnt = 0; //计算有几个增量 用于增量序列数组的元素个数
	int i = L.length;
	while (i > 1) {
		i = i / 3 + 1; //计算增量 采用除3加1的方式 尽量让增量序列互质
		Increment[cnt] = i; //给增量数组赋值
		cnt++;
	}
	cout << "增量序列为：";
	for (int j = 0; j < cnt; j++) cout << Increment[j] << " ";
	cout << endl;
	for (int j = 0; j < cnt; j++) {
		ShellInsert(L, Increment[j]);
	}
}

//快速排序 (挖坑法)
int Partition(SqList& L,int low, int high) {//找到中心点的位置给主程序QuickSort
	int pivotValue = L.data[low]; //取出low位置的值为中心点值 可以想象为low处的值被挖空了
	while (low < high) {
		while (low < high && L.data[high] > pivotValue) high--;
		//当循环跳出时 说明high处的值小于pivotValue了 所以放在左边挖空的地方 即low处
		L.data[low] = L.data[high];
		while (low < high && L.data[low] < pivotValue) low++;
		//当循环跳出时 说明low处的值大于pivotValue了 所以放在右边被挖空的地方
		L.data[high] = L.data[low];
	}
	//当整个循环结束时 low == high 这个位置就是我们要找的放置中心点的位置 我们先给这个地方填上值
	L.data[low] = pivotValue; //low 或者 high 都可以
	return low;
}

void QuickSort(SqList& L, int low, int high) { //快速排序的递归主体
	if (low < high) {
		int pivot = Partition(L, low, high);
		QuickSort(L, low, pivot - 1); // 对左子表进行递归的快速排序
		QuickSort(L, pivot + 1, high); // 对右子表进行递归的快速排序
	}
}

//简单选择排序
void SelectSort(SqList& L) {
	for (int i = 1; i < L.length; i++) {
		int k = i; //辅助变量 用于记录最小值的位置
		for (int j = i + 1; j <= L.length; j++) {
			if (L.data[j] < L.data[i]) k = j; //记录最小值的下标
		}
		if (k != i) {
			int t;
			t = L.data[k];
			L.data[k] = L.data[i];
			L.data[i] = t;
		}
	}
}

//堆调整
void HeapAdjust(SqList& L, int front, int last) {
	/*
	* 已知R[front...last]中记录的关键字除了R[front]之外均满足堆的定义，本函数作用是调整R[front]关键字
	* 使得R[front...last]成为一个小根堆
	*/
	int cur = L.data[front]; //cur表示需要调整位置的结点
	for (int i = 2 * front; i <= last; i *= 2) { //i从根节点的左孩子开始 到右孩子
		if (i < last && L.data[i] > L.data[i + 1]) i++; //找到较小的那个
		if (cur <= L.data[i]) break; //如果当前需要调整的小于较小的，直接break跳出循环，当前位置就是正确的
		//如果当前的更大 就往下交换
		L.data[front] = L.data[i]; front = i; //把当前需要调整的结点移动到i位置处
	}
	L.data[front] = cur;
}

//堆排序
void HeapSort(SqList& L) {
	for (int i = L.length / 2; i >= 1; i--) {
		HeapAdjust(L, i, L.length); //从无序序列建立初始的小根堆
	}
	for (int i = L.length; i > 1; i--) {
		swap(L.data[1], L.data[i]); //根与最后一个元素交换
		//然后进行堆调整
		HeapAdjust(L, 1, i - 1);
	}
	//进行完堆调整后 由于没有删除每一步最小的结点 所有它们都被存在了数组中
	for (int i = L.length; i >= 1; i--)
		cout << L.data[i] << " ";
	cout << endl;
}

int main() {
	SqList L;

	InitSqList(L);
	CreatSqList(L);
	PrintSqList(L);
	cout << endl;

	int choice;
	while (1) {
		cout << "0.退出程序" << "\n1.进行直接插入排序" << "\n2.进行折半插入排序" << "\n3.进行冒泡排序" << "\n4.进行希尔排序"  << "\n5.进行快速排序" << "\n6.进行选择排序" << "\n7.进行堆排序" << endl;
		cout << "请输入选择：";
		cin >> choice;
		switch (choice) {
		case 0:
			cout << "已退出程序！";
			exit(0);
		case 1:
			DirectInsertSort(L);
			PrintSqList(L);
			break;
		case 2:
			HalfInsertSort(L);
			PrintSqList(L);
			break;
		case 3:
			BubbleSort(L);
			PrintSqList(L);
			break;
		case 4:
			ShellSort(L);
			PrintSqList(L);
			break;
		case 5:
			QuickSort(L, 1, L.length);
			PrintSqList(L);
			break;
		case 6:
			SelectSort(L);
			PrintSqList(L);
			break;
		case 7:
			HeapSort(L);
			break;
		default:
			break;
		}
	}

}