经典排序算法

Posted on | In

十大排序算法的时间复杂度（最好情况，最坏情况，平均情况），空间复杂度，排序方式以及稳定性。

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ In-place 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ In-place 不稳定
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ In-Place 稳定
希尔排序 $O(n\log n)$ $O(n \log^2 n)$ $O(n \log^2 n)$ $O(1)$ In-place 不稳定
归并排序 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n)$ Out-place 稳定
快速排序 $O(n\log n$) $O(n\log n)$ $O(n^2)$ $O(\log n)$ In-place 不稳定
堆排序 $O(n\log n$) $O(n\log n)$ $O(n\log n)$ $O(1)$ In-place 不稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n + k)$ $O(k)$ Out-place 稳定
桶排序 $O(n + k)$ $O(n + k)$ $O(n^2)$ $O(n+k)$ Out-place 稳定
基数排序 $O(n\times k)$ $O(n\times k)$ $O(n\times k)$ $O(n+k)$ Out-place 稳定

注意：上表中的$k$表示桶的数量，$n$表示数据规模。In-place表示占用常数内存，不占用额外内存。Out-place表示占用额外内存。

冒泡排序

算法原理

BubbleSort重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法动图

图1 BubbleSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BubbleSort(vector<int>& arr)
{
	if (arr.empty())
	{
		return;
	}
	for (int i = 0; i < arr.size(); i++)
	{
		for (int j = 0; j < arr.size() - 1 - i; j++)
		{
			if (arr[j + 1] < arr[j])
			{
				int tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = tmp;
			}
		}
	}

}

选择排序

算法原理

SelectionSort首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法动图

图2 SelectionSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SelectionSort(vector<int>& arr)
{
	if (arr.empty())
	{
		return;
	}
	for (int i = 0; i < arr.size(); i++)
	{
		int minIndex = i;
		for (int j = i; j < arr.size(); j++)
		{
			if (arr[j] < arr[minIndex])
			{
				minIndex = j;
			}
		}
		int tmp = arr[minIndex];
		arr[minIndex] = arr[i];
		arr[i] = tmp;
	}
}

插入排序

算法原理

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

算法动图

图3 InsertionSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InsertionSort(vector<int>& arr)
{
	if (arr.empty())
	{
		return;
	}
	int cur{};
	for (int i = 0; i < arr.size() - 1; i++)
	{
		cur = arr[i + 1];
		int preIndex = i;
		while (preIndex >= 0 && cur < arr[preIndex])
		{
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = cur;
	}
}

希尔排序

算法原理

ShellSort也是一种插入排序，它把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法图示

图4 ShellSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void ShellSort(vector<int>& arr)
{
	int len = arr.size();
	int tmp, gap = len / 2;
	while (gap > 0)
	{
		for (int i = gap; i < len; i++)
		{
			tmp = arr[i];
			int preIndex = i - gap;
			while (preIndex >= 0 && arr[preIndex] > tmp)
			{
				arr[preIndex + gap] = arr[preIndex];
				preIndex -= gap;
			}
			arr[preIndex + gap] = tmp;
		}
		gap /= 2;

	}

}

归并算法

算法原理

算法采用分治法（Divide and Conquer）。它首先把长度为$n$的输入序列分成两个长度为$\frac{n}{2}$的子序列。然后将已有序的子序列(单个元素自然有序)合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法动图

图5 MergeSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<int> MergeSort(vector<int>& arr)
{
	if (arr.size() < 2)
	{
		return arr;
	}
	int mid = arr.size() / 2;
	vector<int> left(arr.begin(), arr.begin() + mid);
	vector<int> right(arr.begin() + mid, arr.end());
	vector<int> t1 = MergeSort(left);
	vector<int> t2 = MergeSort(right);
	return merge(t1, t2);
}

vector<int> merge(vector<int>& left, vector<int>& right)
{
	vector<int> result(left.size() + right.size());
	for (int index = 0, i = 0, j = 0; index < result.size(); index++)
	{
		if (i >= left.size())
		{
			result[index] = right[j++];
		}
		else if (j >= right.size())
		{
			result[index] = left[i++];
		}
		else if (left[i] > right[j])
		{
			result[index] = right[j++];
		}
		else
		{
			result[index] = left[i++];
		}
	}
	return result;
}

快速排序

算法原理

QuickSort通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法动图

图6 QSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void QuickSort(vector<int>& arr, int start, int end)
{
	if (start < end)
	{
		int pivot = Partition(arr, start, end);
		QuickSort(arr, start, pivot - 1);
		QuickSort(arr, pivot + 1, end);
	}
}

int Partition(vector<int>& arr, int start, int end)
{
	int pivot = arr[start];
	while (start < end)
	{
		while (start < end && arr[end] > pivot)
		{
			end--;
		}
		if (start < end)
		{
			arr[start] = arr[end];
			start++;
		}
		while (start < end && arr[start] < pivot)
		{
			start++;
		}
		if (start < end)
		{
			arr[end] = arr[start];
			end--;
		}

	}
	arr[start] = pivot;
	return start;
}

堆排序

算法原理

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

算法动图

图7 HeapSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int len{};

void HeapSort(vector<int>& arr)
{
	len = arr.size();
	if (len < 1)
	{
		return;
	}
	buildMaxHeap(arr);
	while (len > 0)
	{
		swap(arr, 0, len - 1);
		len--;
		adjustHeap(arr, 0);
	}
}


void buildMaxHeap(vector<int>& arr)
{
	for (int i = (len - 1) / 2; i >= 0; i--)
	{
		adjustHeap(arr, i);
	}
}

void adjustHeap(vector<int>& arr, int i)
{
	int maxIndex = i;
	if ((i * 2) < len && arr[i * 2] > arr[maxIndex])
	{
		maxIndex = i * 2;
	}
	if ((i * 2 + 1) < len && arr[i * 2 + 1] > arr[maxIndex])
	{
		maxIndex = i * 2 + 1;
	}
	if (maxIndex != i)
	{
		swap(arr, maxIndex, i);
		adjustHeap(arr, maxIndex);
	}
}

void swap(vector<int>& arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
注意：堆排序中要用一个全局变量来维护序列的长度。

计数排序

算法原理

CountingSort的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

算法动图

图8 CountingSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void CountingSort(vector<int>& arr)
{
	if (arr.empty())
	{
		return;
	}
	int bias{}, min = arr[0], max = arr[0];
	for (int i = 1; i < arr.size(); i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	bias = 0 - min;
	vector<int> bucket(max - min + 1, 0);
	for (int i = 0; i < arr.size(); i++)
	{
		bucket[arr[i] + bias]++;
	}
	int index = 0, i = 0;
	while (index < arr.size())
	{
		if (bucket[i] != 0)
		{
			arr[index] = i - bias;
			bucket[i]--;
			index++;
		}
		else
		{
			i++;
		}
	}
}

桶排序

算法原理

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

算法图示

图9 BucketSort

C++源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void BucketSort(vector<int>& arr, int bucketSize)
{
	int len = arr.size();
	if (len <= 1)
	{
		return;
	}
		
	int min = arr[0], max = min;
	for (int i = 1; i<len; ++i)
	{
		if (min > arr[i])
		{
			min = arr[i];
		}
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	int k = bucketSize;
	int bucketsNum = (max - min) / k + 1;
	vector<list<int>> buckets(bucketsNum);
	for (int i = 0; i<len; ++i)
	{
		int value = arr[i];
		insert(buckets[(value - min) / k], value);
	}
	int index = 0;
	for (int i = 0; i<bucketsNum; ++i)
	{
		if (buckets[i].size())
		{
			for (auto& value : buckets[i])
			{
				arr[index++] = value;
			}
				
		}
	}
}

基数排序

算法原理

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法动图

图10 RadixSort

C++源码