十大排序算法

排序算法
- 冒泡排序
- 快速排序
- 插入排序
- 希爾排序
- 選擇排序
- 堆排序
- 歸并排序
- 桶排序
- 基數排序
- 計數排序
- 參考資料

排序算法

十大排序算法(C++版)排序算法

冒泡排序

#include <bits/stdc++.h>
using namespace std;
//時間複雜度 最好的：O(n^2), 最壞：O(n^2),平均：O(n^2),空間複雜度：O(1),穩定
//改善的冒泡排序 最好：O(n) 最好 O(n^2) 平均 O(n^2)
void bubble(int a[],int length){

    for(int i=1;i<length;i++){
        bool flag=false;
        for(int j=0;j<length-i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
        if(flag==false) break;
    }
}

快速排序

//快速排序：最好時間複雜度：O(nlogn),最差時間複雜度：O(nlogn),平均時間複雜度：O(nlogn),空間複雜度：O(logn),不穩定

int par(int a[],int length,int i,int j){
    if(a==nullptr || length<=0 || i<0 || j>=length) {
        cout<<"parameter is invalid"<<endl;
        exit(0);
    }

    int index=i+rand()%(j-i+1);
    swap(a[index],a[i]);
    int temp=a[i];
    while(i<j){
        while(i<j && a[j]>=temp) --j;
        if(i<j) a[i]=a[j];
        while(i<j && a[i]<temp) ++i;
        if(i<j) a[j]=a[i];
    }
    a[i]=temp;
    return i;
}

void quickSort(int a[],int length,int i,int j){
    if(i==j) return;
    int index=par(a,length,i,j);
    if(index>i){
        quickSort(a,length,i,index-1);
    }
    if(index<j){
        quickSort(a,length,index+1,j);
    }
}

插入排序

//插入排序，最壞的時間複雜度：O(n^2),最好的時間複雜度為：O(n),平均時間複雜度為：O(n^2),空間複雜度：O(1),穩定
void insertSort(int a[],int length){
    for(int i=1;i<length;i++)
        for(int j=i-1;j>=0 && a[j]>a[j+1]; j--)
            swap(a[j],a[j+1]);
}

希爾排序

//希爾排序,最壞時間複雜度：O(n^2),最好的時間複雜度：O(n),平均時間複雜度：O(n^1.3);空間複雜度：O(1),不穩定

void shellSort(int a[],int length){
    int gap=length/2;
    while(gap>0){
        //gap=gap/3+1;
        for(int i=gap;i<length;i++){
            int cur=a[i];
            int preIndex=i-gap;
            while(preIndex>=0 && a[preIndex]>cur){
                a[preIndex+gap]=a[preIndex];
                preIndex-=gap;
            }
            a[preIndex+gap]=cur;
        }
        gap=gap/2;
    }
}


void shellSort2(int a[], int length){
    if(a==nullptr || length<=0){
        cout<<"invalid parameters"<<endl;
        exit(0);
    }

    int gap=length/2;
    while(gap>0){
        for(int i=gap;i<length;i++){
            int cur=a[i];
            int preIndex=i-gap;
            while(preIndex>=0 && a[preIndex]>cur){
                a[preIndex+gap]=a[preIndex];
                preIndex=preIndex-gap;
            }
            a[preIndex+gap]=cur;
        }
        gap=gap/2;
    }
}

選擇排序

//選擇排序：最好的時間複雜度：O(n^2),最差的時間複雜度：O(n^2),平均時間複雜度：O(n^2),空間複雜度：O(1),不穩定
void selectSort(int a[],int length) {
    for(int i=0;i<length-1;i++){
        int minIndex=i;
        for(int j=i+1;j<length;j++){
            if(a[j]<a[minIndex])
                minIndex=j;
        }
        swap(a[i],a[minIndex]);
    }
}

堆排序

//堆排序，最好時間複雜度：O(nlogn),最差時間複雜度：O(nlogn),平均時間複雜度：O(nlogn),空間複雜度：O(1),不穩定


void bulidHeap(int a[], int length,int index) {
    int temp=a[index];
    for(int k=index*2+1;k<length;k=k*2+1){
        if(k+1<length && a[k]<a[k+1]) ++k;
        if(a[k]>temp){
            a[index]=a[k];
            index=k;
        }else break;
    }

    a[index]=temp;
}

void heapSort(int a[],int len){
    for(int i=len/2-1;i>=0;i--)//從第一個非葉子結點開始
        bulidHeap(a,len,i);
    for(int j=len-1;j>0;j--){
        swap(a[0],a[j]);
        bulidHeap(a,j,0);
    }

}

歸并排序

//歸并排序,最好的時間複雜度：O(nlogn),最好的時間複雜度：O(nlogn),平均時間複雜度：O(nlogn),空間複雜度：O(n),穩定
void merge(int a[],int L,int M,int R){
    int *cent=new int[R-L+1];
    int i=0;
    int pFirst=L;
    int pSecond=M+1;
    while(pFirst<=M && pSecond<=R){
        cent[i++]=a[pFirst]<a[pSecond]?a[pFirst++]:a[pSecond++];
    }
    while(pFirst<=M) cent[i++]=a[pFirst++];
    while(pSecond<=R) cent[i++]=a[pSecond++];
    for(int j=0;j<(R-L+1);j++)
        a[L+j]=cent[j];
    delete[] cent;
}


void mergeSort(int a[],int L,int R){
    if(L==R) return;
    int mid=(L+R)/2;
    mergeSort(a,L,mid);
    mergeSort(a,mid+1,R);
    merge(a,L,mid,R);
}

void mergeSort(int a[],int length){
    if(a==nullptr || length<1) return;
    mergeSort(a,0,length-1);
}

桶排序

對于N個待排資料，M個桶，平均每個桶[N/M]個資料的桶排序平均時間複雜度為：

O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-NlogM)

//桶排序：最差時間複雜度：O(n^2),最好時間複雜度：O(n),平均時間複雜度：O(n+k),空間複雜度：O(n+k),穩定
void insertNum(list<int> &bucket,int val){
    auto iter=bucket.begin();
    while(iter!=bucket.end() && val>=*iter) ++iter;
    bucket.insert(iter,val);
}

void bucketSort(int a[],int length){
    if(a==nullptr || length<=1) return;
    int mina=a[0],maxa=a[0];
    for(int i=0;i<length;i++){
        mina=min(a[i],mina);
        maxa=max(a[i],maxa);
    }

    int k=10;
    int bucketNumber=(maxa-mina)/k+1;

    vector<list<int>> buckets(bucketNumber);
    for(int i=0;i<length;i++){
        int val=a[i];
        insertNum(buckets[(val-mina)/k],val);
    }

    int index=0;
    for(int i=0;i<bucketNumber;i++){
        if(buckets[i].size()>=0){
            for(auto &value:buckets[i]) a[index++]=value;
        }
    }
}

基數排序

//基數排序：最壞時間複雜度：O(n*k),最好時間複雜度：O(n*k),平均時間複雜度：O(n*k),空間複雜度：O(n+k),穩定

int findKth(int num,int n){
    int power=1;
    for(int i=0;i<n;i++) power*=10;
    return (num%power)*10/power;
}

void RadixSort(int a[],int length){
    if(a==nullptr || length<=1) return;
    int maxA=a[0];
    for(int i=0;i<length;i++){
        if(a[i]>maxA) maxA=a[i];
    }

    int k=0;
    //cout<<maxA<<endl;
    while(maxA>0){
        ++k;
        maxA/=10;
    }
    //cout<<"k: "<<k<<endl;

    for(int i=1;i<=k;i++){
        int C[10]={0};
        int B[length];
        for(int j=0;j<length;j++){
            int d=findKth(a[j],i);
            ++C[d];
        }
        for(int j=1;j<10;j++){
            C[j]=C[j]+C[j-1];
        }

        for(int j=length-1;j>=0;j--){
            int d=findKth(a[j],i);
            --C[d];
            B[C[d]]=a[j];
        }

        for(int j=0;j<length;j++)
            a[j]=B[j];
    }
}

int main()
{
    int a[]={15,9,8,7,6,5,4,3,2,1,12,23,45};
    RadixSort(a,13);
    for(int i=0;i<13;i++) cout<<a[i]<<endl;
    return 0;
}

計數排序

基數排序：最壞時間複雜度：O(n+k),最好時間複雜度：O(n+k),平均時間複雜度：O(n+k),空間複雜度：O(n),穩定

#include<iostream>
using namespace std;
int findmax(int *a,int size)
{
	int max=0;
	int length=size;
	for(int i=1;i!=length;i++)
	{
		if(a[max]<a[i])
		max=i;
	}
	return a[max];
}
int* countsort(int *a,int size)
{
	int k=findmax(a,size)+1;
	int *c=new int[k];
	int length=size;
	
	for(int j=0;j!=k;j++)
		c[j]=0;
	for(int i=0;i!=length;i++)
		c[a[i]]=c[a[i]]+1;
	for(int i=1;i!=k;i++)
		c[i]=c[i]+c[i-1];
	int *b=new int[length];
	for(int i=length-1;i>=0;i--)
	{
		b[c[a[i]]-1]=a[i];
		c[a[i]]=c[a[i]]-1;
	}
	return b;
	delete [] c;
}

參考資料

https://blog.csdn.net/hellozhxy/article/details/79911867
https://blog.csdn.net/wordwarwordwar/article/details/22621689

十大排序算法(C++版)排序算法

十大排序算法

排序算法

冒泡排序

快速排序

插入排序

希爾排序

選擇排序

堆排序

歸并排序

桶排序

基數排序

計數排序

參考資料

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述