排序算法回顾

#include 
#include 
#include 
#include 
#include 

using namespace std;
//!< 基本排序算法 插入排序 选择排序 冒泡排序 梳排序（不管他了）

//!< 两层循环 插入排序
vector insertSort(vector data)
{
    int tmp;
    //!< 需要内外两层循环, 外层遍历每一个新位置，内层遍历外层包裹下的每一个点的大小比较操作
    //!< 外层从1 开始, 在内层对 1 和 0 进行比较
    for (int i = 1, j; i < data.size(); i++)
    {
        tmp = data[i];
        for (j = i; j > 0 && data[j - 1] > tmp; j--)
        {
            data[j] = data[j - 1];//!< 依次向后覆盖拷贝，腾出位置给tmp
        }
        data[j] = tmp;
    }
    return data;
}
//!< 选择排序
// 每次迭代中, 找出元素 data[i],..., data[n-1] 中的最小元素，然后将其余 data[i] 交换位置
vector selectSort(vector data){
    //!< 计数 轮数
    // 最后一个元素被剩下就可以了不需要和自己进行比较
    for (size_t i = 0, j, least; i < data.size() - 1; i++) 
    {
        for (j = i + 1, least = i; j < data.size(); j++)//外层, 每一轮都要比较剩下的所有元素 试一试data.size()
        {
            if(data[j] < data[least]){//!< 获取最小元素的索引
                least = j;
            }
        }
        swap(data[i], data[least]);
    }

    return data;
}

//!< 冒泡排序
vector bubbleSort(vector data){
    //!< 跟选择排序一样，外层循环是表示当前的目的停止位置
    for (size_t i = 0; i < data.size() - 1; i++)
    {
        //!< 内层循环 移动到i的位置就停止，i以下的都是已经找到的全剧最小序列
        for (size_t j = data.size() - 1; j > i; --j)
        {
            if(data[j]< data[j - 1])
                swap(data[j], data[j - 1]);
        }
    }
    return data;
}
//!< data { 5, 3, 8, 6, 0, 1, 4, 7};
void quickSort(vector& data, int first, int last)
{
    //!< 1.0 确定 left 和right位置
    int left = first +1;
    int right =  last;

    //!< 2.0 pivot 交换到第一个位置
    swap(data[first], data[(first + right) / 2]);

    int pivot = data[first];
    //!< 3.0 
    while(left <= right){ // = 是为了 让left++ 能退出 while 循环
        while(data[left] < pivot)
            left++;
        while(data[right] > pivot)
            right--;
        if(left < right) //!< case1: 当互补交叉的时候，左右交换，符合快排的思想
            swap(data[left], data[right]);
        else
            left ++;
    }
    //!< case2: left和right重叠或者有越界，将pivot放到right的位置（因为right比pivot小，能够交换位置）
    swap(data[first], data[right]);
    
    //!< 4.0 right已经是分界线了，对其左右子数组 递归
    if(first < right - 1) //此时right已经是pivot了，不需要动
        quickSort(data, first, right - 1);
    if(right + 1 < last)
        quickSort(data, right + 1, last);

}