一、概要

不懂原理原理的，趕緊去找你的 Googe Baidu ??！源碼地址 GitHub

二、實現(xiàn)

//交換
void swap(int *x, int *y){
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}

1.冒泡排序

//冒泡排序
void bubbleSort(int* array, int length)
{
    int i, j;
    for(i = 0; i < length; i++)
    {
        for(j = 0; j < length-(i+1); j++)
        {
            //把大得換到最后（也可把小的換到最前）
            if(array[j] > array[j + 1])
            {
                swap(array+j,array+j+1);
            }
        }
    }
}

//改進冒泡排序
void improvedBubbleSort(int* array, int length)
{
    bool flag=true;
    int i, j;
    for(i = 0; i < length; i++)
    {
        if (false == flag) {
            return;
        }
        flag = false;
        for(j = 0; j < length-(i+1); j++)
        {
            //把大得換到最后（也可把小的換到最前）
            if(array[j] > array[j + 1])
            {
                swap(array+j,array+j+1);
                flag = true;
            }
        }
    }
}

2.插入排序

//插入排序
void insertSort(int* array, int length)
{
    int i, j, key;
    for(i = 1; i < length; i++)
    {
        j = i-1;
        key = array[i];
        while (j>=0 && array[j]>key) {
            array[j+1] = array[j];//元素后移
            j--;
        }
        array[j+1]=key;
    }
}

3.選擇排序

//選擇排序
void sectionSort(int* array, int length)
{
    int i, j, min;
    for(i = 0; i < length; i++)
    {
        min=i;
        for (j=i+1; j<length; j++) {
            if (array[j]<array[min]) {
                min=j;
            }
        }
        if (min!=i) {
            swap(array+i,array+min);
        }
        
    }
}

4.歸并排序

//將有二個有序數(shù)列a[first...mid]和a[mid+1...last]合并。
void mergeArray(int *a, int first, int mid, int last, int *temp)
{
    int i = first, m = mid;
    int j = mid + 1, n = last;
    int k = 0;//記錄元素個數(shù)
    
    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    
    while (i <= m)
        temp[k++] = a[i++];
    
    while (j <= n)
        temp[k++] = a[j++];
    
    //復制回原數(shù)組，這樣原數(shù)組這段就是有序的了
    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
//實現(xiàn)
void mergeSort(int *a, int first, int last, int *temp)
{
    if (first < last)
    {
        //分割
        int mid = (first + last) / 2;
        mergeSort(a, first, mid, temp);    //左邊有序
        mergeSort(a, mid + 1, last, temp); //右邊有序
        //合并
        mergeArray(a, first, mid, last, temp); //再將二個有序數(shù)列合并
    }
}

5.快速排序

#pragma mark 快速排序
//快速排序
void quickSort(int *s, int low, int high)
{
    int i, j, key;
    if (low < high)
    {
        i = low;
        j = high;
        key = s[i];
        while (i < j)
        {
            while(i < j && s[j] > key)
                j--; /* 從右向左找第一個小于key的數(shù) */
            if(i < j)
                s[i++] = s[j];
            
            while(i < j && s[i] < key)
                i++; /* 從左向右找第一個大于key的數(shù) */
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = key;
        quickSort(s, low, i-1); /* 遞歸調用 */
        quickSort(s, i+1, high);
    }
}

6.堆排序

//向下調整

//非遞歸實現(xiàn)
//array是待調整的堆數(shù)組，i是待調整的數(shù)組元素的位置，nlength是數(shù)組的長度
//本函數(shù)功能是：根據數(shù)組array構建大根堆
void heapDownAdjust(int array[],int i,int nLength)
{
    int nChild;
    //for(;2*i+1 < nLength;i=nChild)
    while(2*i+1 < nLength)
    {
        //子結點的位置=2*（父結點位置）+1
        nChild=2*i+1;//左孩子
        //得到子結點中較大的結點
        if(nChild<nLength-1 && array[nChild+1]>array[nChild])
            ++nChild;
        //如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點
        if(array[i]<array[nChild])
        {
            swap(array+i,array+nChild);
        }
        else
            break; //否則退出循環(huán)
        i=nChild;
    }
}

//遞歸實現(xiàn)
void heapDownRecursiveAdjust(int array[],int i,int nLength)
{
    int nChild;
    if (2*i+1 < nLength) {
        //子結點的位置=2*（父結點位置）+1
        nChild=2*i+1;//左孩子
        //得到子結點中較大的結點
        if(nChild<nLength-1 && array[nChild+1]>array[nChild])
            ++nChild;
        if(array[i]<array[nChild]){
            swap(array+i,array+nChild);
            heapDownRecursiveAdjust(array, nChild, nLength);
        }
    }
    
}

//向上調整
//非遞歸實現(xiàn)
void heapUpAdjust(int *array, int index, int nLength){
    int i = index;//子節(jié)點
    int j = (i-1)/2;//父結點
    int temp = array[i];
    while(i>0){
        if(temp <= array[j])
            break;
        else
        {
            array[i] = array[j];//比較換高明
            i = j;
            //記錄父結點
            j = (j-1)/2;
        }
    }
    array[i] = temp;
}

//遞歸實現(xiàn)
void heapUpRecursiveAdjust(int array[], int index, int nLength){
    int i = index;
    int j = (i-1)/2;
    if(i>0){
        if(array[i] <= array[j])
            return;
        else
        {
            swap(array+i, array+j);
            heapUpRecursiveAdjust(array, j, nLength);
        }
    }
}


//創(chuàng)建堆
void createHeap(int *array,int length)
{
    int i;
    //調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素
    //length/2-1是最后一個非葉節(jié)點，此處"/"為整除
    for(i=length/2-1;i>=0;--i)
        heapDownAdjust(array,i,length);
        //heapDownRecursiveAdjust(array,0,i);
}

//插入元素
int insertElement(int *array, int length, int element){
    if (length) {
        //放入元素，這里注意數(shù)組長度要大于length+1
        array[length]=element;
        ++length;
        //向上調整
        heapUpAdjust(array, length-1, length);
        //heapUpRecursiveAdjust(array, length-1, length);
        return length;
    }
    return -1;
}

//刪除堆元素（堆只能刪除根元素）
int deleteElement(int *array, int length){
    if (length) {
        //根結點與最后一個結點交換
        swap(array,array+length-1);
        //向下交換
        heapDownAdjust(array,0,length-1);
        return length-1;
    }
    return 0;
}

//堆排序算法
void heapSort(int *array,int length)
{
    int i;
    //從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素
    for(i=length-1;i>0;--i)
    {
        //把第一個元素和當前的最后一個元素交換，
        //保證當前的最后一個位置的元素都是在現(xiàn)在的這個序列之中最大的
        swap(array,array+i);
        //不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值
        heapDownAdjust(array,0,i);
        //heapDownRecursiveAdjust(array,0,i);
    }
}

7.計數(shù)排序

void countSort(int *input, int *output, int length, int k)//時間復雜度為Ο(n+k)（其中k是整數(shù)的范圍）
{
    // input為輸入數(shù)組，output為輸出數(shù)組，length表示數(shù)組長度，k表示有所輸入數(shù)字都介于0到k之間
    int C[k+1], i, value, pos;
    //初始化
    for(i=0; i<=k; i++)
    {
        C[i] = 0;
    }
    
    //檢查每個輸入元素，如果一個輸入元素的值為input[i],那么c[input[i]]的值加1，此操作完成后，c[i]中存放了值為i的元素的個數(shù)
    for(i=0; i< length; i++)
    {
        C[input[i]] ++;
    }
    
    // 通過在c中記錄計數(shù)和，c[i]中存放的是小于等于i元素的數(shù)字個數(shù)
    for(i=1; i<=k; i++)
    {
        C[i] = C[i] + C[i-1];
    }
    
    // 從后往前遍歷
    for(i=length-1; i>=0; i--)
    {
        value = input[i];
        pos = C[value];
        output[pos-1] = value;
        C[value]--;// 該操作使得下一個值為input[i]的元素直接進入輸出數(shù)組中input[i]的前一個位置
    }
}

8.基數(shù)排序

//找到num的從低到高的第pos位的數(shù)據
int getNumInPosition(int num,int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;
    
    return (num / temp) % 10;
}

//基數(shù)排序
#define RADIX_10 10      //正整形排序
#define KEYNUM_31 10     //正整形位數(shù)
void radixSort(int* array, int length)//時間復雜度O(dn)(d即表示最高位數(shù))
{
    //length表示數(shù)組長度
    int *radixArrays[RADIX_10];    //分別為0~9的序列空間
    for (int i = 0; i < 10; i++)
    {
        radixArrays[i] = (int *)malloc(sizeof(int) * (length + 1));
        radixArrays[i][0] = 0;    //index為0處記錄這組數(shù)據的個數(shù)
    }
    
    for (int pos = 1; pos <= KEYNUM_31; pos++)
    {
        //分配過程
        for (int i = 0; i < length; i++)
        {
            int num = getNumInPosition(array[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = array[i];
        }
        
        //收集
        for (int i = 0, j =0; i < RADIX_10; i++)
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                array[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;    //復位
        }
    }
}

9.桶排序

       桶排序是另外一種以O(n)或者接近O(n)的復雜度排序的算法.

     它假設輸入的待排序元素是等可能的落在等間隔的值區(qū)間內.一
     個長度為N的數(shù)組使用桶排序, 需要長度為N的輔助數(shù)組. 等間
     隔的區(qū)間稱為桶, 每個桶內落在該區(qū)間的元素. 桶排序是基數(shù)
     排序的一種歸納結果

       算法的主要思想: 待排序數(shù)組A[1...n]內的元素是隨機分布在
     [0,1)區(qū)間內的的浮點數(shù).輔助排序數(shù)組B[0....n-1]的每一個
     元素都連接一個鏈表.將A內每個元素乘以N(數(shù)組規(guī)模)取底,并以
     此為索引插入(插入排序)數(shù)組B的對應位置的連表中. 最后將所
     有的鏈表依次連接起來就是排序結果.
     
     這個過程可以簡單的分步如下:
     
       設置一個定量的數(shù)組當作空桶子。
       尋訪序列，并且把項目一個一個放到對應的桶子去。
       對每個不是空的桶子進行排序。
       從不是空的桶子里把項目再放回原來的序列中。

三、測試

測試

四、總結

排序是編程中常常遇到的問題，面試幾乎都會碰到，懂得其中的原理，并能編寫出代碼是必須的。探索原理不但可以提高編程技能，還可以培養(yǎng)一種編程思想 AND SO ON！