O(n2)的冒泡，选择，插入，先不贴，先贴归并，快排，堆排，

O(nlog(n))

归并排序

二路归并递归写法：时间O(nlog(n))，稳定，总时间O(nlog),空间：O(n+log(n))，n为内存，log(n)为栈空间

#include
     
      using namespace std;//归并过程void merge(int arr[], int l, int mid, int r){    int len=r-l+1;//合并长度    vector
      
        help; //临时数组    int lindex = l;    int rindex = mid+1;    while(lindex<=mid && rindex<=r){        if(arr[lindex]
       
        > n){        int arr[n];        for(int i = 0; i < n; i++) cin>>arr[i];        mergesort(arr, 0,n-1);//排序数组，和起始终止de下标        for(int i = 0; i < n; i++){            cout << arr[i] << " ";        }        cout << endl;    }    return 0;}/*108 6 7 9 2 3 4 1 0 5*/
       
      
     

 非递归和多路归并再说：

 

堆排序：对数组进行下标从1开始的堆排序，不稳定，O(nlogn)时间，O(1)空间

#include
     
      using namespace std;void heapadjust(int arr[],int index,int len){    int temp=arr[index];    for(int i=2*index;i<=len;i*=2){        if(i
      
       arr[i])            break;        arr[index]=arr[i];        index=i;    }    arr[index]=temp;}void heapsort(int arr[],int len){    //从最后一个非叶节点建立堆，从下标为1处开始排序    for(int i=len/2;i>=1;i--){        heapadjust(arr,i,len);    }    for(int i=len;i>1;i--){        swap(arr[1],arr[i]);        heapadjust(arr,1,i-1);    }}int main(){    int n;    while(cin >> n){        int arr[n];vector
       
         nums;arr[0]=0;        for(int i = 1; i <= n; i++) {cin>>arr[i];nums.push_back(arr[i]);}        heapsort(arr,n);        for(int i = 1; i <= n; i++){            cout << arr[i] << " ";        }        cout << endl;    }    return 0;}/*108 6 7 9 2 3 4 1 0 5*/
       
      
     

 

快速排序

递归实现：不稳定，最坏O(n2)，空间复杂度（由递归深度决定，O(n)~O(logn)）

#include 
     
      using namespace std;int partitions(int arr[],int low,int high){    int pivotkey=arr[low];    while(low
      
       =pivotkey)            high--;        arr[low]=arr[high];        while(low
       
        >n){        int arr[n];        for(int i=0;i
        
         >arr[i];        quicksort(arr,0,n-1);        for(int i=0;i