[数据结构与算法] 常见的十种排序算法（C++下实现）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 常见的十种排序算法（C++下实现） -> 正文阅读

[数据结构与算法]常见的十种排序算法（C++下实现）

常见的十种排序算法（C++下实现）

前言
排序算法是比较常见的一种算法，这里笔者给出十种排序算法在C++下的实现，并结合资料作一个简单的概括。
源码地址：https://github.com/Z-Li-Jie/Sorts

概括

1、内排序和外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为：内排序和外排序。
内排序是在排序整个过程中，待排序的所有记录全部放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。笔者在这里主要介绍内排序的多种方法。

2、算法分类

十大常见排序算法大致可分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

在这里插入图片描述
3、算法的性能

排序算法的性能主要受3个方面影响

时间性能：排序算法是数据处理中经常执行的一种操作，往往属于系统的核心部分，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要作排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来避免。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
辅助空间：评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间外，执行算法所需要的其他存储空间。
算法的复杂性：这里指的是算法本身的复杂度，而不是指算法的时间复杂度，当算法过于复杂时也会影响排序的性能。

4、其他
稳定：序列中，若元素两等值元素a,b，其中a排在b前面，排序后a仍然在b的前面。
不稳定：即排序前后，元素a,b的顺序不一致。时间复杂度：对排序数据的总的操作次数，反映当n（序列总数）变化时，操作次数呈现的规律。
空间复杂度：即算法在计算机内执行时所需存储空间的度量。它也是数据规模n的函数。

一、冒泡排序（bubble_sort）
1、基本思想：

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
2、算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有元素重复以上的步骤，直到上一步有序的位置（即上一步骤的最后一位）；
重复上述1~3步骤，直到完成排序。

3、动图演示
在这里插入图片描述
4、代码实现及实例

//常规算法
int main()
{
	vector<int> ans = { 3,7,1,3,22,6,9,2,4,6 };
	cout << "排序前：";
	for (auto &num : ans)
		cout << num << " ";
	cout << endl;
	for (int i = 0; i < ans.size() - 1; i++)
	{
		for (int j = 0; j < ans.size() - i - 1; j++)
		{
			if (ans[j] > ans[j + 1])
			{
				swap(ans[j], ans[j + 1]);
			}
		}
	}
	cout << "排序后：";
	for (auto &num : ans)
		cout << num << " ";
	cout << endl;

	return 0;
}

在这里插入图片描述
5、算法改进及实现

这样的冒泡程序还可以进行优化

设置一个标记变量flag，从后往前，比较相邻元素大小，若前一个元素比后一个元素大，则交换数据，并重新设置标记变量；
从后往前，对每队相邻的元素作相同的工作，这样会将最小的元素移到最前面，像是将小的元素慢慢浮上去；
重复上述步骤，其中，若一趟排序中标记变量没有重置（即无可交换的元素，表示序列已然有序），则提前退出循环。

//优化算法
int main()
{
	vector<int> ans = { 3,7,1,3,22,6,9,2,4,6 };
	cout << "排序前：";
	for (auto &num : ans)
		cout << num << " ";
	cout << endl;
	bool flag = true;
	//当没有数据交换时，说明序列已然有序，则提前退出循环
	for (int i = 0; i < ans.size()&&flag; i++)
	{
		flag = false;
		for (int j = ans.size() - 2; j >= 0; j--)
		{
			if (ans[j] > ans[j + 1])
			{
               swap(ans[j], ans[j + 1]);
			   flag = true;
			}
				
		}
	}
	cout << "排序后：";
	for (auto &num : ans)
		cout << num << " ";
	cout << endl;

	return 0;
}

在这里插入图片描述
二、快速排序(quick_sort)

1、基本思想

快速排序通过一趟排序将排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两部分记录进行排序，以达到整个序列有序的目的。

2、算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序（即对上一步中的两个分区重复操作）。

注：“基准”一般选择为序列的最左边的元素，这里，笔者为了基准的一般性，将从序列中最左、最右、中间三个元素中选择其中值作为“基准”。

3、动图演示
在这里插入图片描述
4、代码实现及实例

//递归求解
void quick_sort(vector<int>& array, int left, int right)
{
	if (left >= right)
		return;
	//设置基准值
	int key = array[left];
	int i = left, j = right;
	while (i < j)
	{
		//从右向左，找出小于基准的数，并进行交换
		while (i < j&&array[j] >= key)
			j--;
		array[i] = array[j];
		//从左向右，找出大于基准的数，并进行交换
		while (i < j&&array[i] <= key)
			i++;
		array[j] = array[i];
	}
	array[i] = key;
	quick_sort(array, left, i-1);
	quick_sort(array, i + 1, right);
}

//在最左、最右、中间选择其中的中值作为基准
	int left = 0, right = ans.size() - 1,mid = ans.size() / 2;
	if (ans[left] < ans[mid])
	{
		if (ans[mid] < ans[right])
			swap(ans[left], ans[mid]);
		else
		{
			if (ans[left] < ans[right])
				swap(ans[left], ans[right]);
		}
	}
	else
	{
		if (ans[left] > ans[right])
		{
			if (ans[mid] > ans[right])
				swap(ans[left], ans[mid]);
			else
				swap(ans[left],ans[right]);
		}
	}

在这里插入图片描述
三、简单插入排序 (insert_sort)
1、基本思想

简单插入排序的基本操作是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表。

2、算法步骤

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

3、动图演示
在这里插入图片描述
4、代码实现及实例

void insert_sort(vector<int>& array)
{
	for (int i = 1; i < array.size(); i++)
	{
		int index = i - 1;
		int key = array[i];
		while (index >= 0 && array[index] > key)
		{
			array[index + 1] = array[index];
			index--;
		}
		array[index + 1] = key;
	}
}

在这里插入图片描述
四、希尔排序 (shell_sort)
1、基本思想

希尔排序是第一个突破O(n2)的排序算法，是简单插入排序的改进版。它和插入排序的不同之处在于，它采取了跳跃分割的侧率：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果使基本有序（小的的元素基本在前面，大的基本在后面，不大不小的在中间）而不是局部有序。希尔排序又叫作缩小增量排序。

2、算法步骤

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序（每一次增量的大小即为序列分割的序列数）；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1
时，整个序列作为一个表来处理，表长度即为整个序列的长度。

3、动图演示
在这里插入图片描述

4、代码实现及实例

void shell_sort(vector<int>& array)
{
	int increment = array.size();
	while (increment > 1)
	{
		//增量序列(增量相当于将序列分割的子序列数)
		increment = increment / 2 ;
		for (int i = increment; i < array.size(); i++)
		{
			int j = i;
			int key = array[i];
			while (j - increment >= 0 && key < array[j - increment])
			{
				array[j] = array[j - increment];
				j = j - increment;
			}
			array[j] = key;
		}
	}
}

在这里插入图片描述
五、简单选择排序 (select_sort)

1、基本思想

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2、算法步骤

初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录
R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

3、动图演示
在这里插入图片描述
4、代码实现及实例

void select_sort(vector<int>& array)
{
	for (int i = 0; i <array.size() ; i++)
	{
		int index = i;
		int key = array[i];
		for (int j = i + 1; j < array.size(); j++)
		{
			if (array[j] < key)
			{
				index = j;
				key = array[j];
			}
		}
		swap(array[i], array[index]);
	}
}

在这里插入图片描述
六、堆排序 (heap_sort)

1、基本思想

堆排序就是利用堆（默认大顶堆）进行排序的方法。它的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它和堆数组的末尾元素交换，然后将剩余的n-1元素的序列重新构造成一个堆，重复上述操作，最后便能得到一个有序序列了。
注：堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2、算法步骤

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

3、动图演示
在这里插入图片描述
4、代码实现及实例

//构建大根堆
void maxheap(vector<int>& array, int start, int end)
{
	int j = 2 * start + 1;
	while(j<=end-1)
	{
		//判断左右孩子的值
		if (j <= end - 1 && array[j] < array[j + 1])
			j++;
		if (array[j] < array[start])
			break;
		else
		{
			swap(array[j], array[start]);
			start = j;
			j = 2 * j + 1;
		}
	}
}

//堆排序
void heapsort(vector<int>& array, int len)
{
	//构建大根堆，叶子节点不用参与
	for (int i = len / 2 - 1; i >= 0; i--)
	{
		maxheap(array, i, len - 1);
	}

	for (int i = len - 1; i >= 1; i--)
	{
		//将堆顶的根节点（此时的最大值）和末尾元素交换
		swap(array[0], array[i]);
		//将0~i-1之间的元素重新构建大根堆
		maxheap(array, 0, i-1);
	}
}

在这里插入图片描述
七、归并排序 (merge_sort)

1、基本思想

归并排序就是利用归并的思想实现排序的方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

2、算法步骤

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序（递归）；
将两个排序好的子序列合并成一个最终的排序序列。

3、动图演示
在这里插入图片描述
4、代码实现及实例

void merge_sort(vector<int>& array, int left, int right)
{
	if (left >= right)
		return;

	int mid = (left + right) >> 1;
	merge_sort(array, left, mid);
	merge_sort(array, mid + 1, right);
	int l = left, r = mid + 1;
	int len = right - left + 1;
	int i = 0;
	vector<int> tmp(len,0);
	//此时数组的左右两子数组元素分别有序，现在使其合并起来也有序
	while (l <= mid && r <= right)
	{
		if (array[l] <= array[r])
			tmp[i++] = array[l++];
		else
			tmp[i++] = array[r++];
	}
	//将左子数组中剩余元素（有序）加入进来
	while (l <= mid)
		tmp[i++] = array[l++];
	//将左子数组中剩余元素（有序）加入进来
	while (r <= right)
		tmp[i++] = array[r++];

	for (int j = 0; j < len; j++)
		array[left + j] = tmp[j];
}

在这里插入图片描述
八、计数排序 (counting_sort)

1、基本思想

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中（用空间换取时间）。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

2、算法步骤

找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

3、动图演示
在这里插入图片描述
4、代码实现及实例

//计数排序
void counting_sort(vector<int>& array,int minval,int maxval)
{
	int len = maxval - minval + 1;
	vector<int> bucket(len, 0);
	for (auto &num : array)
	{
		bucket[num - minval]++;
	}
	int index = 0;
	for (int i = 0; i < len; i++)
	{
		while (bucket[i] > 0)
		{
			array[index++] = i + minval;
			bucket[i]--;
		}
	}
}

在这里插入图片描述
九、桶排序 (bucket_sort)

1、基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。其原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

2、算法步骤

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序（如可用简单插入排序进行排序）；
从不是空的桶里把排好序的数据拼接起来。

3、图片演示
在这里插入图片描述
4、代码实现及实例

//桶排序
void bucket_sort(vector<int>& array, int sz, int minval, int maxval)
{
	//每个桶最大的深度
	int bucketcnt = floor((maxval - minval) / sz) + 1;
	vector<vector<int>> bucket(sz);

	//将每个元素分配到对应的桶序号中
	for (int i = 0; i < array.size(); i++)
	{
		bucket[floor((array[i] - minval) / bucketcnt)].push_back(array[i]);
	}
	int index = 0;

	for (int i = 0; i < sz; i++)
	{
		//这里对每个桶都运用插入排序
		insert_sort(bucket[i]);
		for (int j = 0; j < bucket[i].size(); j++)
		{
			array[index++] = bucket[i][j];
		}
	}
}

在这里插入图片描述
十、基数排序 (radix_sort)

1、基本思想

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

2、算法步骤

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

3、动图演示
在这里插入图片描述
4、代码实现及实例

void radix_sort(vector<int>& array, int maxdigit)
{
	int mod = 10;
	int dev = 1;
	//从低位至高位（每一位都是0——9），根据元素大小（取余）进行排序
	for (int i = 0; i < maxdigit; i++)
	{
		vector<vector<int>> bucket(10);
		for (int j = 0; j < array.size(); j++)
		{
			//类似桶排序
			int num = floor((array[j] % mod) / dev);
			bucket[num].push_back(array[j]);
		}

		int index = 0;
		for (int a = 0; a < bucket.size(); a++)
		{
			for (int b =0 ; b < bucket[a].size(); b++)
			{
				array[index++] = bucket[a][b];
			}
		}

		mod = mod * 10;
		dev = dev * 10;
	}
}