归并排序和快速排序

归并排序：将数组每次分成两部分分别排序，然后逐一合并

 



 1 template<typename T>
void __merge(T arr[], int l, int mid, int r) {
    int *aux = new int[r - l + 1];//开辟新的空间
    for (int i = l; i <= r; i++)
        aux[i - l] = arr[i];
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid)
        {
            arr[k] = aux[j - l];
            j++;
        }
        else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l])
        {
            arr[k] = aux[i - l];
            i++;
        }
        else
        {
            arr[k] = aux[j - l];
            j++;
        }
    }
    delete[] aux;

}
template<typename T>
void __mergeSort(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertionSort(arr, l, r);//使用插入排序对其进行优化
        return;
    }
    /*if(r-l<=15) {
    insertionSort(arr,l,r);
    return ;
    }
    */
    int mid = (l + r) / 2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    if (arr[mid]>arr[mid + 1])//对近乎有序的数组的优化
        __merge(arr, l, mid, r);
}
template<typename T>
void mergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n - 1);
}
template<typename T>
void mergeSortBU(T arr[], int n) {//自底向上排序
    for (int sz = 1; sz <= n; sz += sz)
        for (int i = 0; i + sz < n; i += sz + sz)
            __merge(arr, i, i + sz - 1, min(n - 1, i + sz + sz - 1));
}

快速排序：将数组分成两部分，使得组边部分小于标准，右边部分大于标准，这样就将标准元素放到了排序数组正确的位置

template<typename T>//找到一个索引使得arr[l...p-1]<v,arr[p+1..r]>v,这样v就在恰当的位置了
int  __partition(T arr[], int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);//优化

    T v = arr[l];//一个标准两个索引
    int j = l;//使得arr[l+1...j] < v ; arr[j+1...i) > v，每次遇到小于v的元素进行交换， 扩充arr[l+1...j]的同时，将大于部分往后放
    for (int i = l + 1; i <= r; i++)
    {
        if (arr[i] < v) {
            j++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[l], arr[j]);//将v放到恰当位置
    return j;
}
template<typename T>
void __quickSort(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}


template<typename T>//找到一个索引使得arr[l...p-1]<v,arr[p+1..r]>v,这样v就在恰当的位置了
int  __partition2(T arr[], int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);//优化，对于近乎有序的数组，快速排序会退化成一个O(n2)级别的算法

    T v = arr[l];//一个标准两个索引
    int i = l + 1, j = r;
    while (true) {
        while (i <= r && arr[i] < v)
            i++;

        while (j >= l + 1 && arr[j] > v)
            j--;
        if (i>j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[j], arr[l]);
    return j;
}
template<typename T>
void __quickSort2(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }
    int p = __partition2(arr, l, r);
    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p + 1, r);
}
template<typename T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

三路快排

//三路快速排序
template <typename T>
void __quickSort3Ways(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l + 1;    // arr[lt+1...i) == v
    while (i < gt) {
        if (arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            i++;
            lt++;
        }
        else if (arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        }
        else { // arr[i] == v
            i++;
        }
    }

    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n) {

    srand(time(NULL));
    __quickSort3Ways(arr, 0, n - 1);
}