常見排序算法一般按平均時間復(fù)雜度分為兩類：
O(n^2)：冒泡排序猜拾、選擇排序府适、插入排序
O(nlogn)：歸并排序羔飞、快速排序、堆排序

簡單排序時間復(fù)雜度一般為O(n^2)檐春，如冒泡排序逻淌、選擇排序、插入排序等
高級排序時間復(fù)雜度一般為O(nlogn)疟暖，如歸并排序卡儒、快速排序、堆排序俐巴。

兩類算法隨著排序集合越大骨望，效率差異越大，在數(shù)量規(guī)模1W以內(nèi)的排序欣舵，兩類算法都可以控制在毫秒級別內(nèi)完成擎鸠，但當(dāng)數(shù)量規(guī)模達(dá)到10W以上后，簡單排序往往需要以幾秒缘圈、分甚至小時才能完成排序劣光；而高級排序仍可以在很短時間內(nèi)完成排序。

一）選擇排序：遍歷數(shù)組元素糟把，找到最小值然后與第n個索引（n=0绢涡，1，2...lengh)交換遣疯。(不穩(wěn)定排序)

#include <stdio.h>
void selectsort(int *a,int len)
{
        int tmp =0;
        int index = 0;
        for(int i =0; i<len; i++)
        {
                tmp = a[i];
                index = i;
                for(int j = i+1;j<len;j++)
                {
                        if(tmp > a[j])
                        {
                                tmp = a[j];
                                index= j;
                        }
                }
                a[index]=a[i];
                a[i]=tmp;
        }
}
cc

int main()
{
        int a[]={342,367,1,989,3,9,235,8,0,432,2};
        int number = sizeof(a)/sizeof(int);
        selectsort(a,number);
        for(int i =0;i<number;i++)
        {
                printf(" %d",a[i]);
        }
        return 0;
}

二)冒泡排序：數(shù)組內(nèi)相鄰元素比較大小相互交換雄可，循環(huán)遍歷最大的向下降。（穩(wěn)定性排序）

#include <stdio.h>
void bubblesqort(int *a,int len)
{
        int tmp=0;
        for(int i =0;i<len-1;i++)
        {
                for(int j =0;j<len-1-i;j++)
                {
                        if(a[j]>a[j+1])
                        {
                                tmp=a[j];
                                a[j]=a[j+1];
                                a[j+1]=tmp;
                        }
                }
        }
}

int main()
{
        int a[]={342,367,1,989,3,9,235,8,0,432,2};
        int number = sizeof(a)/sizeof(int);
        bubblesqort(a,number);
        for(int i =0;i<number;i++)
        {
                printf(" %d",a[i]);
        }
        return 0;
}

三）快速排序：

設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)滞项，然后將所有比它小的數(shù)都放到它前面狭归，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序文判。值得注意的是过椎，快速排序不是一種穩(wěn)定的排序算法，也就是說戏仓，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動疚宇。
一趟快速排序的算法是：
1）設(shè)置兩個變量i、j赏殃，排序開始的時候：i=0敷待，j=N-1；
2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)仁热，賦值給key榜揖，即key=A[0]；
3）從j開始向前搜索抗蠢，即由后開始向前搜索(j--)举哟，找到第一個小于key的值A(chǔ)[j]，將A[j]和A[i]互換迅矛；
4）從i開始向后搜索妨猩，即由前開始向后搜索(i++)，找到第一個大于key的A[i]秽褒，將A[i]和A[j]互換壶硅；
5）重復(fù)第3、4步销斟，直到i=j庐椒； (3,4步中，沒找到符合條件的值蚂踊，即3中A[j]不小于key,4中A[i]不大于key的時候改變j扼睬、i的值，使得j=j-1悴势，i=i+1窗宇，直至找到為止。找到符合條件的值特纤，進行交換的時候i军俊， j指針位置不變。另外捧存，i==j這一過程一定正好是i+或j-完成的時候粪躬，此時令循環(huán)結(jié)束）担败。

#include <stdio.h>
void qsort(int *a,int nleft, int nright)
{
        if(nleft>=nright)
                return;
        int i =nleft;
        int j =nright;
        int key =a[i];
        while(i<j)
        {
                while(i<j && a[j]>=key)
                        j--;
                a[i]=a[j];
                while(i<j && a[i]<=key)
                        i++;
                a[j]=a[i];
        }
        a[i]=key;

        qsort(a,nleft,i-1);
        qsort(a,i+1,nright);

}

int main()
{
        int a[]={4321,3,54,57,96567,23,78634,67565,23,78,0,4,56,234,321,1,5546,62634};
        int len = sizeof(a)/sizeof(int);
        qsort(a, 0, len-1);
        for(int i =0;i<len;i++)
        {
                printf(" %d",a[i]);
        }
        return 0;
}

四）堆排序

堆排序是利用堆的性質(zhì)進行的一種選擇排序。
利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性镰官，使得每次從無序中選擇最大記錄(最小記錄)變得簡單提前。

（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)
② 再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個記錄R[n]交換泳唠，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]狈网，且滿足R[1..n-1].keys≤R[n].key
③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆笨腥。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換拓哺，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys脖母，同樣要將R[1..n-2]調(diào)整為堆士鸥。
……
直到無序區(qū)只有一個元素為止晾剖。

#include <stdio.h>
//array是待調(diào)整的堆數(shù)組蛾洛，i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長度
//本函數(shù)功能是：根據(jù)數(shù)組array構(gòu)建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
    int nChild;
    int nTemp;
    for(;2*i+1<nLength;i=nChild)
    {
        //子結(jié)點的位置=2*（父結(jié)點位置）+1
        nChild=2*i+1;
        //得到子結(jié)點中較大的結(jié)點
        if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
        //如果較大的子結(jié)點大于父結(jié)點那么把較大的子結(jié)點往上移動负拟，替換它的父結(jié)點
        if(array[i]<array[nChild])
        {
            nTemp=array[i];
            array[i]=array[nChild];
            array[nChild]=nTemp; 
        }
        else break; //否則退出循環(huán)
    }
}
//堆排序算法
void HeapSort(int array[],int length)
{
    int i;
    //調(diào)整序列的前半部分元素肥照，調(diào)整完之后第一個元素是序列的最大的元素
    //length/2-1是最后一個非葉節(jié)點脚仔，此處"/"為整除
    for(i=length/2-1;i>=0;--i)
    HeapAdjust(array,i,length);
    //從最后一個元素開始對序列進行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個元素
    for(i=length-1;i>0;--i)
    {
        //把第一個元素和當(dāng)前的最后一個元素交換建峭，
        //保證當(dāng)前的最后一個位置的元素都是在現(xiàn)在的這個序列之中最大的
        array[i]=array[0]^array[i];
        array[0]=array[0]^array[i];
        array[i]=array[0]^array[i];
        //不斷縮小調(diào)整heap的范圍玻侥，每一次調(diào)整完畢保證第一個元素是當(dāng)前序列的最大值
        HeapAdjust(array,0,i);
    }
}
int main()
{
    int i;
    int num[]={9,8,7,6,5,4,3,2,1,0};
    HeapSort(num,sizeof(num)/sizeof(int));
    for(i=0;i<sizeof(num)/sizeof(int);i++)
    {
        printf("%d ",num[i]);
    }
    printf("\nok\n");
    return 0;
}

五）歸并排序

歸并排序時的時間復(fù)雜度為O（nlgn) 其主要思想是分治法(divide and conquer)决摧，分就是要將n個元素的序列劃分為兩個序列亿蒸，再將兩個序列劃分為4個序列，直到每個序列只有一個元素掌桩，最后边锁，再將兩個有序序列歸并成一個有序的序列。

#include <stdlib.h>
#include <stdio.h>

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}


void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

int main(int argc, char * argv[])
{
    int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
    int i, b[8];
    MergeSort(a, b, 0, 7);
    for(i=0; i<8; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

六）插入排序

插入排序就是每一步都將一個待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置波岛，直到全部插入完畢茅坛。

#include <stdio.h>
void insert_sort(int *array, unsigned int n)
{
        int i,j;
        int temp;
        for(i=1; i<n;i++)
        {
                temp = *(array+i);
                for(j=i;j>0 && *(array+j-1)>temp;j--)
                {
                        *(array+j) = *(array+j-1);
                }
                *(array+j)=temp;
        }
}

int main()
{
        int m[]={223,53,232,43,343435,231,13,56,2,7343,3,64426,23,53462,23,2,6544,3,4};
        int len = sizeof(m)/sizeof(int);
        insert_sort(m, len);
        for(int i = 0;i<len;i++)
        {
                printf("%d ", m[i]);
        }
        printf("\n ok\n");
        return 0;
}

七）折半插入排序

折半插入排序（binary insertion sort）是對插入排序算法的一種改進，由于排序算法過程中则拷，就是不斷的依次將元素插入前面已排好序的序列中贡蓖。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點煌茬，可以采用折半查找的方法來加快尋找插入點的速度斥铺。
(減少了比較次數(shù)，交換次數(shù)一樣）

#include<iostream>    
using namespace std;    
  
void BinaryInsertSort(int *a,int left,int right){  
    int tmp ;  
    int i,low,high,middle,k;    
  
    for( i =left+1 ; i<=right ; i++){  
        tmp = a[i];  
        low = left;  
        high = i -1;  
        while( low <= high ){  
            middle = (low + high )/2;  
            if(tmp < a[middle])  
                high = middle -1;  
            else  
                low= middle + 1;  
        }  
        for( k = i-1 ; k >= low ; k--)  
            a[k+1] = a[k];  
        a[low] = tmp;  
    }  
}  
  
int main(){  
    int a[]={43,24,54,2,345,3,12,6};  
    BinaryInsertSort(a,0,7);  
    for(int i=0;i<8 ;i++)  
        cout<<a[i]<<" ";  
    cout<<endl;  
    return 0;
} 

八）希爾排序

希爾排序坛善，也稱遞減增量排序算法晾蜘，是插入排序的一種更高效的改進版本邻眷。希爾排序是非穩(wěn)定排序算法。
希爾(Shell)排序又稱為縮小增量排序剔交，它是一種插入排序肆饶。它是直接插入排序算法的一種威力加強版。

希爾排序的基本思想是：
把記錄按步長gap 分組岖常，對每組記錄采用直接插入排序方法進行排序驯镊。
隨著步長逐漸減小，所分成的組包含的記錄越來越多腥椒，當(dāng)步長的值減小到 1 時阿宅，整個數(shù)據(jù)合成為一組，構(gòu)成一組有序記錄笼蛛，則完成排序

#include <stdio.h>
#include<iostream>  
using namespace std; 

void ShellSort(int* data,unsigned int len)
{
    if(len<=1||data==NULL)
        return;

    int j = 0;
    for(int div=len/2;div>=1;div/=2)
    {
        for(int i=div;i<len;i++)
        {
            for( j=i;(j-div>=0)&&(j>=0)&&(data[j]<data[j-div]);j-=div)
            {               
                swap( *(data+j),*(data+j-div));
            }
        }
    }
}

int main()
{  
    int a[]={345,24,54,2,43,3,12,6};  
    ShellSort(a,8);  
    for(int i=0;i<8 ;i++)  
        cout<<a[i]<<" ";  
    cout<<endl;  
        return 0;
}

九）基數(shù)排序

實現(xiàn)原理

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度洒放，數(shù)位較短的數(shù)前面補零。然后滨砍，從最低位開始往湿，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列惋戏。
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital）领追，LSD的排序方式由鍵值的最右邊開始，而MSD則相反响逢，由鍵值的最左邊開始绒窑。

#include <stdio.h>
#include<iostream>  
using namespace std; 

int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
{
    int d = 1; //保存最大的位數(shù)
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixsort(int data[], int n) //基數(shù)排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //計數(shù)器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //進行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空計數(shù)器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //統(tǒng)計每個桶中的記錄數(shù)
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
        for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //將臨時數(shù)組的內(nèi)容復(fù)制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}


int main()
{  
    int a[]={345,24,54,2,43,3,12,6};  
    radixsort(a,8);  
    for(int i=0;i<8 ;i++)  
        cout<<a[i]<<" ";  
    cout<<endl;  
        return 0;

}