排序算法总结

分手后的思念是犯贱 2021-12-21 01:21 262阅读 0赞

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
    */

转载于:https://www.cnblogs.com/joelwang/p/10656498.html