Sort

Sorting(排序)

排序是指将一组数据按照一定的顺序排列的过程。排序算法是计算机科学中最基础的算法之一，它是对数据进行排列、整理的一种有效的方法。排序算法可以分为内部排序和外部排序。

Bogo sort(猴子排序)

Bogo sort(猴子排序)是一种非常简单的排序算法，它不断随机打乱数组，直到数组排序完成。它的平均时间复杂度为 O(n!), 最坏情况时间复杂度为 O(∞)。

这种排序过于随机, 所以很少有人使用它。

其代码也是十分的简单

c++

void bogoSort(Vector<int>& v){
    while (!isSorted(v)){
        shuffle(v)
    }
}

bool isSorted(Vector<int>& v)
{
    for (int i = 0; i < v.size() - 1; i ++)
    {
        if(v[i] >v[i+1]){
            return false;
        }
    }
    return true;
}

Selection sort(选择排序)

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序的平均时间复杂度为 O(n^2), 最坏情况时间复杂度为 O(n^2)。

c++

void selectionSort(Vector<int>& v){
    for (int i = 0; i < v.size() - 1; i ++)
    {
        int minIndex = i;
        for (int j = i + 1; j < v.size(); j ++)
        {
            if (v[j] < v[minIndex])
            {
                minIndex = j;
            }
        swap(v[i], v[minIndex]);
        }
    }
}

Insertion sort(插入排序)

插入排序(Insertion sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的平均时间复杂度为 O(n^2), 最坏情况时间复杂度为 O(n^2)。

c++

void insertionSort(Vector<int>& v){
    for (int i = 1; i < v.size(); i ++)
    {
        int j = i - 1;
        int temp = v[i];
        while (j >= 0 && v[j] > temp)
        {
            v[j + 1] = v[j];
            j --;
        }
        v[j + 1] = temp;
    }
}

Merge sort(归并排序)

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序的平均时间复杂度为 O(nlogn), 最坏情况时间复杂度为 O(nlogn)。

c++

void mergeSort(Vector<int>& v){
    if (v.size() <= 1)   // 基线条件
        return;
    int mid = v.size() / 2;
    Vector<int> left(v.begin(), v.begin() + mid);
    Vector<int> right(v.begin() + mid, v.end());
    mergeSort(left);
    mergeSort(right);
    merge(left, right, v);
}

void merge(Vector<int>& v, const Vector<int>& left, const Vector<int>& right) {
    int i = 0;  // 原数组 v 的索引
    int i1 = 0; // 左半部分 left 的索引
    int i2 = 0; // 右半部分 right 的索引

    // 遍历合并到原数组 v
    while (i < v.size()) {
        // 选择较小的元素：若右半部分已用完，或左半部分元素更小且未用完
        if (i2 >= right.size() || (i1 < left.size() && left[i1] < right[i2])) {
            v[i] = left[i1];
            i1++;
        } else {
            v[i] = right[i2];
            i2++;
        }
        i++;
    }
}

另外一点,归并排序的很大优势在于它可以多线程并行处理, 因此在某些情况下, 归并排序的效率要比其他排序算法更高。比如在大型计算机上

总结

好了,到目前为止 CS06B 数据结构与算法的排序部分就介绍完了,希望大家能有所收获.

关于后面两节课是介绍继承和多态,如果有兴趣可以去看笔记前面的 C++.oop 教学

最后,感谢大家的阅读,希望大家能有所收获.

Sort ​

Sorting(排序) ​

Bogo sort(猴子排序) ​

Selection sort(选择排序) ​

Insertion sort(插入排序) ​

Merge sort(归并排序) ​

总结 ​