题解 | #排序#

//插入排序
    vector<int> insertSort(vector<int>& arr) {
        int tp;
        int j;
        for(int i = 1; i < arr.size(); i++) {
            j = i-1;
            tp = arr[i];
            while(j >= 0 && arr[j] > tp){
                arr[j+1] = arr[j];
                j--;
            }
            ++j;
            arr[j] = tp;
        }
        return arr;
    }
    //选择排序
    vector<int> selectSort(vector<int>& arr) {
        for(int i = 0; i < arr.size(); i++) {
            int min = i;;
            for(int j = i+1; j < arr.size(); j++) {
                if(arr[j] <= arr[min])
                    min = j;
            }
            if(min != i)
                swap(arr[min], arr[i]);
        }
        return arr;
    }
    //冒泡排序
    vector<int> bubleSort(vector<int>& arr) {
        bool flag = true;
        int len = arr.size()-1;
        while(len >= 0 && flag) {
            flag = false;
            for(int i = 0; i < len; i++) {
                if(arr[i] > arr[i+1]) {
                    flag = true;
                    swap(arr[i], arr[i+1]);
                }
            }
            len--;
        }
        return arr;
    }
    //快速排序
    vector<int> quickSort(vector<int> &arr, int low, int high) {
        int left =low, right = high;
        if(left > right) return arr;
        int base = arr[low];
        while(left < right) {
            while(left< right && arr[right] >= base){
                right--;
            }
            if(left < right) {
                arr[left] = arr[right];
                left++;
            }
            while(left < right && arr[left] <= base) {
                left++;
            }
            if(left < right) {
                arr[right] = arr[left];
                right--;
            }
        }
        arr[left] = base;
        quickSort(arr, low, right-1);
        quickSort(arr, right+1, high);
        return arr;
    }
    //堆排序 使用大跟堆
    //1、堆调整
    //2、头尾替换 再调整
    void adjust(vector<int> &arr, int i, int size) {
        int tp = arr[i];  //记录根节点
        for(int k = 2 * i + 1; k < size; k += 2 * k) {
            if(k + 1 < size && arr[k+1] > arr[k]){
                k++; //k指向最大的子节点
            }
            if(arr[k] > tp) { //与根节点进行比较
                arr[i] = arr[k];
                i = k;
            } else  //根节点最大 直接跳出
                break;
        }
        arr[i] = tp;        
    }
    vector<int> heapSort(vector<int>& arr) {
        //从最后一个有子树的根节点开始调整
        for(int i = arr.size() / 2 - 1; i >= 0; i--) { 
            adjust(arr, i, arr.size());
        }
        for(int i = arr.size()-1; i >= 0; i--) {
            swap(arr[0], arr[i]);
            adjust(arr, 0, i);
        }
        return arr;
    }