排序算法C++

# 排序

算法稳定性：关键字相同的元素在排序之后， 相对位置 不变
内部排序 ：排序期间元素全部存放在 内存中 的排序
外部排序 ：排序期间元素 无法全部 同时存放在内存中，必须在排序的过程中根据要求不断地 在内，外存之 间移动的排序。

# 直接插入排序

添加 哨兵 节点存放需要更换位置的节点值
从第二个位置开始
若小于前一个节点，此节点需要 前移 ，变为哨兵
根据判断往前循环判断哨兵应该放的位置，同时为了哨兵有位置放，在循环中，循环位置之后的 集体后移
找到后，将哨兵插入到对应节点
性能：时间复杂度 O(n^2 )，空间复杂度 O(1) , 稳定

	void InsertSort(Elemtype A[], int n)
	{
	//A [0] 是哨兵
	int i, j;
	for (i = 2; i < n; i++) // 循环所有节点
	{
	// 从小到大排序
	if (A[i] < A[i - 1]) // 判断那个 i 节点太小需要向前更换位置
	{
	A[0] = A[i]; // 哨兵指向 A [i] 节点
	// 向前移动寻找哨兵该插入的位置，并对元素向后移动
	for (j = i - 1; A[0] < A[j]; --j) // 当哨兵小于 j 节点时停止，
	{
	// 向后移动
	A[j + 1] = A[j];
	}
	// 哨兵小于 A [j]，在 A [j+1] 位置赋值
	A[j + 1] = A[0];
	}
	}
	}

# 折半插入排序

根据直接插入排序，引入折半查找
先 折半查找
然后统一移动带 插入位置之后 的所有元素
时间复杂度 O(n^2) 稳定算法，

	void BinsearchSort(Elemtype A[], int n)
	{
	//A [0] 是哨兵
	int i, j,low,high,mid;
	for (i = 2; i < n; i++) // 循环所有节点
	{
	// 从小到大排序
	A[0] = A[i]; // 哨兵指向 A [i] 节点
	// 向前移动寻找哨兵该插入的位置，并对元素向后移动
	// 使用折半查找找到位置
	// 设置折半查找的范围
	low = 1;
	high = i - 1; //i-1 为带查找的最后一个
	while (low <= high) // 默认递增有序
	{
	mid = (low + high) / 2; // 取中间点
	if (A[mid] > A[0]) // 如果中间节点大于哨兵，则在左边
	{
	high = mid - 1;
	}
	else
	{
	low = mid + 1; // 查右部分
	}
	}
	// 后移 high+1 后面的全部后移
	for (j = i - 1; j >= high + 1; --j)
	{
	A[j + 1] = A[j];
	}
	// 哨兵小于 A [high]，在 A [high+1] 位置赋值
	A[high + 1] = A[0];
	}
	}

# 希尔排序

又叫 缩小增量排序 ，先追求表中元素 部分有序 ，在逐渐 逼近全局 有序
先取小于 n 的步长 d , (一般取 n/2 ), 所有距离为 d 的倍数放在同一组，在各组内进行直接插入排序
取第二步步长 (d/2)
循环直到 d=1
性能分析，时间复杂度 O(n^2) , 不稳定仅适合 线性表 为 顺序存储 的情况。

	// 希尔排序
	void ShellSort(Elemtype A[], int n)
	{
	int dk, i, j;
	// 步长变化，首次取 n/2，之后每次去 dk/2
	for (dk = n / 2; dk >= 1; dk = dk / 2)
	{
	// 对每一个 dk 组进行排序，类似直接插入排序
	for (i = dk + 1; i < n; ++i)
	{
	if (A[i] < A[i - dk]) // 和前一个数据相差 dk，将 A [i] 插入到有序增量子表
	{
	A[0] = A[i]; // 暂存 A [i]
	// 记录后移，寻找查找位置
	for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) // 从 A [j] 找到 A [0] 应该插入的位置
	{
	A[j + dk] = A[j]; // 记录后移，查找插入的位置
	}
	A[j + dk] = A[0];
	}
	}
	}
	}

# 冒泡排序

交换 ：是指根据序列中 两个元素 关键字的 比较 结果来对换这两个记录在序列中的 位置
冒泡排序 ：从后往前 (或从前往后) 两两 比较相邻 元素的值，每一趟排序将最小的元素交换到 待排序序列 的第一个位置
性能分析：空间复杂度：O (1)，时间复杂度为 O (n^2), 稳定的排序

	// 交换
	void swap(Elemtype a, Elemtype b)
	{
	Elemtype* c; // 交换的中间值
	c = b;
	a = b;
	b = c;
	}

	// 顺序排序
	void BubbleSort(Elemtype A[], int n)
	{
	int i, j;
	bool flag;
	for (int i = 0; i < n - 1; i++) // 从头到尾
	{
	flag = false; // 记录是否发生了交换
	for (j = n - 1; j > i; j-- ) // 从后往前计算，每次将小的交换到前面，每次交换都能确定一个最小值
	{
	if (A[j - 1] > A[j]) // 从小到大排序
	{
	swap(A[j - 1], A[j]);// 交换，数组第一个为指针
	flag = true; // 发生了交换

	}
	}
	if (flag == false)
	{
	return; // 本趟遍历后没有发生交换，说明表已经有序退出
	}
	}
	}

# `快排排序`

快排基于 分治法
取第一个元素为 基准
通过一趟排序将待排序表划分为独立的 两部分L[1...k-1],和L[k+1...n],
性能
时间复杂度: O(log2n) 以 2 为低
空间复杂度 O(log2n)

	// 快排划分算法
	int partition(Elemtype A[], int low, int high)
	{
	// 默认将当前表中第一个作为基准
	Elemtype n = A[low];
	// 根据基准对当前区间实行快排
	while (low < high)
	{
	// 从顶部相下循环
	while (low < high && A[high] >= n)
	{
	high--;
	}
	// 结束 while，A [high] 大于 n 了需要变换位置，或者 low=high 结束循环
	A[low] = A[high]; //A [low] 原本是基准位置小的移动到左边
	// 从底部开始向上
	while (low < high && A[low] <= n)
	{
	low++;
	}
	// 若是 low 比较小，或者 low=high 结束了 while 循环
	A[high] = A[low];

	}
	A[low] = n; // 将基准值填入它的位置
	return low; // 返回基准点，作为下回分界点，左右已经实现小于大于 n 了
	}

	// 快速排序
	void QuickSort(Elemtype A[], int low, int high)
	{
	if (low < high) // 递归跳出条件
	{
	// 使用递归进行划分
	// 先进行整体划分
	int n = partition(A, low, high);
	// 对小于基准值的左边划分
	QuickSort(A, low, n - 1);
	// 对小于基准值的右边划分
	QuickSort(A, n+1, high);
	}
	}

# 简单选择排序

每一趟再待排序元素中选取关键字最小的元素加入到有序子序列中
时间复杂度: O(n^2) , 不稳定 的算法

	// 简单选择排序
	void SelectSort(Elemtype A[], int n)
	{
	int i,j,min;
	for (i = 0; i < n - 1; i++)
	{
	min = i; // 记录最小元素位置
	for (j = i + 1; j < n; j++) // 从 i+1 节点移除向后循环，判断出最小的值
	{
	if (A[j] < A[min])
	{
	min = j;
	}
	}
	if (min != i) // 如果最小数值发生了变化，进行交换
	{
	swap(A[i], A[min]);
	}
	}
	}

# 堆排序

n 个关键字序列 L [1....n] 称为堆
1， L[i]>=L[2i] 且 L[i]>=L[2i+1]
2， L[i]<=L[2i] 且 L[i]<=L[2i+1]
满足 1 的堆成为大根堆，大跟对的最大元素在根节点，且任一个非跟节点的值小于等于其双亲节点值。
对于小跟堆，新元素放在表尾，与父节点相比，若新元素比父节点更小，则将两者互换，新元素就这样一路上升，直到无法继续上升为止
被删除的元素用元素替代，然后让改元素不断 下坠 直达 无法下坠为 止。
堆排序适合关键字比较多的情况，例如，在一亿个数据中选出前 100 个最大值？
首先使用一个大小为 100 的数组，读入前 100 个数，建立小跟堆，而后依次读入余下的数，若小于堆顶则舍弃
否则用该数组取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。
性能:
空间效率：辅助单元，空间复杂度 O(1)
时间效率: O(nlogn)
不稳定

堆定义
堆排序原理

堆排序原理

堆排序原理

	// 堆排序
	void HeadAdjust(Elemtype A[], int k, int len)
	{
	// 将元素 k 作为跟的子树进行调整
	A[0] = A[k]; //A [0] 暂存子树，后续比大小要更换要更换根节点
	for (int i = 2 * k; i <= len; i *= 2)
	{
	if (i < len && A[i] < A[i + 1])
	{
	i++; //i 取 key 较大的子结点的下标
	}
	if (A[0] >= A[i])
	{
	break;// 如果根节点大于子结点最大，则可结束，符合大根堆
	}
	else
	{
	A[k] = A[i]; // 子树根节点，取代最大
	k = i; //k 的子树影响到直接子节点，以便继续向下筛选
	}
	}
	//k 最终存档的要筛选的值，等于原本最初的子树根节点
	A[k] = A[0];

	}

	void buildMaxHeap(Elemtype A[], int len)
	{
	for (int i = len / 2; i > 0; i--) // 从底部向上反复调整堆
	{
	HeadAdjust(A, i, len);
	}
	}
	// 堆排序算法
	void HeapSort(Elemtype A[], int len)
	{
	buildMaxHeap(A, len); // 初始化堆
	for (int i = len -1; i > 1; i--) // 共需要 n-1 趟的交换和建堆过程
	{
	swap(A[i], A[1]); // 输出栈顶元素 (和堆低元素交换)
	HeadAdjust(A, 1, i - 1); // 调整，把剩余的 i-1 个元素整理成堆
	}
	}

# 归并排序

归并就是将 两个或两个以上 的有序表组合成一个新的有序表。
待排序表含 有n个 记录，则可将其视为 n 个有序的子表
每个子表长度为 1，然后两两归并，得到 n/2 个长度为 2或1 的有序表，继续 两两归并 ... 如此 重复 ，直到 合并 成一个 长度为n 的有序表为止
称为 2路归并排序
性能：空间复杂度 O(n) , 时间复杂度 O(nlogn) , 稳定性

	// 归并排序 8 为 n
	Elemtype* B = (Elemtype)malloc((8 + 1) sizeof(Elemtype)); // 辅助数组，协助 merge 存储元素
	void Merge(Elemtype A[], int low, int mid, int high)
	{
	int k,i,j;
	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]) // 比较 B 中辅助大小
	{
	A[k] = B[i++]; // 将最小元素放到 A 中
	}
	else
	{
	A[k] = B[j++];
	}
	}
	while (i <= mid) // 将 i 和 j 未处理的代码复制到 A 中，因为递归底层运算，后面的元素是有序的
	{
	A[k++] = B[i++];
	}
	while (j <= high)
	{
	A[k++] = B[j++];
	}
	}
	void MergeSort(Elemtype 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,...Q0
按照各个关键字 位权重递增 ( 个，十，百 )，对 d个 关键字位分别做 分配 和 收集
收集，把 Qr+1 ... Q0 各个队列中的结点 依次出兑 并 链接
性能:
空间复杂度: 辅助存储 空间 r 个队列 O(r)
时间复杂度: O(d(n+r)) 稳定
善于解决的问题
数据元素可以方便 拆分为d组 ，且 d组较小
每个关键字取 值范围不大 ，即 r较小
数据元素个数 n较大

基数排序

	// 使用基数排序
	// 求出最大位数
	int maxBit(Elemtype A[],int n)
	{
	// 求这些代码在求 n 个元素的最大值
	int maxData = A[0];
	for (int i = 1; i < n; i++)
	{
	if (maxData < A[i])
	{
	maxData = A[i]; // 存储最大元素
	}
	}
	// 求最大值为位数
	int d = 1; // 记录最大值
	while (maxData >= 10)
	{
	maxData /= 10; // 初以 10，每次减去位数
	d++;
	}
	return d;
	}
	// 基数排序
	void radixsort(Elemtype A[], int n)
	{
	int d = maxBit(A, n); // 求出最大位数
	int i, j, k;
	int radix = 1; // 决定得出是哪一位十位 / 百位，个位
	int temp[100]; // 存储数据 A --- 对应 bucket
	int bucket[10]; // 计时器存储对应位个数
	// 进行 d 次排序
	for (i = 1; i <= d; i++) // 循环次数根据个数决定
	{
	for (j = 0; j < 10; j++)
	{
	bucket[j] = 0; // 清空计时器
	}
	// 统计每个 bucket 个位计数的元素个数
	for (j = 0; j < n; j++)
	{
	k = (A[j] / radix) % 10; // 求 A [j] 对 10 求余，即个位数
	bucket[k]++;
	}
	//bucket 存储这个对应位数，的个数
	// 循环 bucket 从 0~10 记录了立、从低到高的累计量
	// 为了能够足够空间将分好的数据存入 temp 数组内部
	for (j = 1; j < 10; j++)
	{
	bucket[j] = bucket[j - 1] + bucket[j];
	}
	// 形成存储队列存储到 temp 当中
	for (j = n - 1; j >= 0; j--)
	{
	k = (A[j] / radix) % 10; // 存储位数
	temp[bucket[k] - 1] = A[j]; // 存储了对应地址
	bucket[k]--; // 空间地址 --
	}
	// 将临时数组的内容复制到 data 当中
	for (j = 0; j <= n; j++)
	{
	A[j] = temp[j];
	}
	radix = radix * 10; // 个位之后，十位，依次
	}
	}

# 比较

对比性能

# 测试代码

	#include <iostream>
	using namespace std;
	typedef int Elemtype;
	void print_sort(Elemtype A[], int n)
	{
	//A [0] 为哨兵
	for (int i = 1; i <= n; i++) // 循环所有节点
	{
	cout << A[i] << " ";
	}
	cout << endl;
	}

	int main(void)
	{
	//A [0] 为哨兵
	Elemtype A[8]{ 0,49,38,65,97,76,13,27 };
	// 简单插入排序
	//InsertSort(A, 8);
	// 折半插入排序
	// BinsearchSort(A, 8);
	// 希尔排序
	// ShellSort(A, 8);
	// 顺序排序
	//BubbleSort(A, 8);
	// 使用快排
	// QuickSort(A, 0, 7);
	// 输出
	//SelectSort(A, 8);
	// 堆排序
	// HeapSort(A, 8);
	// 使用二路归并
	MergeSort(A, 0, 7);
	// 使用基数排序
	//radixsort(A, 8);
	print_sort(A, 7);
	return 0;
	}

C++计算机科学算法