十大经典排序算法+sort排序

---

本文转自：十大经典排序算法，其中有动图+代码详解，本文简单介绍+个人理解。

排序算法

经典的算法问题，也是面试过程中经常被问到的问题。排序算法简单分类如下：

这些排序算法的时间复杂度等参数如下：

其中，n代表数据规模，k代表桶的个数，In-place代表不需要额外空间，Out-place代表需要额外的空间。

冒泡排序（Bubble Sort）

最简单易懂的排序方法。每次比较两个元素，如果顺序错误，则交换之。重复地访问整个序列，直到没有元素需要交换。

算法描述

• 比较相邻的元素。如果顺序错误，就交换之；
• 遍历序列，重复步骤一，一次遍历后最大元素处于最右边；
• 重复步骤二，每次重复，可以将一个元素移至相应位置（已排好），直至所有元素排好；

算法分析

最佳情况：\(T(n) = O(n)\)，最差情况：\(T(n) = O(n^2)\)，平均情况：\(T(n) = O(n^2)\)。

参考代码

void bubbleSort(vector<int> &nums) {
	int n = nums.size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n-1-i; j++) {
			if(nums[j] > nums[j+1]) {
				// 元素交换
				nums[j] = nums[j]^nums[j+1];
				nums[j+1] = nums[j]^nums[j+1];
				nums[j] = nums[j]^nums[j+1];
			}
		}
	}
}

选择排序（Selection Sort）

最稳定的排序方法之一，无论什么情况时间复杂度都是 \(O(n^2)\)，不需要额外空间。简单直观，每次找到未排序中的最小（最大）元素，放至相应位置，执行（n-1）次排序完成。

算法描述

• 遍历无序序列，找到最小（最大）元素，将该元素与对应位置交换；
• 重复步骤一（n-1）次，将所有元素放至相应位置，即排序完毕；

算法分析

最佳情况：\(T(n) = O(n^2)\)，最差情况：\(T(n) = O(n^2)\)，平均情况：\(T(n) = O(n^2)\)。

参考代码

void selectSort(vector<int> &nums) {
	int n = nums.size(), minIndex;
	for(int i = 0; i < n-1; i++) {
		minIndex = i;
		for(int j = i+1; j < n; j++) {
			if(nums[j] < nums[minIndex])//寻找最小元素
				minIndex = j;
		}
		if(i == minIndex) continue;//相同位置元素不可异或交换
		// 元素交换
		nums[i] = nums[i]^nums[minIndex];
		nums[minIndex] = nums[i]^nums[minIndex];
		nums[i] = nums[i]^nums[minIndex];
	}
}

插入排序（Insertion Sort）

同样是一种简单易懂的排序算法，不需要额外空间。通过构建有序序列，对于未排序元素，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体步骤如下：

• 第一个元素视为已排序；
• 取出下一元素，在已排序列中从后向前扫描；
• 如果该已排序元素大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素≤新元素的位置，将新元素插入到该位置后；
• 重复步骤2~4，直至全部排好序。

算法分析

最佳情况：\(T(n) = O(n)\)，最坏情况：\(T(n) = O(n^2)\)，平均情况：\(T(n) = O(n^2)\)。

参考代码

void insertSort(vector<int> &nums) {
	int n = nums.size(), prev, num;
	for(int i = 0; i < n; i++) {
		prev = i-1;//有序序列尾部
		num = nums[i];//当前元素
		while(prev>=0 && nums[prev]>num) {
			nums[prev+1] = nums[prev];//后移
			prev--;
		}
		nums[prev+1] = num;
	}
}

希尔排序（Shell Sort）

第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。

算法描述

• 定义增量序列：{t1，t2，...，tk}，其中一般有 t1>t2>...>tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子序列进行直接插入排序。仅增量因子为1 时，整个序列作为一个序列来处理，序列长度即为整个序列的长度。

举例说明

上面的算法描述可能不是很好懂，举个例子说明一下。对与{5, 2, 4, 1, 5, 9, 7, 8, 9, 0}序列，第一趟排序，增量t1=4（自定义），序列分为{5, 5, 9}，{2,9,0}，{4,7}，{1,8}，分别对其进行插入排序，序列变为{5,0,4,1, 5,2,7,8, 9,9}；第二趟排序，增量t2=2，序列分为{5,4,5,7,9}，{0,1,2,8,9}，对其进行插入排序，序列变为{4,0, 5,1, 5,2, 7,8, 9,9}；第三趟排序，增量t3=1，序列为{4,0,5,1,5,2,7,8,9,9}，对其进行插入排序，变为{0,1,2,4,5,5,7,8,9,9}。

算法分析

希尔排序的时间复杂度和其增量序列有关系，这涉及到数学上尚未解决的难题；不过在某些序列中复杂度可以视为O(n^{1.3)；希尔排序时间复杂度的下界是n*log}2 n。

参考代码

void shellSort(vector<int> &nums) {
	int n = nums.size();
	int gap, i, j;

	for(gap = n/2; gap > 0; gap /= 2) {
		//插入排序简洁写法
		for(i = gap; i < n; i++) {
			int num = nums[i];
			for(j = i-gap; j>=0 && nums[j]>num; j-=gap)
				nums[j+gap] = nums[j];
			nums[j+gap] = num;
		}
	}
}

归并排序（Merge Sort）

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，时间复杂度始终都是O(n log n）。代价是需要额外的内存空间。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序有不少的应用，比如求解逆序对问题，只需要在归并排序的过程中添加一行代码就可以。

算法描述

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

合并的过程需要额外的空间，利用一个新数组，比较两个子序列，不断将较小元素加入新数组，最后再将新数组更新至原序列。

算法分析

最佳情况：\(T(n) = O(nlogn)\)，最差情况：\(T(n) = O(nlogn)\)，平均情况：\(T(n) = O(nlogn)\)。

空间复杂度为\(O(n)\)。

参考代码

void Merge(vector<int> &nums, int first, int med, int last) {
    int i = first, j = med+1;

    vector<int> temp(nums.size());//额外空间
    int cur=0;//当前位置
    while(i<=med && j<=last) {
        if(nums[i] <= nums[j])
            temp[cur++] = nums[i++];
        else
            temp[cur++] = nums[j++];
    }
    while(i <= med)
        temp[cur++] = nums[i++];
    while(j <= last)
        temp[cur++] = nums[j++];

    for(int m = 0; m < cur; m++)//更新数组
        nums[first++] = temp[m];
}
void mergeSort(vector<int> &nums, int first, int last) {
	if(first < last) {
	    int med = first+(last-first)/2;
	    mergeSort(nums, first, med);
	    mergeSort(nums, med+1, last);
	    Merge(nums, first, med, last);
    }
}

快速排序（Quick Sort）

基本思想：选定一个排序基准进行一趟排序，将所有元素分为两部分（大于基准和小于基准），分别对两部分在此进行快速排序。

快速排序可以用于求解第K大问题，因为每一次排序之后，可以固定一个元素。

算法描述

快速排序使用分治法来把一个序列分为两个子序列。具体算法描述如下：

• 从序列中选取排序基准（pivot）；
• 对序列进行排序，所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面，序列分为左右两个子序列。称为分区操作（partition）；
• 递归，对左右两个子序列进行快速排序。

算法分析

最佳情况：\(T(n) = O(nlogn)\)，最差情况：\(T(n) = O(n2)\)，平均情况：\(T(n) = O(nlogn)\)。

参考代码

void quickSort(vector<int> &nums, int left, int right) {
	if(left<right) {
		int l=left, r=right;
		int pivot = nums[left];//判断标准值
		while(l<r) {
			while(l<r && nums[r]>=nums[l])//一定记住要加等于号，在下面加也行
				r--;
			swap(nums[l], nums[r]);

			while(l<r && nums[l]<nums[r])//在这里加等于号也行，但必须有一个加
				l++;
			swap(nums[l], nums[r]);
		}
		nums[l]=pivot;

		quickSort(nums, l+1, right);
		quickSort(nums, left, l-1);
	}
}

堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

• 将初始待排序关键字序列(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，则整个排序过程完成。

可能看起来看起来有点复杂，在本文的参考链接中有动图解释，可能好容易理解一些。

算法分析

最佳情况：\(T(n) = O(nlogn)\)，最差情况：\(T(n) = O(nlogn)\)，平均情况：\(T(n) = O(nlogn)\)。

参考代码

int len;
void heapify(vector<int> &nums, int i) {
	int left = 2*i+1;
	int right = 2*i+2;
	int largest = i;

	if(left<len && nums[left] > nums[largest])
		largest = left;
	if(right<len && nums[right] > nums[largest])
		largest = right;

	if(largest != i) {
		swap(nums[i], nums[largest]);
		heapify(nums, largest);
	}
}
void buildMaxHeap(vector<int> &nums) {
	len = nums.size();
	for(int i = len/2; i>=0; i--)
		heapify(nums, i);
}
void heapSort(vector<int> &nums) {
	buildMaxHeap(nums);

	for(int i = nums.size()-1; i>0; i--) {
		swap(nums[0], nums[i]);
		len--;
		heapify(nums, 0);
	}
}

计数排序（Counting Sort）

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

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素C[i]是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。这种做法其实就是map的基本用法。

计数排序限制性太大，要求必须是确定范围的整数。实际做题中根本用不到，不过在某些特殊场景中可能可以用上。

算法描述

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

算法分析

当输入的元素是n 个0到k之间的整数时，它的运行时间是 \(O(n + k)\)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

最佳情况：\(T(n) = O(n+k)\)，最差情况：\(T(n) = O(n+k)\)，平均情况：\(T(n) = O(n+k)\)。

参考代码

void countingSort(vector<int> &nums, int maxValue) {
	int bucket[maxValue+1] = {0};
	int n = nums.size();
	int sorted = 0;

	for(int i = 0; i < nums.size(); i++) {
		bucket[nums[i]]++;
	}
	for(int i = 0; i < maxValue+1; i++) {
		while(bucket[i] > 0) {
			nums[sorted++] = i;
			bucket[i]--;
		}
	}
}

桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定（代码中通过设定每个桶的容量间接设定此映射关系）。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。

算法描述

• 设置桶的数量：先设定桶的容量，再根据数组的最大值和最小值计算出桶的数量；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序：由于每个桶数据量很小，可以采用插入排序；
• 将非空桶里排好序的数据拼接起来。

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

最佳情况：T(n) = O(n+k)，最差情况：T(n) = O(n+k)，平均情况：T(n) = O(n2)。

参考代码

void bucketSort(vector<int> &nums, int bucketSize) {
	int n = nums.size();
	if(n == 0) return;

	int minValue = nums[0], maxValue = nums[0];
	for(int i = 1; i < n; i++) {
		if(nums[i] > maxValue) maxValue = nums[i];
		if(nums[i] < minValue) minValue = nums[i];
	}

	if(bucketSize < 5) bucketSize = 5;//默认每个桶的容量为5
	int bucketNum = (maxValue-minValue)/bucketSize + 1;//桶的数量

	vector< vector<int> > buckets(bucketNum);

	for(int i = 0; i < nums.size(); i++)
		buckets[(nums[i]-minValue)/bucketSize].push_back(nums[i]);

	int sorted = 0;
	for(int i = 0; i < buckets.size(); i++) {
		insertSort(buckets[i]);//插入排序
		for(int j = 0; j < buckets[i].size(); j++)
			nums[sorted++] = buckets[i][j];
	}
}

基数排序（Radix Sort）

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn)，n为数组长度，k为数组中的数的最大的位数；

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

算法描述

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

算法分析

最佳情况：\(T(n) = O(n * k)\)，最差情况：\(T(n) = O(n * k)\)，平均情况：\(T(n) = O(n * k)\)。

基数排序有两种方法：MSD，从高位开始进行排序；LSD，从低位开始进行排序。

参考代码

//LSD
void redixSort(vector<int> &nums, int maxDigit) {
	int mod = 10;
	int dev = 1;
	vector< vector<int> > buckets(10);

	for(int i = 0; i < maxDigit; i++, dev*=10, mod*=10) {
		for(int j = 0; j < nums.size(); j++) {
			int bid = nums[j] % mod / dev;//取出对应数位作为桶编号
			buckets[bid].push_back(nums[j]);
		}

		int sorted = 0;
		for(int i = 0; i < buckets.size(); i++) {
			for(int j = 0; j < buckets[i].size(); j++)
				nums[sorted++] = buckets[i][j];
			buckets[i].clear();
		}
	}
}

总结

冒泡排序是基础，每轮遍历将“最大元素”移至正确位置（“最右边”），不稳定的O(n^2)；

选择排序要了解，选择排序每轮遍历将“最小（大）元素”移至正确位置（“最左（右）边”），稳定的O(n^2)；

插入排序最简单，适合数据量较小的排序，依然是O(n^2)；

希尔排序是插入排序升级版，不好用，为O(nlog^2n)；

归并排序和快速排序要熟记原理并会写代码。时间复杂度都是O(nlogn)，前者不稳定，后者稳定。最常用的排序方法。

堆排序代码复杂，不太好理解，也不好用，为O(nlogn)。

计数排序、桶排序、基数排序都不是比较排序，可以归为一类，对数据有特殊的要求。其中计数排序是基础，类似建立map对应；桶排序将数据的大小分到不同的桶中，桶内再微小排序；基数排序则是多次的桶排序，每次桶排序根据对应数位将数据分到不同桶中。

---

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

---