# 概述

# 稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 $R$ 和 $S$ ，且在原本的列表中 $R$ 出现在 $S$ 之前，在排序过的列表中 $R$ 也将会是在 $S$ 之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序、希尔排序不是稳定排序。

该部分内容来自算法导论。

快速排序是基于归并的原地排序算法，期望时间复杂度 $O(n \log n)$ , 最坏时间复杂度 $O(n^2)$ . 空间复杂度 $O(1)$ .

核心代码如下：

quickSort

	// 最初调用 quickSort (A, 0, A_len-1);
	void quickSort(int* A, int p , int r) {
	if (p<r) {
	q = partition(A, p, r);
	quickSort(A, p, q-1);
	quickSort(A, q+1, r);
	}
	}

	// 对子数组 A [p..r] 就地重排
	int partition(int *A, int p, int r) {
	int x = A[r];
	int i = p-1;
	for (int j=p;j<r;j++) {

	}
	}

LeetCode: 数组中的第 K 个最大元素

参考算法导论 9.2 以期望线性时间做选择。

	void randomizedSelect(int A[], int p, int r, int i) {
	if (p == r) return A[p];
	q - RANOOMIZED-PARTITION(A, p, r )
	k 畸·- q - p -1-1
	if i = k I> the pivot value is the answer
	then ret■rn A[q]？也if i< k
	then retorn RANOOMIZED-SELECT(A, p, q - I, i)
	dse return RANOOMIZED-SELECT(A, q + l. r , i-k)
	}