冒泡排序

    void bubbleSort(vector<int>& arr){
        for(int i = 0; i < arr.size(); ++i){
            int flag = true;
            for(int j = 0; j < arr.size() - 1 - i; ++j){
                if(arr[j+1] < arr[j]){
                    swap(arr[j], arr[j+1]);
                    flag = false;
                }
            }
            if(flag) return;
        }
    }

插入排序

    void insertSort(vector<int>& arr){
        for(int i = 1; i < arr.size(); ++i){
            int val = arr[i];
            int index = i - 1;
            //如果比val大志电，就右移
            while(index >= 0 && arr[index] > val){
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = val;
        }
    }

選擇排序

    void selectSort(vector<int>& arr){
        for(int i = 0; i < arr.size() - 1; ++i){
            int minIndex = i;
            //i后面哪個比arr[i]小，哪個就是minIndex
            for(int j = i + 1; j < arr.size(); j++){
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr[i], arr[minIndex]);
        }
    }

歸并排序

class Sorts{
public:
    void mergeSort(vector<int>& arr, int left, int right){
        if(left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
    void Merge(vector<int>& arr, int left, int mid, int right){
        int i = left;
        int j = mid + 1;
        int k = 0;
        vector<int> tmp(right - left + 1);
        while(i <= mid && j <= right){
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        if(i <= mid){
            while(i <= mid) tmp[k++] = arr[i++];
        } else{
            while(j <= right) tmp[k++] = arr[j++];
        }
        //注意arr范圍left -> right
        for(int i = 0; i < tmp.size(); ++i){
            arr[left + i] = tmp[i];
        }
    }
};

快排

class Sorts{
public:
    void quickSort(vector<int>& arr, int left, int right){
        if(left >= right) return;
        int q = _partition(arr, left, right);
        quickSort(arr, left, q - 1);
        quickSort(arr, q + 1, right);
    }
    int _partition(vector<int>& arr, int left, int right){
        int pivot = arr[left];
        int j = left;
        for(int i = left + 1; i <= right; ++i){
            if(arr[i] <= pivot){
                j++;
                swap(arr[j], arr[i]);
            }
        }
        swap(arr[left], arr[j]);
        return j;
    }
};

堆排序

class HeapSort{
public:
    void sort(vector<int>& arr){
        if(arr.size() <= 1) return;
        buildHeap(arr);
        int k = arr.size() - 1;
        while(k > 0){
            swap(arr[0], arr[k--]);
            heapify(arr, k, 0);
        }
    }
    void buildHeap(vector<int>& arr){
        for(int i = (arr.size() - 1) / 2; i >= 0; --i){
            heapify(arr, arr.size() - 1, i);
        }
    }
    void heapify(vector<int>& arr, int length, int i){
        int maxPos = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        maxPos = (l <= length && arr[l] > arr[maxPos]) ? l : maxPos;
        maxPos = (r <= length && arr[r] > arr[maxPos]) ? r : maxPos;
        if(maxPos != i){
            swap(arr[i], arr[maxPos]);
            heapify(arr, length, maxPos);
        }
    }
};