7种排序代码总结

冒泡排序

// 冒泡排序
template <typename T>
void bubbleSort(vector<T>& arr)
{
    int n = (int)(arr.size());
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
        }
    }
}

选择排序

// 选择排序
template <typename T>
void selectSort(vector<T>& arr)
{
    int n = (int)(arr.size());
    for(int i=0;i<n-1;i++) {
        int minId = i; // 从i开始最小的数的索引
        for(int j=i+1;j<n;j++){
            if(arr[j] < arr[minId])
                minId = j;
        }
        swap(arr[i], arr[minId]);
    }
}

插入排序

// 插入排序
template <typename T>
void insertSort(vector<T>& arr)
{
    int n = (int)(arr.size());
    for(int i=1;i<n;i++){
        for(int j=i;j>0;j--){
            if(arr[j] >= arr[j-1])
                break;
            swap(arr[j], arr[j-1]);
        }
    }
}

// 插入排序 优化版
template <typename T>
void insertSort2(vector<T>& arr)
{
    int n = (int)(arr.size());
    for(int i=1; i<n; i++){
        T e = arr[i]; // 该元素需要放在合适的位置
        int j; // e应该放在j这个位置
        for(j=i; j>0 && arr[j-1] > e; j--){
            arr[j] = arr[j-1];
        }
        arr[j] = e;
    }
}

希尔排序

// 希尔排序
template <typename T>
void shellSort(vector<T>& arr)
{
    int n = (int)(arr.size());
    for(int gap=n/2;gap>0;gap/=2){
        //内部使用插入排序
        for(int i=gap;i<n;i++){
            for(int j=i;j-gap>=0;j-=gap) {
                if(arr[j] >= arr[j-gap])
                    break;
                swap(arr[j], arr[j-gap]);
            }
        }
    }
}

归并排序

// 归并排序 递归版
template <typename T>
void _merge(vector<T>& arr, vector<int>& aux, int left, int right, int mid)
{
    // 复制一份出来
    for(int i=left; i<=right; i++) {
        aux[i] = arr[i];
    }
    int i = left;
    int j = mid+1;
    for(int k=left;k<=right;k++) {
        if(i>mid) {
            arr[k] = aux[j];
            j++;
        }
        else if(j>right) {
            arr[k] = aux[i];
            i++;
        }
        else if(aux[i] < aux[j] ) {
            arr[k] = aux[i];
            i++;
        }
        else {
            arr[k] = aux[j];
            j++;
        }
    }
}

// [left, right]
template <typename T>
void _mergeSort(vector<T>& arr, vector<T>& aux, int left, int right)
{
    if(left >= right)
        return;

    int mid = left + (right-left)/2;

    _mergeSort(arr, aux, left, mid); // [left, mid]
    _mergeSort(arr, aux, mid+1, right); // [mid+1, right]
    _merge(arr, aux, left, right, mid);
}

template <typename T>
void mergeSort(vector<T>& arr)
{
    vector<T> aux = arr; //辅助数组
    int n = int(arr.size());
    _mergeSort(arr, aux, 0, n-1);
}

三路快排

// [left, right]
template <typename T>
void _quickSort3Ways(vector<T>& arr, int left, int right)
{
    if(left >= right)
        return;
    int randId = rand() % (right-left+1)+left;
    swap(arr[left], arr[randId]);
    //当前位置是i， 第一个=的位置是j
    T pivot = arr[left];
    int i = left+1;
    int j = left+1;
    int k = right;
    while(i<=k){
        if(arr[i] > pivot) {
            swap(arr[i], arr[k]);
            k--;
        }
        else if(arr[i] < pivot) {
            swap(arr[i], arr[j]);
            i++;
            j++;
        }
        else {
            i++;
        }
    }
    swap(arr[j-1], arr[left]);
    _quickSort3Ways(arr, left, j-1);
    _quickSort3Ways(arr, k+1, right);

}

template <typename T>
void quickSort3Ways(vector<T>& arr)
{
    int n = (int)(arr.size());
    _quickSort3Ways(arr, 0, n-1);
}

堆排序

// i表示要调整的索引 n表示数组长度
template <typename T>
void adjust(vector<T>& arr, int i, int n)
{
    //只需要保证有左孩子，如果没有，啥都不用做
    while(2*i+1<n) {
        //判断左右选择那一边
        int k = 2*i+1;
        //如果有右孩子，就和左孩子比一下，选择更大的孩子
        if(k+1<n && arr[k] < arr[k+1])
            k += 1;

        if(arr[i] >= arr[k])
            break;

        swap(arr[i], arr[k]);
        i = k;
    }
}

template <typename T>
void heapSort(vector<T>& arr)
{
    int n =(int)(arr.size());
    // 变成一个最大堆
    for(int i=n/2 - 1;i>=0;i--) {
        adjust(arr, i, n);
    }

    //k表示数组长度
    for(int k=n-1;k>0;k--){
        swap(arr[0], arr[k]);
        adjust(arr, 0, k); //重新调整
    }
}