选择排序与快速排序

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕

C++实现

#include <iostream>
#include <vector>

template<typename T>
void selection_sort(std::vector<T>& arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.size(); j++)
            if (arr[j] < arr[min])
                min = j;
        std::swap(arr[i], arr[min]);
    }
}

int main() {
    std::vector<int> arr1 = {10, 7, 8, 9, 1, 5};
    selection_sort(arr1);
    std::cout << "Sorted array (int): ";
    for (int i = 0; i < arr1.size(); i++)
        std::cout << arr1[i] << " ";
    std::cout << std::endl;

    std::vector<float> arr2 = {3.14, 2.71, 1.618, 0.707, 2.718};
    selection_sort(arr2);
    std::cout << "Sorted array (float): ";
    for (int i = 0; i < arr2.size(); i++)
        std::cout << arr2[i] << " ";
    std::cout << std::endl;

    return 0;
}

• 时间复杂度 O(n^2)，需要遍历每个元素

• 空间复杂度O(1)，不占用额外空间

快速排序

快速排序是一种使用分治策略的排序算法。它选择一个元素作为“枢纽”或“基准”元素，然后将数组分为两个子数组——一个包含所有比基准元素小的元素，另一个包含所有比基准元素大的元素。然后对这两个子数组进行递归地快速排序。

算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）;

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

C++实现：

#include<iostream>
using namespace std;

int Partition(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) {
            --high;
        }
        A[low] = A[high];
        while (low < high && A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivot = Partition(A, low, high);
        QuickSort(A, low, pivot - 1);
        QuickSort(A, pivot + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    QuickSort(arr, 0, n - 1);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

C++11优化随机快排

// 随机快排
class Solution {
private:
    void qSort(vector<int>& nums, int leftBorder, int rightBorder) {
        if(leftBorder >= rightBorder) return;

        // 随机中轴
        int pivot = leftBorder + rand() % (rightBorder - leftBorder + 1);
        swap(nums[pivot], nums[leftBorder]);
        int left = leftBorder, right = rightBorder;
        int pivotNum = nums[leftBorder];

        //普通快排
        while(left < right) {
            while(left < right && nums[right] >= pivotNum) --right;
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivotNum) ++left;
            nums[right] = nums[left];
        }
        nums[left] = pivotNum;

        //下面代码是关键优化，缩小一下中轴范围，针对2，2，2，2，2...这种重复样本有效
        while(left>0 && nums[left] == nums[left-1]) --left;
        while(right< nums.size()-1 && nums[right] == nums[right+1]) ++right;

        //递归缩小范围的左右区域
        qSort(nums, leftBorder,left-1);
        qSort(nums, right+1, rightBorder);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        qSort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
}

时间空间复杂度分析

• 时间复杂度

  对于最好和平均情况，快速排序的时间复杂度是 O(nlogn)。这是因为在这些情况下，每次分区操作，我们可以将数组分为两个近乎相等的部分。这就意味着每次递归调用处理一半的大小。

  但是在最坏情况下（即当给定的数组已经完全排序或者完全逆序排列时），快排的时间复杂度是 O(n^2)。这是因为每次分区操作只能减少数组大小1。

• 空间复杂度

  • 快速排序是原地排序，不需要额外的存储空间，所以空间复杂度为 O(1)。
  • 但是，快速排序是递归的，因此需要考虑递归栈的空间。在最坏的情况下，递归栈的深度为 O(n)。在平均情况下，递归栈的深度为 O(logn)。