数据结构-排序 2021/8/12 23:02

#include <iostream>
using namespace std;
/*
算法的稳定性：排序后，相同关键字的元素相对位置和排序前一致，则为稳定
内部排序：数据都在内存中
外部排序：数据太多，无法全部放入内存

*/

/*
插入排序：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
优化：用折半查找找到应该插入的位置，再移动元素
整体来看时间复杂度仍然是O(n^2)
*/
void InsertSort(int A[], int n)//插入排序
{
	int i, j, temp;
	for (i = 1; i < n; i++)
	{
		if (A[i] < A[i - 1])
		{
			temp = A[i];
			for (j = i ; j >= 0&&A[j]>=temp; j--)
			{
				A[j] = A[j - 1];
			}
			A[j + 1] = temp;
		}
	}
}
void InsertSort2(int A[], int n)//折半插入排序
{
	int i, j, low, high, mid;
	for (i = 1; i <= n; i++)
	{
		if (A[i] < A[i - 1])
		{
			A[0] = A[i];
			low = 1; high = i - 1;
			while (low <= high)
			{
				mid = (low + high) / 2;
				if (A[mid] > A[0]) high = mid - 1;
				else low = mid + 1;
			}
			for (j = i-1; j >= high+1; j--)
			{
				A[j + 1] = A[j];
			}
			A[high + 1] = A[0];
		}
	}
}
/********************************************************************/
/*
希尔排序：先追求部分有序，再追求全局有序
最坏时间复杂度：O(n^2) 当n在某个范围时，可达O(n^1.3)
仅适用于顺序表，不适用于链表
*/
void ShellSort(int A[], int n)
{
	int d, i, j;
	for (d = n / 2; d >= 1; d = d / 2)//设置步长
	{
		for (i = d + 1; i <= n; i++)
		{
			if (A[i] < A[i - d])
			{
				A[0] = A[i];
				for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
				{
					A[j + d] = A[j];
				}
				A[j + d] = A[0];

			}
		}
	}
}
/*****************************************************************************/
/*
冒泡排序：交换排序的一种
每一趟都能确定一位当前的最小值（最大值）
冒泡排序适用于链表
时间复杂度(O(n^2))稳定
*/
void BubbleSort(int A[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		bool flag = false;
		for (int j = n - 1; j > i; j--)
		{
			if (A[j - 1] > A[j])
			{
				swap(A[j - 1], A[j]);
				flag = true;
			}
		}
		if (flag == false)
			return;
	}
}
/*******************************************************************/
/*
快速排序
最好时间复杂度O(nlogn)最坏时间复杂度O(n^2)平均时间复杂度O(nlogn)
不稳定
408原题中，一次划分确定一个元素的最终位置，一趟排序确定多个元素位置
*/
int Partition(int A[], int low, int high) {
	int pivot = A[low];//取第一个元素作为基准
	while (low < high)
	{
		while (low < high && A[high] >= pivot) --high;
		A[low] = A[high];
		while (low < high && A[low] <= pivot) ++low;
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}
void QuickSort(int A[], int low, int high)
{
	if (low < high) {
		int pivotpos = Partition(A, low, high);
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1,high);
	}
}
/*****************************************************************/
/*
简单选择排序：选择排序的一种
每一趟找到最小的，将它前移
时间复杂度：O(n^2)不稳定
既可以用于顺序表，也可以用于链表
*/
void SelectSort(int A[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
			if (A[j] < A[min]) min = j;
		if (min != i) swap(A[i], A[min]);
	}
}

/*********************************************************************************/
/*
堆排序
建立大根堆：把左右非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整
1)检查当前结点是否满足根>=左、右，若不满足，则将当前结点与更大的一个孩子互换）
2)若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断下坠）
时间复杂度：O(nlogn)
不稳定

堆中插入新元素：不断和父元素进行对比，进行上升
堆中删除元素：非终端结点的删除：用最底层终端结点代替当前需删除结点然后进行下坠操作
*/
void HeadAdjust(int A[], int k, int len)//将以k为根的子树调整为大根堆
{
	A[0] = A[k];
	for (int i = k * 2; i <= len; i = i * 2)
	{
		if (i < len && A[i] < A[i + 1])
			i++;
		if (A[0] >= A[i]) break;
		else {
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = A[0];
}
void BuildMaxHeap(int A[], int len)//建立大根堆
{
	for (int i = len / 2; i > 0; i--)
		HeadAdjust(A, i, len);
}

void HeapSort(int A[], int len)//堆排序
{
	BuildMaxHeap(A, len);
	for (int i = len; i > 1; i--)
	{
		swap(A[i], A[1]);
		HeadAdjust(A, 1, i - 1);
	}
}
/**************************************************************************/
/*
归并排序：将两个或多个有序的序列合并成一个

时间复杂度为O(nlogn),稳定
*/
int* B = (int*)malloc(100 * sizeof(int));//辅助数组B
//A[low...mid]和A[mid+1,...high]各自有序，将两个部分归并
void Merge(int A[], int low, int mid ,int high)
{
	int i, j, k;
	for (k = low; k <= high; k++)
		B[k] = A[k];//将A中所有元素复制到B中
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
	{
		if (B[i] <= B[j])//将较小值复制到A中
			A[k] = B[i++];
		else
			A[k] = B[j++];
	}
	while (i <= mid) A[k++] = B[i++];
	while (j <= high) A[k++] = B[j++];

}
void MergeSort(int A[], int low, int high)
{
	if (low < high) {
		int mid = (low + high) / 2;
		MergeSort(A, low, mid);
		MergeSort(A, mid + 1, high);
		Merge(A, low, mid, high);
	}
}
/********************************************************************/
/*
基数排序：基数排序不是基于比较的算法
基数排序通常基于链式储存实现
基数排序得到递减序列的过程如下：
初始化：设置r个空队列，Qr-1，Qr-2...Q0
按照各个关键字 权重递增的次序（个十百），对d个关键字位分别做“分配”和“收集”
分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Qx队尾
收集：把Qr-1，Qr-2......Q0各个队列中的结点依次出队并链接

时间复杂度O(d(n+r)),d趟分配和收集，分配是每趟n次，收集是每趟r次，d:把关键字拆分为d个部分，n：n个数据，r：每个部分可能取r个值
稳定的

基数排序适用于：
1.数据元素的关键字可以方便的拆分为d组，且d较小
2.每组关键字的取值范围不大，即r较小
3.数据元素个数n较大
*/
typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode,*LinkList;

typedef struct {//链式队列
	LinkNode* front, * rear;//队列的队头和队尾指针
}LinkQuene;

/******************************************************************/
/*
外部排序：数据元素太多，无法一次全部读入内存进行排序
使用“归并排序”的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序

首先构造初始归并段，生成一小段一小段内部有序的子序列
然后进行多次归并

优化：1.将二路归并改为多路归并，但这也会带来负面影响：k路归并时，需要开辟k个输入缓冲区，内存开销增加；
没挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加（败者树可以减少对比关键字次数）
2.减少初始归并段数量：譬如内存中有四个块，可以一次读入外存四个块进行内部排序，这样生成的初始归并段更长，数量更少
*/

/*
败者树，解决了外部排序中多路归并需要对比次数过多的问题
可以理解ppt中关于七龙珠打斗的流程
*/

/*
置换选择排序可以得到更大的初始归并段
理解ppt
要注意到输出归并段时是存在输出缓冲的
*/

/*
最佳归并树:归并树的带权路径长度就是整个归并的读写磁盘次数，为了让读写磁盘的次数变少，我们可以依据haffman树的有关原理构造最佳归并树
注意：对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树，则需要
补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造
*/

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}
/****************************************************************************/


int main()
{
	int a[13] = { 9,78,54,97,16,18,9,26,4,89,6,48,64};
	//InsertSort2(a, 8);
	//ShellSort(a, 8);
	//BubbleSort(a, 9);
	//SelectSort(a, 9);
	//QuickSort(a, 0, 8);
	//BuildMaxHeap(a, 8);
	//HeapSort(a, 8);
	//Merge(a, 0, 4, 8);
	MergeSort(a, 0,12);
	for (int i = 0; i < 13; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}