排序算法性能比较

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gyqdrdnt-1660610091407)(C:\Users\11606\AppData\Roaming\Typora\typora-user-images\image-20220721090524078.png)]$

冒泡排序

优化版本

void BubbleSort(int a[], int len) {
	bool exchange;   //为交换直接退出
	for (int i = 0; i < len-1; i++)
	{
		exchange = false;
		for (int j = 0; j < len-i-1; j++)
		{
			if (a[j] > a[j+1])
			{
				swap(a[j], a[j + 1]);
				exchange = true;
			}
		}
		if (!exchange)
			break;
	}	
}

选择排序

首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。

void SelectionSort(int a[], int len) {
	int min;
	for (int i = 0; i < len-1; i++)
	{
		min = i;
		for (int j = i+1; j < len; j++)
		{
			if (a[min] > a[j])
				min = j;
		}
		swap(a[min], a[i]);
	}
}

插入排序

把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。

void InsertSort(int a[], int len) {
	int temp;
	for (int i = 1; i < len; i++)
	{
		temp = a[i];
		for (int j = i-1; j >=0 ; j--)
		{
			if (a[j] > temp) 
				a[j + 1] = a[j];
			else {
				a[j+1] = temp;
				break;
			}
		}
	}
}

希尔排序

希尔排序是对插入排序的改进；他减少了交换的次数，优化了插入排序。

希尔排序算法的基本思想是将待排序的表按照间隔切割成若干个子表，然后对这些之表进行插入排序。一般来说第一次的间隔（divide ) 为整个排序表的一半（divide = ceil(size /2);）然后对按照这些间隔划分的子表进行直接插入排序，第二次间隔又是第一次的一半（ divide = ceil(divide / 2)）然后对按照这些间隔划分的子表。

void shellSort(int a[], int len) {
	int jump = len / 2; //跨越长度；
	int i, j;
	while (jump >=1)
	{
		for ( i = jump; i < len; ++i) {
			int temp = a[i];
			for ( j = i - jump; j >= 0 && a[j] > temp; j -= jump) //以jump为距离进行插入排序
			{
				a[j+jump] = a[j];
			}
			a[j + jump] = temp;
		}
		jump /= 2;
	}
}

计数排序

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。（先增加到0，记住差距）

void CountSort(int a[], int len) {
	int max = INT_MIN;
	for (int i = 0; i < len; i++) //获得最大值
		if (max < a[i])
			max = a[i];

	vector<int> counts(max+1,0);    //用于计数，记录每个值出现次数
	for (int i = 0; i < len; i++)  
	{
		counts[i]++;
	}

	int index = 0;
	for (int i = 0; i < counts.size(); i++)  //按照此处，重新对数组赋值
	{
		while (counts[i] > 0) {
			a[index] = i;
			counts[i]--;
		}
	}
}

桶排序

桶排序可以看成是计数排序的升级版，它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。

桶排序序思路：

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

归并排序

归并算法的核心思想是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

递归版

void merge_sort(int a[], int low, int high) {
	if (low >= high)
		return;

	int* temp = (int *)malloc( (high - low +1)* sizeof(int));  //分配临时数组
	int key = 0;
	int center = (low + high) / 2;
	int left_start = low, left_end = center;         //左边区间
	int right_start = center + 1, right_end = high;   //右边区间

	merge_sort(a, low,  center);   //递归处理
	merge_sort(a, center+1,  high);

	while (left_start <= left_end && right_start <= right_end)  //合并区间到temp中
	{
		temp[key++] = a[left_start] < a[right_start] ? a[left_start++] : a[right_start++];
	}
	while (left_start <= left_end)
		temp[key++] = a[left_start++];
	while (right_start <= right_end)
		temp[key++] = a[right_start++];

	for (int i = 0; i < high-low+1; i++)  //重新将temp替换a
		a[low + i] = temp[i];

	delete[] temp;  //删除空间
}

迭代版

void merge_sort(int a[], int len) {
	int* temp = new int[len];  //暂存转移值
	for (int seg = 1; seg < len; seg*=2)  //seg，分割片段大小
	{
		for (int start = 0; start < len; start += 2 * seg) {       //每两个片段进行组合
			int low = start, center = min(start + seg, len), high = min(start + 2 * seg, len); //片段左中右断点
			int key = low;
			int left_start = low, left_end = center;
			int right_start = center, right_end = high;  

			while (left_start<left_end && right_start < right_end)  //开始合并
				temp[key++] = a[left_start] < a[right_start] ? a[left_start++] : a[right_start++];
			while (left_start < left_end)
				temp[key++] = a[left_start++];
			while (right_start < right_end)
				temp[key++] = a[right_start++];

			for (int i = low; i < high; i++)  // 交换转移值
			{
				a[i] = temp[i];
			}
		}
	}
	delete[] temp;
}

快速排序

每次都取数组的第一个元素作为基准元素，凡是大于这个基准元素的都放在他的右边，凡是小于这个基准元素的都放在它的左边。

递归版本

void quickSort(int a[], int left, int right)
{	
	if (left>=right)   return;

	int i = left, j = right;
	int temp = a[left];

	while (i < j)  //归位  左小右大
	{
		while (i < j && a[j] >= temp)		
			j--;
		while (i < j && a[i] <= temp)
			i++;
		if (i < j)
			swap(a[i], a[j]);
	}
	swap(a[i], a[left]);    
	quickSort(a, left, i-1);   //递归调用
	quickSort(a, i+1, right);	
}

非递归版本

// 快速排序非递归版本  假设每次都以第一个元素作为枢轴值，进行一趟划分：
int partition(int a[], int low, int high) {  //对成对点进行排序
	int key = a[low],temp = low;
	while (low<high)
	{
		while (low < high && a[high] >= key)
			high--;
		while (low < high && a[low] <= key)
			low++;
		if (low < high)
			swap(a[low], a[high]);
	}
	swap(a[temp], a[low]);
	return low;
}
void quickSort(int a[], int left, int right) {
	stack<int> s;
	int boundary;
	if (left<right)
	{
		int boundary = partition(a, left, right);  //首次
		if (boundary -1>left)
		{
			s.push(left);  //先入栈左端点
			s.push(boundary - 1); //再入栈右端点
		}
		if (boundary +1<right)
		{
			s.push(boundary + 1);
			s.push(right);
		}
		while (!s.empty())   //遍历栈中所有成对点
		{
			int high = s.top();  //先取出右端点
			s.pop();
			int low = s.top(); 	//再取出左端点
			s.pop();
			boundary = partition(a,low,high);
			if (boundary - 1 > low)
			{
				s.push(low);
				s.push(boundary - 1);
			}
			if (boundary + 1 < high)
			{
				s.push(boundary + 1);
				s.push(high);
			}
		}
	}
}

堆排序

堆排序顾名思义，是利用堆这种数据结构来进行排序的算法。堆是一种优先队列，两种实现，最大堆和最小堆，以下以最大堆举例。

我们完全可以把堆（以下全都默认为最大堆）看成一棵完全二叉树，但是位于堆顶的元素总是整棵树的最大值，每个子节点的值都比父节点小，由于堆要时刻保持这样的规则特性，所以一旦堆里面的数据发生变化，我们必须对堆重新进行一次构建。

既然堆顶元素永远都是整棵树中的最大值，那么我们将数据构建成堆后，只需要从堆顶取元素不就好了吗？第一次取的元素，是否取的就是最大值？取完后把堆重新构建一下，然后再取堆顶的元素，是否取的就是第二大的值？反复的取，取出来的数据也就是有序的数据。

//堆排序（大顶堆）
void build_Heap(int a[], int len, int index){
	int left = index * 2 + 1;  //左节点 
	int right = index * 2 + 2;  //右节点
	int max = index;   //最大节点
	if (left< len && a[left] > a[max])
	{
		max = left;
	}
	if (right<len && a[right] > a[max])
	{
		max = right;
	}
	if (max != index) {   //父节点比儿子节点小，则交换，在继续向下缺点当前节点位置。
		swap(a[max], a[index]);
		build_Heap(a, len, max);
	}	
}

void HeapSort(int a[], int len) {
	for (int i = len / 2 -1; i>=0; --i)
		build_Heap(a, len, i);    //从倒数第二层开始构建堆

	for (int i = len-1; i > 0 ; --i)
	{
		swap(a[0], a[i]);  //将最大的放到对尾
		build_Heap(a, i, 0);  //去除最后一个排好的后，重新确定剩余元素堆位置。
	}
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将数据按位数切割成不同的数字，然后按每个位数分别比较。

假设说，我们要对 100 万个手机号码进行排序，应该选择什么排序算法呢？排的快的有归并、快排时间复杂度是 O(nlogn)，计数排序和桶排序虽然更快一些，但是手机号码位数是11位，那得需要多少桶？内存条表示不服。
这个时候，我们使用基数排序是最好的选择。

int max_bits(int a[], int len){  //获得最大位数
	int max = INT_MIN;
	int num = 1;
	for (int i = 0; i < len; i++)
	{
		max = max > a[i] ? max : a[i];
	}
	while (max/10 != 0)
	{
		max /= 10;
		num++;
	}
	return num;
}

void radixsort(int a[], int len) {
	int* temp = new int[len];
	int count[10];
	int maxbits = max_bits(a, len);
	int radix = 1;
	int k;
	for (int j = 0; j <maxbits ; j++)  //对每个位进行排序
	{
		memset(count, 0, sizeof(count));  //重置计数器

		for (int i = 0; i < len; i++)  //按位数进行计数
		{
			k = (a[i] / radix) % 10;
			count[k]++;
		}

		for (int i = 1; i < 10; i++)      //共享桶空间， 总和为len；得到每个数应该放入bucket中的位置
			count[i] += count[i - 1];

		for (int i = len-1; i >=0 ; i--)  //如果从前往后排，共享的count[k]不好计算;count[k]保存k目前能放的最大下标；
		{
			k = (a[i] / radix) % 10;
			temp[count[k]-1] = a[i];
			count[k]--;
		}

		for (int i = 0; i < len; i++)
			a[i] = temp[i];

		radix *= 10;
	}
}