排序算法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];
			}
		}
	}
}

冒泡排序

交换：是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

冒泡排序：从后往前(或从前往后)两两比较相邻元素的值，每一趟排序将最小的元素交换到待排序序列的第一个位置

性能分析：空间复杂度(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;
}