hello算法之排序

创建时间: 2026-06-13 10:59:56

排序算法

评价维度

  • 运行效率:我们期望排序算法的时间复杂度尽量低,且总操作数量较小。
  • 就地性:顾名思义,原地排序通过这原数组上直接操作实现排序,无需借助额外的辅助数组,从而节省内存。
  • 稳定性:稳定排序在完成排序后,相等元素在数组中的相对顺序不发生改变。
  • 自适应性:自适应排序能够利用输入数据已有的排序信息来减少计算量,达到最优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。
  • 是否基于比较:基于比较多排序依赖比较运算符J(<、=、>)来判断元素的相对顺序,从而排序整个数组,理论最优时间复杂度为O(n log n)。而非比较排序不使用比较运算符,时间复杂度可达O(n),但其通用性相对较差。

1. 选择排序

选择排序(selection sort)的工作原理非常简单: 开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序区间的末尾。

设数组的长度为n,选择排序的算法流程如下所示。

  1. 初始状态下,所有元素未排序,区间索引为[0, n-1]。
  2. 选取区间[0, n-1]中最小元素,将其与索引0处的元素交换。完成后,数组前1个元素已排序。
  3. 选取区间[1, n-1]中最小的元素,将其与索引1处的元素交换。完成后,数组前2个元素已排序。
  4. 以此类推。经过n-1轮选择与交换后,数组前n-1个元素完成排序。
  5. 仅剩的一个元素必定是最大元素,无需排序,因此数组排序完成。
void selectionSort(vector<int> &nums) {
	int n = nums.size();
	for(int i = 0; i < n - 1; i++) {
		int k = i;
		for(int j = i + 1; j < n; j++) {
			if(nums[j] < nums[k])
				k = j;
		}
		swap(nums[i], nums[k]);
	}
}

特性

  • 时间复杂度为O(n^2)、非自适应。
  • 空间复杂度为O(1)、原地排序。
  • 非稳定性、有可能会打乱原有的顺序。如下所示。
1 4 3 4 5 2
 \    /
  \  /
   \/
   /\
 / 	 \
4 4 3 1 5 2

2. 选择排序

冒泡排序(bubble sort) 通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样,因此得名冒泡排序。冒泡排序过程利用元素交换操作来实现:从数组最左端开始向右遍历,依次比较相邻元素大小,如果“左元素>右元素”就交换两者。遍历完成后,最大的元素会被移动到数组的最右端。

算法流程

  1. 首先,对n个元素执行“冒泡”,将数组最大的元素交换到正确的位置。
  2. 接下来,对剩余n-1个元素执行“冒泡”,将第二大元素交换到正确的位置。
  3. 以此类推,经过n-1轮“冒泡”后,前n-1大的元素都被交换到了正确的位置。
  4. 仅剩的一个元素必定是最小元素,无需排序,因此数组排序完成。
void bubbleSort(vector<int> &nums) {
	for(int i = nums.size() - 1; i > 0; i--) {
		for(int j = 0; j < i; j++) {
			if(nums[j] > nums[j+1]){
				swap(nums[j], nums[j+1]);
			}
		}
	}
}

效率优化

我们发现,如果某轮“冒泡”中没有执行任何操作,说明数组的排序已经完成,可以直接返回结果,因此,我们可以增加一个标志位flag来检测这种情况。

void bubbleSortWithFlag(vector<int> &nums) {
	for(int i = nums.size() - 1; i > 0; i--) {
		bool flag = false;
		for(int j = 0; j < i; j++) {
			if(nums[j] > nums[j+1]) {
				swap(nums[j], nums[j+1]);
				flag = true;
			}
		}
		if(!flag)
			break;
	}
}

算法特性

  • 时间复杂度为O(n^2)、自适应排序。
  • 空间复杂度为O(1)、原地排序。
  • 稳定排序。

3.插入排序

插入排序(insertion sort)是一种简单的排序算法,它的原理类似于手动整理一副牌的过程。

具体来说,插入排序就是在未排序区间选择一个基准元素,将元素与左侧已排序区间的元素逐一比较大小,并将该元素插入到正确的位置。

算法流程

  1. 初始状态下,数组的第1个元素已完成排序。
  2. 选取数组的第二个元素作为base,将其插入到正确的位置后,数组的前两个元素已经排序。
  3. 选取第三个元素作为base,将其插入到正确的位置后,数组的前3个元素已排序。
  4. 以此类推,在最后一轮中,选取最后一个元素作为base,将其插入到正确位置后,所有元素均已排序。
void insertionSort(vector<int> &nums) {
	for(int i = 1; i < nums.size(); i++) {
		int base = nums[i], j = i - 1;
		for(;j >= 0 && nums[j] > base; j--){
			nums[j+1] = nums[j];
		}
		nums[j+1] = base;
	}
}

算法特性

  • 时间复杂度为O(n^2)、自适应排序。
  • 空间复杂度为O(1)、原地排序。
  • 稳定排序。

4.快速排序

快速排序(quick sort)是一种基于分治策略的排序算法,运行高效,应用广泛。

快速排序的核心就是“哨兵划分”选择一个基数作为哨兵,将大于基数的挪动到右侧,小于基数的挪动到左侧。

  1. 选取数组最左端元素作为基数,初始化将个指针i和j分别指向数组的两端。
  2. 设置一个循环,每轮中使用i(j)分别寻找第一个比基数大(小)的元素,然后交换这两个元素。
  3. 循环执行步骤2.,直到i和j相遇时停止,最后将基准数交换至两个子数组的分界线。

上述步骤完成后,原数组被划分成三个部分:左子树组、基准数、右子数组,且满足“左子数任意元素<=基准数<=右子数任意元素”。因此,我们接下来只需要对这两个子数组进行排序。

/* 哨兵划分 */
int partition(vector<int> &nums, int left, int right) {
	int i = left, j = right;
	for(;i<j;) {
		for(;i<j && nums[j]>=nums[left];j--);
		for(;i<j && nums[j]<=nums[left];i++);
		swap(nums[i], nums[j]);
	}
	swap(nums[i], nums[left]);
	return i;
}

算法流程

  1. 首先,对原数组执行一次“哨兵划分”,得到末排序的左子数组和右子数组。
  2. 然后,对左子数组和右子数组分别递归执行“哨兵划分”。
  3. 持续递归,直至子数组长度为1时终止,从而完成整个数组的排序。
void quickSort(vector<int> &nums, int left, int right) {
	if(left >= right)
		return;
	int pivot = partition(nums, left, right);
	quickSort(nums, left, pivot - 1);
	quickSort(nums, pivot + 1, right);
}

算法特性

  • 时间复杂度为O(nlogn)、非自适应排序
  • 空间复杂度为O(n)、原地排序
  • 非稳定排序

为什么快速排序那么快

从名字可以看出,快速排序中效率上肯定有优势,虽然快速排序的时间复杂度可能和归并排序和堆排序相同,但是通常快速排序的效率更高,具有以下原因。

  • 出现最差情况的概率很低:虽然快速排序的最差时间复杂度为O(n^2),没有归并排序稳定,但在绝大多数情况下,快速排序能在O(nlogn)的时间复杂度下运行。
  • 缓存使用效率高:在执行哨兵划分操作时,系统可用整个子数组加载到缓存,因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素,从而缺乏这一特性。
  • 复杂度的常数系数小:在这三种算法中,快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

基数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子,假设输入数组是完全倒序的,由于我们选择最左端元素作为基数,那么哨兵划分完成后,基数被交换至数组最右端,导致左子数组长度为n-1、右子数组长度为0。如此递归下去,每轮哨兵划分后都有一个子数组的长度为0,分治策略失效,快速排序退化为“冒泡排序”的近似形式。

为了避免这种情况发生,我们可以优化哨兵划分中的基准数的选取策略,例如,我们可以随机选取一个元素作为基准数。然而,如果运气不佳,每次都选到不理想的基准数,效率仍然不尽人意。

编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例,那么快速排序的效率仍然可能劣化。

为了进一步改进,我们可以在数组中选取三个候选元素(通常为数组的首、尾、中点元素),并将这三个候选元素的中位数作为基准数。这样一来,基准数“不大不小”的概率将大幅提升。当然,我们可以选取更多的候选元素,进一步提升算法的稳健性。采用这种方法后,时间复杂度劣化至O(n^2)的概率大大降低。

int mediaThree(vector<int> &nums, int left, int mid, int right){
	int l = nums[left], m = nums[mid], r = nums[right];
	if((l <= m && m <= r) || (r <=m && m <= l))
		return mid;
	if((m <= l && l <= r) || (r <= l && l <= m))
		return left;
	return right;
}

int partition(vector<int> &nums, int left, int right) {
	int med = mediaThree(nums, left, (left + right) / 2, right);
	swap(nums[left], nums[med]);
	int i = left, j = right;
	for(;i < j;) {
		for(;j < j && nums[j] >= nums[left];)
			j--;
		for(;i < j && nums[i] <= nums[left];)
			i++;
		swap(nums[i], nums[j]);
	}
	swap(nums[i], nums[left]);
	return i;
}

递归深度优化

在某些输入下,快速排序可能占用空间较多,以完全有序的输入数组为例,设递归中的子数组长度为m,每轮哨兵划分操作都将产生长度为0的左子数组和长度为m-1的右子数组,这意味着每一层递归调用减少的问题规模非常小(只减少一个元素),递归树的高度会达到n-1,此时需要占用O(n)大小的栈帧空间。

为了防止栈帧空间的积累,我们可以每轮哨兵排序完成后,比较两个子数组的长度,仅对较短的子数组进行递归。由于较短子数组的长度不会超过n/2,因此这种方法能确保递归深度不超过log n,从而将最差空间复杂度优化至O(log n)。

void quickSort(vector<int> &nums, int left, int right) {
	for(;left < right;) {
		int pivot = partition(nums, left, right);
		// 对两个子数组中较短的那个执行快速排序
		if(pivot - left < right - pivot) {
			quickSort(nums, left, pivot - 1);
			left = pivot + 1;
		} else {
			quickSort(nums, pivot + 1, right);
			right = pivot - 1;
		}
	}
}

5.归并排序

归并排序(merge sort)是一种基于分治策略的排序算法,包含“划分”和“合并”阶段

  1. 划分阶段:通过递归不断地将数组从中点处分开,将长数组的排序问题转换为短数组的排序问题。
  2. 合并阶段:当子数组长度为1时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束。

算法流程

划分阶段:从顶至底递归地将数组从中点切分为两个子数组。

  1. 计算数组中点mid,递归划分左子数组(区间[left, mid])和右子数组(区间[mid+1, right])。
  2. 递归执行步骤1,直至子数组长度为1时终止。

合并阶段:从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是,从长度为1的子数组开始合并,合并阶段中的每个子数组都是有序的。

归并排序与二叉树后遍历的递归顺序是一致的。

  • 后序遍历:先递归左子树,再递归右子树,最后处理根节点。
  • 归并排序:先递归左子树,再递归右子树,最后处理合并。
void merge(vector<int> &nums, int left, int mid, int right) {
	vector<int> tmp(right - left + 1);
	int i = left, j = mid + 1, k = 0;

	for(;i <= mid && j <= right;){
		if(nums[i] <= nums[j])
			tmp[k++] = nums[i++];
		else
			tmp[k++] = nums[j++];
	}

	for(;i <= mid;){
		tmp[k++] = nums[i++];
	}
	for(;j <= right;) {
		tmp[k++] = nums[j++];
	}

	for(k = 0; k < tmp.size(); k++) {
		nums[left + k] = tmp[k];
	}
}

void mergeSort(vector<int> &nums, int left, int right) {
	if(left >= right)
		return;
	int mid = left + (right - left) / 2;
	mergeSort(nums, left, mid);
	mergeSort(nums, mid + 1, right);
	merge(nums, left, mid , right);
}

算法特性

  • 时间复杂度为O(n log n)、非自适应排序
  • 空间复杂度为O(n)、非原地排序
  • 稳定排序

6.堆排序

堆排序(heap sort)是一种基于堆数据结构的高效排序算法。可以利用建堆操作和元素出堆操作实现堆排序。

  1. 输入数组并建立小顶堆,此时最小元素位于堆顶。
  2. 不断执行出堆操作,依次记录出堆元素,即可得到从小到大的排序的序列

算法流程

设数组长度为n,堆排序流程如下:

  1. 输入数组并建立大顶堆。完成后,最大的元素位于堆顶。
  2. 将堆顶元素(第一个元素)与堆底元素(最后一个元素)交换,完成后,堆长度减1,已排序元素加1。
  3. 从堆顶元素开始,从顶到底执行堆化操作(sift down)。完成堆化后,堆的性质得到修复。
  4. 循环执行上述的第二、第三步。循环n-1轮后,即可完成数组排序。
void siftDown(vector<int> &nums, int n, int i) {
	for(;;) {
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		int ma = i;
		if(l < n && nums[l] > nums[ma]){
			ma = l;
		}
		if(r < n && nums[r] > nums[ma]){
			ma = r;
		}
		if(ma == i){
			break;
		}
		swap(nums[i], nums[ma]);
		i = ma;
	}
}

void heapSort(vector<int> &nums) {
	for(int i = nums.size() / 2 - 1; i >= 0; --i){
		siftDown(nums, nums.size(), i);
	}

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

算法特性

  • 时间复杂度O(nlog n)、非自适应排序。
  • 空间复杂度O(1)、原地排序。
  • 非稳定排序。

7.桶排序

前面几种排序算法都属于比较排序算法,它们通过比较元素间的大小来实现排序。此类算法时间复杂度无法超越O(nlogn)。下面将探讨几种非比较排序算法,它们的时间复杂度可以达到线性阶。

桶排序(bucket sort)是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中,然后在每个桶内部分别执行排序,最终按照桶的顺序将所有数据合并。

算法流程

考虑一个长度为n的数组,其元素是范围[0,1)内的浮点数。桶排序的流程如下。

  1. 初始化k个桶,将n个元素分配到k个桶中。
  2. 对每个桶分别执行排序。
  3. 按照桶从小到大的排序合并结果。
void bucketSort(vector<float> &nums) {
	int k = nums.size() / 2;
	vector<vector<float>> buckets(k);
	for (float num : nums) {
		int i = num * k;
		buckets[i].push_back(num);
	}
	for(vector<float> &bucket : buckets) {
		sort(bucket.begin(), bucket.end());
	}
	int i = 0;
	for(vector<float> &bucket : buckets) {
		for(float num : bucket) {
			nums[i++] = num;
		}
	}
}

算法特性

桶排序适用于处理体量很大的数据。例如,输入数据包含100万个元素,由于空间限制,系统内存无法一次性加载所有数据。此时,我们可以将数据分成1000个桶,然后分别对每个桶进行排序,最后将结果合并。

  • 时间复杂度O(n+k)。
  • 空间复杂度为O(n+k)、非原地排序。

计数排序

计数排序(counting sort)通过统计元素的数量来实现排序,通常应用于整个数组。

简单实现

给定一个长度为n的数组nums,其中的元素都是“非负整数”,计数排序的整体流程如下:

  1. 遍历数组,找出其中最大的数字,记为m,然后创建一个长度为m + 1的辅助数组counter。
  2. 借助counter统计nums中各数字的出现次数,其中counter[num]对应数字num出现的次数。统计方法很简单,只需要遍历nums,每次循环counter[num] = counter[num]+1就可以了。
  3. 由于counter的各个索引天然有序,因此相当于所有数字已经排序好了。接下来,我们遍历counter,根据各数字出现的次数从小到大的顺序填入nums即可。
void countingSortNative(vector<int> &nums) {
	int m = 0;
	for (int num : nums){
		m = max(m, num);
	}

	vector<int> counter(m + 1, 0);
	for(int num : nums) {
		counter[num]++;
	}
	int i = 0;
	for(int num = 0; num < m + 1; num++) {
		for(int j = 0; j < counter[num]; j++, i++) {
			nums[i] = num;
		}
	}
}

完整实现

上面的简单实现会有一个问题,就是当输入数据是一个对象时,简单例子就失效了。假设输入对象是一个商品对象,我们想按照商品价格(类的成员变量)对商品进行排序,而上述算法只能给出价格的排序结果。

那么如何才能获得原始数据的排列结果呢?我们首先计算counter的“前缀和”。顾名思义,索引i处的前缀和prefix[i]等于数组前i个元素和:

前缀和具体明确的意义,prefix[num]-1代表元素num在结果数组res中最后一次出现的索引。这个信息非常关键,因为它告诉我们各个元素应该出现在结果数组的那个位置。接下来,我们倒叙遍历原数组nums的每个元素num,在每轮迭代中执行以下两步。

  1. 将num填入数组res的索引prefix[num] - 1处
  2. 令前缀和prefix[num]减小1,从而得到下次放置num的索引。

遍历完成后,数组res中就是排序好的结果,最后使用res覆盖原数组nums即可。

void countingSort(vector<int> &nums) {
	int m = 0;
	for(int num : nums) {
		m = max(m, num);
	}

	vector<int> counter(m + 1, 0);
	for(int num : nums) {
		counter[num]++;
	}
	for(int i = 0; i < m; i++) {
		counter[i+1] += counter[i];
	}
	int n = nums.size();
	vector<int> res(n);
	for(int i = n - 1; i >= 0; i--) {
		int num = nums[i];
		res[counter[num]-1] = num;
		counter[num]--;
	}
	nums = res;
}

算法特性

  • 时间复杂度O(n+m)、非自适应排序。
  • 空间复杂度为O(n+m)、非原地排序。
  • 稳定排序。

基数排序

前面介绍了计数排序,它适用于数据量n较大但数据范围m较小的情况。假设现在我们需要对n=10^6个学号进行排序,而学号是一个8位数字,这意味着数据范围m=10^8非常大,使用计数排序时需要分配大量的内存空间,而基数排序可以避免这种情况。

基数排序(radix sort)的核心思想与计数排序一致,也通过统计个数来实现排序。在此基础上,基数排序利用数字之间的递进关系,依次对每一位进行排序,从而得到最终的排序结果。

算法流程

以学号为例,假设数字的最低位是1位,最高位是第8位,基数排序流程如下:

  1. 初始化位数k=1。
  2. 对学号的第k位进行“计数排序”。完成后,数据会根据第k位从小到大排序。
  3. 将k增加1,然后返回步骤2继续迭代,直到所有位都排序完成后结束。
int digit(int num, int exp) {
	return (num / exp) % 10;
}

void countingSortDigit(vector<int> &nums, int exp) {
	vector<int> counter(10, 0);
	int n = nums.size();
	for(int i = 0; i < n; i++) {
		int d = digit(nums[i], exp);
		counter[d]++;
	}

	vector<int> res(n, 0);
	for(int i = n - 1; i >= 0; i--) {
		int d = digit(nums[i], exp);
		int j = counter[d] - 1;
		res[j] = nums[i];
		counter[d]--;
	}
	for(int i = 0; i < n; i++)
		nums[i] = res[i];
}

void radixSort(vector<int> &nums) {
	int m = *max_element(nums.begin(), nums.end());
	for(int exp = 1; exp <= m; exp *= 10)
		countingSortDigit(nums, exp);
}

算法特性

相较于计数排序,基数排序适用于排序数值较大的情况,但是数据必须可以表示为固定位数的格式,且位数不能过大。

  • 时间复杂度为O(nk)、非自适应排序。
  • 空间复杂度为O(n+d)、非原地排序。
  • 稳定排序。