排序算法总结

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

O(nlog(n))

归并排序

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

#include<bits/stdc++.h>
using namespace std;

//归并过程
void merge(int arr[], int l, int mid, int r){
    int len=r-l+1;//合并长度
    vector<int> help; //临时数组
    int lindex = l;
    int rindex = mid+1;
    while(lindex<=mid && rindex<=r){
        if(arr[lindex]<arr[rindex]){
            help.push_back(arr[lindex++]);
        }else{
            help.push_back(arr[rindex++]);
        }
    }
    while(lindex<=mid){
        help.push_back(arr[lindex++]);
    }
    while(rindex<=r){
        help.push_back(arr[rindex++]);
    }
    for(int i=0;i<len;i++){
        arr[l+i]=help[i];
    }
}

void mergesort(int arr[], int l,int r){
    if(l==r) return;
    int mid=(r+l)/2;
    mergesort(arr,l,mid);
    mergesort(arr,mid+1,r);
    merge(arr,l,mid,r);
}

int main(){
    int n;
    while(cin >> 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;
}
/*
10
8 6 7 9 2 3 4 1 0 5
*/

 非递归和多路归并再说：

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

#include<bits/stdc++.h>
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<len && arr[i]<arr[i+1])
            i++;
        if(temp>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<int> 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;
}
/*
10
8 6 7 9 2 3 4 1 0 5
*/

快速排序

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

#include <bits/stdc++.h>

using namespace std;

int partitions(int arr[],int low,int high){
    int pivotkey=arr[low];
    while(low<high){
        while(low<high && arr[high]>=pivotkey)
            high--;
        arr[low]=arr[high];
        while(low<high && arr[low]<=pivotkey)
            low++;
        arr[high]=arr[low];
    }
    arr[low]=pivotkey;
    return low;
}

void quicksort(int arr[],int low,int high){
    if(low<high){
        int pivot=partitions(arr,low,high);
        quicksort(arr,low,pivot-1);
        quicksort(arr,pivot+1,high);
    }
}

int main(){
    int n;
    while(cin>>n){
        int arr[n];
        for(int i=0;i<n;i++) cin>>arr[i];
        quicksort(arr,0,n-1);
        for(int i=0;i<n;i++) cout<<arr[i]<<" ";
        cout<<endl;
    }
}
/*
10
8 6 7 9 2 3 4 1 0 5
*/