PS:页面右边有该文章的目录，可快捷跳转到对应位置
目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。

1.冒泡排序

1.1 算法介绍

• 时间复杂度(平均) O(n²)
• 时间复杂度(最好) O(n)
• 时间复杂度(最坏) O(n²)
• 空间复杂度 O(1)

这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法)

1.2 代码实现

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 1; j < n - i; ++j) {
            if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]);
        }
    }
}

1.3 GIF原理图

2.插入排序

2.1 算法介绍

• 时间复杂度(平均) O(n²)
• 时间复杂度(最好) O(n)
• 时间复杂度(最坏) O(n²)
• 空间复杂度 O(1)

2.2 代码实现

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

2.3 GIF原理图

3.快速排序

3.1 算法介绍

• 时间复杂度(平均) O(nlogn)
• 时间复杂度(最好) O(nlogn)
• 时间复杂度(最坏) O(n²)
• 空间复杂度 O(nlogn)

快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。
复杂度分析:
最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2)
平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn)

3.2 代码实现

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

3.3 GIF原理图

没找到合适的动图，排序过程请看算法介绍

4. C++ STL里的排序

C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 <algorithm>

传入参数:

4.1 对数组进行升序排序

sort默认排序顺序是升序

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[10] = {1,5,9,8,7,5,3,2,6,4};
    sort(a, a+10);
    for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9
    return 0;
}

4.2 对数组进行降序排序

这时候就需要自定义比较函数

bool compare(int a, int b) {
    return a > b;
}

然后再排序

sort(a, a+10, compare);

4.3 对结构体数组进行排序

同理自定义排序函数可以让我们对结构体进行排序

bool compare(struct aaa A, struct aaa B) {
    if (A.a == B.a) return A.b > B.b; 
    return A.a > B.a;
}

然后再进行排序

sort(aaa, aaa+10, compare);

猫猫说