常用排序算法汇整

注:文章中的一些排序演示的GIF除特殊说明外均来源于网络,简介来源于百度百科

排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性
冒泡排序O(n2)O(n)O(n2)O(1)稳定
选择排序O(n2)O(n2)O(n2)O(1)不稳定
插入排序O(n2)O(n)O(n2)O(1)稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定
快速排序O(n log n)O(n log n)O(n2)O(n log)不稳定
计数排序O(n + k)O(n + k)O(n + k)O(k)稳定

请注意,这个表格中以下几种排序方法需要交换元素

  • 冒泡排序
  • 选择排序
  • 快速排序

总之,只要在下方提供的代码中发现有swap()函数的都是需要交换元素

冒泡排序

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成

#include <cstdio>
#include <algorithm>

const int n = 9;
int a[] = {0, 9, 5, 6, 8, 2, 7, 3, 4, 1};

int main()
{
	for(int i = n - 1; i > 0; i--)
		for(int j = 1; j < i + 1; j++)
			if(a[j] > a[j + 1])
				std::swap(a[j], a[j + 1]);
	
	for(int i = 1; i < n + 1; i++)
		printf("%d ", a[i]);
	return 0;
}

选择排序

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

#include <cstdio>
#include <algorithm>

const int n = 9;
int a[] = {0, 9, 5, 6, 8, 2, 7, 3, 4, 1};

int main()
{
	
	for(int i = 1; i < n; i++)
	{
		int tmp = i;
		for(int j = i + 1; j <= n; j++)
			if(a[tmp] > a[j])
				tmp = j;
		
		if(tmp != i)
			std::swap(a[tmp], a[i]);
	}
	
	for(int i = 1; i < n + 1; i++)
		printf("%d ", a[i]);
	return 0;
}

插入排序

将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中

基本思想:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止

#include <cstdio>

const int n = 9;
int a[] = {0, 9, 7, 8, 2, 5, 1, 3, 6, 4};

int main()
{
	
	for(int i = 2; i <= n; i++)
	{
		int tmp = a[i];
		int j = i - 1;
		
		while(j >= 0 && a[j] > tmp)
			a[j + 1] = a[j], j--;
		
		if(j != i - 1)//这句可以省略? 
			a[j + 1] = tmp;
	}
	
	for(int i = 1; i < n + 1; i++)
		printf("%d ", a[i]);
	return 0;
}

归并排序

归并排序不仅可以排序,还可以求逆序对数

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序

两个有序表合并成一个有序表,称为二路归并

注:代码实现的是归并排序+求逆序对,如不需要求逆序对,只需要删除有关“ans”变量的内容即可

另可参考这篇文章

#include<cstdio>

int a[1005], r[1005], n, ans;
void msort(int s, int t)
{
	if(s == t)
		return;
	int mid = s + t >> 1;
	msort(s, mid), msort(mid + 1, t);
	
	int i = s, j = mid + 1, k = s;
	while(i <= mid && j <= t)
		if(a[i] <= a[j])
			r[k++] = a[i++];
		else
			r[k++] = a[j++], ans += mid - i + 1; 
	while(i <= mid)
		r[k] = a[i], k++, i++;
	while(j <= t)
		r[k] = a[j], k++, j++;
	for(int i = s; i <= t; i++)
		a[i] = r[i];
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	msort(1, n);
	
	for(int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	
	printf("%\nd\n", ans);
	return 0;
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

关于快排,stl中有一些实现快排的函数,比如sort()

#include <cstdio>
#include <algorithm>

const int n = 9;
int a[] = {0, 9, 7, 8, 2, 5, 1, 3, 6, 4};

void qsort(int l, int r)
{
	if(r <= l)
		return;
	int i = l, j = r + 1, key = a[l];
	while(true)
	{
		while(a[++i] < key)
			if(i == r)
				break;
		
		while(a[--j] > key)
			if(j == l)
				break;
		
		if(i >= j)
			break;
		
		std::swap(a[i], a[j]);
	}
	std::swap(a[l], a[j]);
	
	qsort(l, j - 1);
	qsort(j + 1, r);
	return;
}

int main()
{
	qsort(1, n);
	
	for(int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	return 0;
}

计数排序

这是最快最简单的排序算法,但同时也是最浪费内存的一种算法

有些地方也叫作“桶排序”,但我去查了桶排序的定义,和计数排序还是有区别的,准确的来说,桶排序≠基数排序

不过我的书(普及组版)上是把计数排序当做桶排,因为桶排序的原理涉及到hash,所以书上就干脆把桶排当做是计数排序

换句话说

  • 普及组:桶排序≠基数排序
  • 提高组:桶排序=基数排序
#include <cstdio>

int n, a[1005];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		a[x]++;
	}
	
	
	for(int i = 1; i <= 1000; i++)
		for(int j = 1; j <= a[i]; j++)
			printf("%d ", i);
	return 0;
}

↑其实这是一种不规范的做法,我写成这样是为了便于理解

本站遵循「CC BY 4.0」创作共享协议,转载请注明出处