各种排序算法

各种排序算法的总结

规定一个统一的接口:

template <typename T>
void xxxx_sort(T *arr, int l, int r){
    /*
     *  函数具体实现
     */
}

### 时间复杂度：O(n^2)

冒泡排序

template <typename T>
void bubble_sort(T *arr, int l, int r){
    for (int i = r - 1; i >= l; i--){
        bool Swap = false;
        for (int j = l; j <= i; j++)
            if (arr[j] > arr[j + 1]){
                swap(arr[j], arr[j + 1]);
                Swap = true;
            }
        if (!Swap) break;
    }
}

插入排序

template <typename T>
void insert_sort(T *arr, int l, int r){
    
}

选择排序

时间复杂度：O(nlogn)

快速排序

template <typename T>
void quick_sort(T *arr, int l, int r){

    if (l >= r)
        return;
    
    int x = arr[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j){
        while (arr[++i] < x)
            ;
        while (arr[--j] > x)
            ;
        if (i < j)
            swap(arr[i], arr[j]);
    }

    quick_sort<int>(arr, l, j);
    quick_sort<int>(arr, j + 1, r);
}

归并排序

template <typename T>
void merge_sort(T *arr, int l, int r){
    T *tmp = new T[r - l + 1];
    m_sort<int>(arr, tmp, l, r);
    delete tmp;
}
template <typename T>
void m_sort(T *arr, T *tmp, int l ,int r){
    if (l >= r)
        return;
    
    int mid = l + r >> 1;
    m_sort<T>(arr, tmp, l, mid);
    m_sort<T>(arr, tmp, mid + 1, r);

    int k = l;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r){
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (int i = l; i <= r; i++)
        arr[i] = tmp[i];
}