排序算法总结

发表于 | 更新于

算法分类

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

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

图1

算法复杂度

排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
插入排序 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\) 稳定
希尔排序 \(O(n^{1.3})\) \(O(n^2)\) \(O(n)\) \(O(1)\) 不稳定
选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定
堆排序 \(O(nlogn)\) \(O(nlogn)\) \(O(nlogn)\) \(O(1)\) 不稳定
冒泡排序 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\) 稳定
快速排序 \(O(nlogn)\) \(O(n^2)\) \(O(nlogn)\) \(O(nlogn)\) 不稳定
归并排序 \(O(nlogn)\) \(O(nlogn)\) \(O(nlogn)\) \(O(n)\) 稳定
计数排序 \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) 稳定
桶排序 \(O(n+k)\) \(O(n^2)\) \(O(n)\) \(O(n+k)\) 稳定
基数排序 \(O(nlog(r)m)\) \(O(nlog(r)m)\) \(O(nlog(r)m)\) \(O(n+m)\) 稳定

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

七个常用排序算法

冒泡排序

冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
void bubbleSort(vector<int> &arr) {
	int n = arr.size();
	bool flag = false;
	for (int i = 0; i < n - 1; i++) {
		flag = true;
		for (int j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				flag = false;
			}
		}
		if (flag) break;
	}
}

选择排序

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
void selectionSort(vector<int> &arr) {
	int n = arr.size();
	int minIndex;
	for (int i = 0; i < n - 1; i++) {
		minIndex = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		if (minIndex != i) {
			swap(arr[i], arr[minIndex]);
		}
	}
}

插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(vector<int> &arr) {
	int n = arr.size();
	for (int i = 1; i < n; i++) {
		int cur = arr[i];
		int preIndex = i - 1;
		while (preIndex >= 0 && arr[preIndex] > cur) {
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = cur;
	}
}

归并排序

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

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
vector<int> merge(const vector<int> &left, const vector<int> &right) {
	vector<int> res;
	int i = 0, j = 0;
	while (i < left.size() && j < right.size()) {
		if (left[i] < right[j]) {
			res.push_back(left[i++]);
		}
		else {
			res.push_back(right[j++]);
		}
	}
	while (i < left.size()) {
		res.push_back(left[i++]);
	}
	while (j < right.size()) {
		res.push_back(right[j++]);
	}
	return res;
}
void mergeSort(vector<int> &arr) {
	int n = arr.size();
	if (n < 2) return;
	int mid = n / 2;
	vector<int> left(vector<int>(arr.begin(), arr.begin() + mid));
	vector<int> right(vector<int>(arr.begin() + mid, arr.end()));
	mergeSort(left);
	mergeSort(right);
	arr = merge(left, right);
}

快速排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int partition(vector<int> &arr, int left, int right) {
	int pivot = left;
	int index = pivot + 1;
	for (int i = index; i <= right; i++) {
		if (arr[i] < arr[pivot]) {
			swap(arr[i], arr[index]);
			index++;
		}
	}
	swap(arr[pivot], arr[index - 1]);
	return index - 1;
}
void quickSort(vector<int> &arr, int left, int right) {
	int n = arr.size();
	if (left < right) {
		int partitionIndex = partition(arr, left, right);
		quickSort(arr, left, partitionIndex - 1);
		quickSort(arr, partitionIndex + 1, right);
	}
}

堆排序

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

在堆排序中，主要有以下几个操作：

  • 创建最大堆：将堆中的所有数据重新排序，使其满足最大堆的性质
  • 堆排序：移除位于第一个根节点的数据，并做最大堆调整的递归运算
  • 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
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
void heapify(vector<int> &arr, int len, int index) {
	int left = index * 2 + 1;
	int right = index * 2 + 2;
	int lagest = index;
	if (left<len&&arr[left]>arr[lagest]) {
		lagest = left;
	}
	if (right<len&&arr[right]>arr[lagest]) {
		lagest = right;
	}
	if (lagest != index) {
		swap(arr[lagest], arr[index]);
		heapify(arr, len, lagest);
	}
}
void buildMaxHeap(vector<int> &arr) {
	int n = arr.size();
	for (int i = n / 2; i >= 0; i--) {
		heapify(arr, n, i);
	}
}
void heapSort(vector<int> &arr) {
	int n = arr.size();
	buildMaxHeap(arr);
	for (int i = n - 1; i > 0; i--) {
		swap(arr[i], arr[0]);
		heapify(arr, i, 0);
	}
}

基数排序

基数排序属于“分配式排序”，又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void radixSort(vector<int> &arr, int maxDigit) {
	int n = arr.size();
	vector<vector<int>> buckets(10, vector<int>());
	for (int i = 0; i <= maxDigit; i++) {
		for (int j = 0; j < n; j++) {
			int index = arr[j] / (i + 1) % 10;
			buckets[index].push_back(arr[j]);
		}
		arr.clear();
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < buckets[j].size(); k++) {
				arr.push_back(buckets[j][k]);
			}
		}
		buckets = vector<vector<int>>(10, vector<int>());
	}
}
0%