归并排序Merge Sort

自顶向下进行排序

//归并排序
#include<iostream>
#include<algorithm>
using namespace std;



template<typename T>
void _mergeSort(T arr[],int l,int mid,int r){
   T aux[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++;
       }
       
       
   }
   
   
   
}

//递归使用归并排序，对[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[],int l,int r){
    if (l>=r)
        return;
    int mid = (r-l)/2 + l;
    __mergeSort(arr,0,mid);
    __mergeSort(arr,mid+1,r);
    _mergeSort(arr,l,mid,r);
    
}
template<typename T>
void mergeSort(T arr[],int n){
   __mergeSort(arr,0,n-1);
}

自底向上进行归并排序

//自低向上归并排序 Merge Sort
template<typename T>
void mergeSortBU(T arr[],int n){
    for (int sz = 1; sz < n; sz += sz)
        for (int i = 0; i + sz < n; sz+=sz+sz)
            //对arr[i...i+sz-1]和arr[i+sz...i+2*sz-1]进行归并
            _mergeSort(arr,i,i+sz,min(i+sz+sz+1,n-1));
}

快速排序

//快速排序
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
//返回p，使得arr[l...p-1]<arr[p] arr[p+1...r]>arr[p]
int __partition(T arr[],int l,int r){
    T v = arr[l];
    //arr[l+1...j]<v arr[j+1...i]>v
    int j = l;
    for (int i = l+1; i < r; i++)
    {
        if (arr[i]<v)
        {
            swap(arr[j+1],arr[i]);
            j++;
        }
        
    }

    swap(arr[l],arr[j]);
    return j; 
}

//对arr[l...r]部分进行快速排序
template<typename T>
void __quickSort(T arr[],int l,int r){
    if (l>=r)
    return;
    int p = __partition(arr,l,r);
    __quickSort(arr,l,p-1);
    __quickSort(arr,p+1,r);
    
}

template<typename T>
void __quickSort(T arr[],int n) {
    __quickSort(arr,0,n-1);
}