常用排序算法总结

Myth丶恋晨 2022-10-29 07:41 237阅读 0赞

**目录**

比较排序

插入排序 O()

冒泡排序 O()

快速排序O(nlgn)

归并排序O(nlgn)

线性时间排序

计数排序O(n+k)

基数排序O(pn+pk)

--------------------

排序算法可以分为两大类：**比较排序**和**线性时间排序。**

*  比较排序：依赖于比较和交换来将元素移动到正确的位置上。时间复杂度不可能小于O(n logn)。
 *  线性时间排序：依赖于数据集合中的某些特征，并不是所有场合都能使用，时间复杂度为O(n)。

某些排序算法只使用数据本身的存储空间来处理和输出数据（就地排序）；而有些则需要额外的空间来处理和输出数据。

# 比较排序 #

## 插入排序 O(![n^\{2\}][n_2]) ##

插入排序虽然不是最有效的排序算法，但是它**简单**，并且**不需要额外的存储空间**。其最佳的应用场景是对一个小的数据集合进行递增排序。打扑克整理扑克牌时，使用到的就是插入排序。

优点：当将元素插入一个有序数据集中时，最需要最多对有序数据集进行一次遍历，而不需要完整地运行算法。这个特性使得插入排序在增量排序中非常高效。

void myInsertSort(vector<int> &arr) {
    	int sorted, i, j,temp;
    	// j 指向的为未排序的数字
    	for (j = 1; j < arr.size(); j++) {
    		temp = arr[j];//temp 为当前需要排序的数字
    		i = j - 1;
    		sorted = arr[i];// sorted 为已排序好的最后一个数字
    		// i 指向已排序的数字
    		while (i>=0 && temp < arr[i])
    		{
    			arr[i + 1] = arr[i];
    			i--;
    		}
    		arr[i + 1] = temp;
    	}
    }

## 冒泡排序 O(![n^\{2\}][n_2]) ##

void bubleSort(vector<int> &arr) {
    	int temp;
    	for (int i = 0; i < arr.size()-1; i++) {
    		for (int j = i + 1; j < arr.size(); j++) {
    			if (arr[j - 1] > arr[j]) {
    				temp = arr[j - 1];
    				arr[j - 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    	}
    }

## 快速排序O(nlgn) ##

快速排序是一种分治排序算法，广泛认为它是解决一般问题的最佳排序算法。同插入排序一样，它也属于比较排序，而且不需要额外的存储空间，在处理中到大型数据集时，快速排序是比较好的选择。

快速排序算法是一种分治算法，因此可以用分治的思想将排序分为三个步骤：

1.  分：设定一个分割值，并将数据分割成两部分。
2.  治：分别在两部分使用递归的方式继续使用快速排序法。
3.  合：对分割部分排序直至完成。

快速排序最坏情况下的性能不会比插入排序的最坏情况好。事实上，通过采用合适的方法选择分割值，可以大大改善快速排序最坏情况的效率，使其表现得与其平均情况相当。

选择分割值一种行之有效的方法是通过**随机选择法**来选取：

**首先随机选择三个数，然后选择这三个数的中间值（中位数），**由于这种分割算法依赖随机数的统计特性，从而保证快速排序的整体性能。

[快速排序C++实现][C]

## 归并排序O(nlgn) ##

归并排序是另一种运用**分治法**排序的算法。它是**比较排序**，并且它**需要额外的存储空间**来完成排序工程。**归并排序**（Merge Sort）是建立在[归并][Link 1]操作上的一种有效，**稳定**的[排序算法][Link 2]，该算法是采用[分治法][Link 3]（Divide and Conquer）的一个非常典型的应用。将已有序的子序列[合并][Link 4]，得到完全有序的[序列][Link 5]；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为[二路归并][Link 6]。

排序过程：

1.  分：将数据集分为两半。
2.  治：分别在两个部分用递归的方式继续使用归并排序法。
3.  合：将分开的两部分合并成一个有序的数据集。

归并算法与其他排序最大的不同在于它的归并过程：**将两个有序的数据集合并成一个有序的数据集。**

从下文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的**最好，最坏，平均时间复杂度均为O(nlogn)。**

归并排序需要额外的存储空间来运行，因为合并过程不能在无序数据集本身进行，所以必须要有**两倍于无序数据集的空间**来运行算法。

然而归并排序对于海量数据处理还是非常有价值的，因为它能够按预期将数据集分开。这使得我们能够将数据集分割为更为可管理的数据，接着使用归并排序处理数据，然后不断地合并数据，在这个过程中并不需要一次存储所需要的数据。

归并排序本质上是将一个无序元素集分割成许多个只包含一个元素的集，然后不断地将这些小集合并，直到一个新的大有序数据集生成。

归并算法流程图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

合并两个数据集：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1][]

# 线性时间排序 #

## 计数排序O(n+k) ##

计数排序是一种高效的线性时间排序，它通过计算一个集合中元素出现的次数来确定集合如何排列。计数排序是不需要比较的。

局限性：只能用于整型或者那些可以用整型来表示的数据集合。这是因为计数排序利用一个数组的索引来记录元素出现的次数。例如，整数3出现过4次，那么将4存储到数组索引为3的位置上。同时我们还需要知道集合中最大整数的值。以便为数组分配足够的空间。

优点：

*  速度快，时间复杂度为O(n)
 *  稳定，稳定的排序能是具有相同数值的元素有相同的顺序，就像它们在原始集合中表现出来的那样。在某些情况下，这是一个非常重要的特性。（比如按分数排名，即使是相同分数，排名也有先后顺序）

计数排序的本质是通过计算无序集合中整数出现的次数来决定集合应该如何排序的。

计数排序的**时间复杂度为O(n+k)**，其中n为要排序的元素个数，k为data中的最大整数加1.这是由于计数排序包含三个循环，其中两个的运行时间正比于n，另一个运行时间正比于k。对于空间上来说，计数排序需要两个大小为n的数组，一个大小为k的数组。

int ctsort(int *data, int size, int k) {
    	int *counts, *temp;
    	int i, j;
    
    	// 为计数数组分配存储空间，数组的索引值就是元素本身，counts包含每个元素在有序集合temp中的偏移量
    	if ((counts = (int *)malloc(k * sizeof(int))) == NULL) {
    		return -1;
    	}
    	// 为临时存放排序好的数组开辟空间
    	if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {
    		return -1;
    	}
    
    	//初始化计数数组
    	for (i=0; i < k; i++)
    	{
    		counts[i] = 0;
    	}
    	//计算每个元素出现的次数
    	for (j = 0; j < size; j++) {
    		counts[data[j]]++;//元素的值就是计数数组的下标
    	}
    	//将计数数组元素的值逐个累加
    	for (i=1; i< k;i++)
    	{
    		counts[i] = counts[i] + counts[i - 1];
    	}
    	//使用计数数组定位每一个元素，从后往前
    	for (j = size-1; j >=0; j--)
    	{
    		counts[data[j]]--;
    		temp[counts[data[j]]]= data[j];
    		
    	}
    	//temp 里存放的就是已排序好的数组，将内存复制
    	memcpy(data, temp, size * sizeof(int));
    
    	//释放内存
    	free(counts);
    	free(temp);
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 2][]

## 基数排序O(pn+pk) ##

p为每个元素的位数，n为元素的个数，k为基数。

基数排序的时间复杂度取决于它选择哪种稳定排序来对位数值进行排序。由于基数排序对每个p位置的位数值使用计数排序，因此基数排序消耗的运行时间是基数排序的p倍，即O(pn+pk)。其对空间的要求与计数排序一样：为两个大小为n的数组，一个大小为k的数组。

[基数排序][Link 7]

基数排序是将数据按位分开，并从数据的最低有效位到最高有效位进行比较，依次排序，从而得到有序数据集合。例如对\{15,12,49,16,36,40\}进行排序。在对个位数进行排序后，其结果为\{40,12,15,16,36,49\}，在对十位进行排序后，其结果为\{12,15,16,36,40,49\}。

有一点非常重要，在对每一位数值进行排序时，其排序过程必须是**稳定**的。因为，一旦一个数值通过较低有效位的值进行进行排序之后，此数据的位置应该不变，除非通过较高有效位的值进行比较后需要调整位置。例如在上例中，整数12和15的十位数都包含1，当对其十位数进行排序时，一个不稳定的算法可能不会维持其在个位数排序过程中的顺序。而一个稳定的排序算法可以保证它们不重新排序。**基数排序会用到计数排序**，因为对于基数排序来说，除了稳定性，它还是一种线性算法，其必须知道每一位可能的最大值。

基数排序并不局限于对整型数据进行排序，只要能把元素分割成整型数，就可以使用基数排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 3][]

[n_2]: https://private.codecogs.com/gif.latex?n%5E%7B2%7D
[C]: https://blog.csdn.net/luolaihua2018/article/details/110368341
[Link 1]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741
[Link 2]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605
[Link 3]: https://baike.baidu.com/item/%E5%88%86%E6%B2%BB%E6%B3%95/2407337
[Link 4]: https://baike.baidu.com/item/%E5%90%88%E5%B9%B6/5615281
[Link 5]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[Link 6]: https://baike.baidu.com/item/%E4%BA%8C%E8%B7%AF%E5%BD%92%E5%B9%B6/53201558
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221024/bfab62a93a364eafa20ea0df31a00847.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1]: /images/20221024/3fadd973e839446b80f42bdb026346ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 2]: /images/20221024/a776ed6a6ef248e69d6951f59f7f0a14.png
[Link 7]: https://blog.csdn.net/luolaihua2018/article/details/110187087
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 3]: /images/20221024/82dd24f21b794c4e959cee00bf78de49.png