几种常见的排序方法

1、冒泡排序法
冒泡排序法的思想是将相邻的两个数进行比较，最终的目的是将数组中的最大/最小数放到最后一位，然后以此类推。

/*l相邻两个数比较，直到将最小的一个放末尾*/
void Solution::maopao(std::vector<int>& arrs)
{
    int length = arrs.size();
    for (int i = 0; i < length -1 ; i ++)
    {
        for (int j = 0; j < length - i -1; j ++)
        {
            if (arrs[j] < arrs[j+1])
            {
                int temp = arrs[j +1];
                arrs[j + 1] = arrs[j];
                arrs[j] = temp;
            }
        }
    }
}

2、选择排序法
选择排序法是寻找数组中的最小值，然后放到数组第一个，下次循环是依次排放。

void choice(std::vector<int>& arrs)
{
    int length = arrs.size();
    for (int i = 0; i< length; i++)
    {
        int k = i;
        for (int j = k + 1; j < length; j ++)
        {
            if (arrs[j] > arrs [k])
            {
                k = j;
            }
        }

        int temp = arrs[i];
        arrs[i] = arrs[k];
        arrs[k] = arrs[i];
    }
}

3、插入排序法
插入排序法首先默认第一个数是已经排序过的，然后从第二个数开始进行比较插入。

void insert(std::vector<int>& arrs)
{
    int length = arrs.size();
    for (int i = 0; i < length; i ++)
    {
        if (arrs[i] > arrs[i - 1])
        {
            int wait = arrs[i];
            int j = i;
            while (j > 0 && arrs[j -1] < wait)
            {
                arrs[j] = arrs[j - 1];
                j--;
            }
            arrs[j] = wait;
        }
    }
}

4、快速排序法
快速排序法的思想是找一个中间量的数，然后左右两端分别排序。

void quickSort(int array[], int left, int right){
    if (left > right){
        return;
    }
    int i, j, temp;
    i = left;
    j = right;
    //以最左边的数作为基准数
    temp = array[left];
    while (i != j){
        //先从右边开始找小于temp的元素  注意等号
        while (array[j] >= temp && i < j) {
            j--;
        }
        //再从左边开始找大于temp的元素
        while (array[i] <= temp && i < j){
            i++;
        }
        //左右哨兵均找到满足要求的数后，交换这两个数
        if (i < j){
            int change = array[i];
            array[i] = array[j];
            array[j] = change;
        }
    }
    //i==j  将基准数归位，此时基准数左边的数均小于基准数，右边的数均大于基准数
    array[left] = array[j];
    array[j] = temp;
    
    //然后递归处理基准左边未排序的数，和基准右边的数
    quickSort(array, left, i-1);
    quickSort(array, i + 1, right);
 
}