排序总结

发表于 2022-08-16 分类于计算机基础，数据结构阅读次数： Waline：本文字数： 2.4k 阅读时长 ≈ 2 分钟

知识框架：

我们需要重点掌握快速排序，堆排序，归并排序

1. 基本概念：

我们需要让排列表中的数据按关键字有序。例如[1,2,3,4,5]就是有序的。

算法的稳定性：假如排序表中有两个元素a和b，它们的关键字相同，在开始排序之前，a在b之前，排序之后，a还是在b之前，则称为稳定排序，反之，不稳定。

2. 内部排序

2.1 插入排序

2.1.1 直接插入排序

2.1.2 折半插入排序

2.1.3 希尔排序

2.2 交换排序

2.2.1 冒泡排序

2.2.2 快速排序

快速排序的思想是基于分治法的。

基本思想：

在待排序的表L[1...n]中任取一个元素pivot作为基准（通常取首元素），通过一趟排序后将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中的所有元素小于pivot，L[k + 1...n]中所有元素大于等于pivot，则pivot就放在了最终的位置上，这个过程称为一趟快速排序。然后分别递归对两个字表重复上述过程，直到每部分只有一个元素或空为止。

ps: 需要了解一趟和一次的区别

对此，我们可以得出一个结论，每趟快速排序都可以最小确定一个元素的位置。

算法流程：

指针j从high往前搜，直到找到第一个小于基准pivot = 49的数27，将27交换到i所指的位置。

指针i从low往后搜，直到找到第一个大于基准pivot = 49的数65，将65交换到j所指的位置。

指针j从high往前搜，直到找到第一个小于基准pivot = 49的数13，将13交换到i所指的位置。

指针i从low往后搜，直到找到第一个大于基准pivot = 49的数97，将97交换到j所指的位置。

指针j继续往前搜索小于基准pivot的元素，直到i == j

这时候我们的第一趟排序也就完成了。

然后我们递归以上过程，即可得到最终的答案。

希望不理解的可以手动模拟多遍。

总结：

从后往前寻找比基准小的元素，然后和i交换
从前往后寻找比基准大的元素，然后和j交换
知道i==j我们停止继续搜索
递归以上过程

时间和空间复杂度：

空间效率：由于快速排序是递归的，需要借用栈来辅助，其容量应与递归调用的最大深度一样，最好情况下为O(logN)，最坏情况下，需要进行n-1次递归，所以栈的深度为O(N)，平均情况下，栈的深度为O(logN)。

时间效率： 快速排序的运行时间与划分是否对称有关，最坏情况发生在两个区域分别包含n-1和0个元素时，即程序基本有序或基本逆序，得到的最坏时间复杂度为O(n^2)。理想情况下，左右两个子列表都不大于n/2，时间复杂度为O(nlogn)

稳定性：是不稳定的。例如给{3,2,2}，经过一趟排序后{2,2,3}，可以发现2的相对次序已经发生了改变，所以是不稳定的。

快速排序是所有内部排序算法中平均性能最优的排序算法

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

//划分
int partition(vi& nums, int lo, int hi){
    //基准
    int pivot = nums[lo];
    while(lo < hi){
        //从后往前找到第一个小于pivot的元素
        while(lo < hi && nums[hi] >= pivot) hi--;
        swap(nums[lo], nums[hi]);
        //从前往后找到第一个大于pivot的元素
        while(lo < hi && nums[lo] <= pivot) lo++;
        swap(nums[lo], nums[hi]);
    }
    return lo;
}

void quickSort(vi& nums, int lo, int hi){
    if(lo < hi){
        //划分操作，找到基准pivot 的位置
        int pivotPos = partition(nums, lo, hi);
        quickSort(nums, lo, pivotPos);
        quickSort(nums, pivotPos + 1, hi);
    }
}

int main(){
    vi nums = {49,38,65,97,76,13,27,49};
    int lo = 0, hi = nums.size() - 1;
    quickSort(nums, lo, hi);
    for(int i = 0; i <= hi; i++){
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}