hello算法之排序
排序算法
评价维度
- 运行效率:我们期望排序算法的时间复杂度尽量低,且总操作数量较小。
- 就地性:顾名思义,原地排序通过这原数组上直接操作实现排序,无需借助额外的辅助数组,从而节省内存。
- 稳定性:稳定排序在完成排序后,相等元素在数组中的相对顺序不发生改变。
- 自适应性:自适应排序能够利用输入数据已有的排序信息来减少计算量,达到最优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。
- 是否基于比较:基于比较多排序依赖比较运算符J(<、=、>)来判断元素的相对顺序,从而排序整个数组,理论最优时间复杂度为O(n log n)。而非比较排序不使用比较运算符,时间复杂度可达O(n),但其通用性相对较差。
1. 选择排序
选择排序(selection sort)的工作原理非常简单: 开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序区间的末尾。
设数组的长度为n,选择排序的算法流程如下所示。
- 初始状态下,所有元素未排序,区间索引为
[0, n-1]。 - 选取区间
[0, n-1]中最小元素,将其与索引0处的元素交换。完成后,数组前1个元素已排序。 - 选取区间
[1, n-1]中最小的元素,将其与索引1处的元素交换。完成后,数组前2个元素已排序。 - 以此类推。经过n-1轮选择与交换后,数组前n-1个元素完成排序。
- 仅剩的一个元素必定是最大元素,无需排序,因此数组排序完成。
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) 通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样,因此得名冒泡排序。冒泡排序过程利用元素交换操作来实现:从数组最左端开始向右遍历,依次比较相邻元素大小,如果“左元素>右元素”就交换两者。遍历完成后,最大的元素会被移动到数组的最右端。
算法流程
- 首先,对
n个元素执行“冒泡”,将数组最大的元素交换到正确的位置。 - 接下来,对剩余
n-1个元素执行“冒泡”,将第二大元素交换到正确的位置。 - 以此类推,经过
n-1轮“冒泡”后,前n-1大的元素都被交换到了正确的位置。 - 仅剩的一个元素必定是最小元素,无需排序,因此数组排序完成。
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个元素已完成排序。
- 选取数组的第二个元素作为
base,将其插入到正确的位置后,数组的前两个元素已经排序。 - 选取第三个元素作为
base,将其插入到正确的位置后,数组的前3个元素已排序。 - 以此类推,在最后一轮中,选取最后一个元素作为
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)是一种基于分治策略的排序算法,运行高效,应用广泛。
快速排序的核心就是“哨兵划分”选择一个基数作为哨兵,将大于基数的挪动到右侧,小于基数的挪动到左侧。
- 选取数组最左端元素作为基数,初始化将个指针
i和j分别指向数组的两端。 - 设置一个循环,每轮中使用
i(j)分别寻找第一个比基数大(小)的元素,然后交换这两个元素。 - 循环执行步骤
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时终止,从而完成整个数组的排序。
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时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束。
算法流程
划分阶段:从顶至底递归地将数组从中点切分为两个子数组。
- 计算数组中点
mid,递归划分左子数组(区间[left, mid])和右子数组(区间[mid+1, right])。 - 递归执行步骤
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)是一种基于堆数据结构的高效排序算法。可以利用建堆操作和元素出堆操作实现堆排序。
- 输入数组并建立小顶堆,此时最小元素位于堆顶。
- 不断执行出堆操作,依次记录出堆元素,即可得到从小到大的排序的序列
算法流程
设数组长度为n,堆排序流程如下:
- 输入数组并建立大顶堆。完成后,最大的元素位于堆顶。
- 将堆顶元素(第一个元素)与堆底元素(最后一个元素)交换,完成后,堆长度减1,已排序元素加1。
- 从堆顶元素开始,从顶到底执行堆化操作(sift down)。完成堆化后,堆的性质得到修复。
- 循环执行上述的第二、第三步。循环
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)内的浮点数。桶排序的流程如下。
- 初始化k个桶,将n个元素分配到k个桶中。
- 对每个桶分别执行排序。
- 按照桶从小到大的排序合并结果。
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,其中的元素都是“非负整数”,计数排序的整体流程如下:
- 遍历数组,找出其中最大的数字,记为
m,然后创建一个长度为m + 1的辅助数组counter。 - 借助
counter统计nums中各数字的出现次数,其中counter[num]对应数字num出现的次数。统计方法很简单,只需要遍历nums,每次循环counter[num] = counter[num]+1就可以了。 - 由于
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,在每轮迭代中执行以下两步。
- 将num填入数组
res的索引prefix[num] - 1处 - 令前缀和
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位,基数排序流程如下:
- 初始化位数k=1。
- 对学号的第k位进行“计数排序”。完成后,数据会根据第k位从小到大排序。
- 将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)、非原地排序。
- 稳定排序。
