排序算法及其C實(shí)現(xiàn)是怎樣的

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)排序算法及其C實(shí)現(xiàn)是怎樣的，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

排序算法(Sorting Algorithm)是計(jì)算機(jī)算法的一個(gè)組成部分。

排序的目標(biāo)是將一組數(shù)據(jù) (即一個(gè)序列) 重新排列，排列后的數(shù)據(jù)符合從大到小 (或者從小到大) 的次序。這是古老但依然富有挑戰(zhàn)的問(wèn)題。Donald Knuth的經(jīng)典之作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》(The Art of Computer Programming)的第三卷就專門用于討論排序和查找。從無(wú)序到有序，有效的減小了系統(tǒng)的熵值，增加了系統(tǒng)的有序度。對(duì)于一個(gè)未知系統(tǒng)來(lái)說(shuō)，有序是非常有用的先驗(yàn)知識(shí)。因此，排序算法很多時(shí)候構(gòu)成了其他快速算法的基礎(chǔ)，比如二分法就是基于有序序列的查找算法。直到今天，排序算法依然是計(jì)算機(jī)科學(xué)積極探索的一個(gè)方向。

我在這里列出一些最常見(jiàn)的排序方法，并嘗試使用C語(yǔ)言實(shí)現(xiàn)它們。一組數(shù)據(jù)存儲(chǔ)為一個(gè)數(shù)組a，數(shù)組有n個(gè)元素。a[i]為數(shù)組中的一個(gè)元素，i為元素在數(shù)組中的位置 (index)。根據(jù)C的規(guī)定，數(shù)組下標(biāo)從0開(kāi)始。假設(shè)數(shù)組從左向右排列，下標(biāo)為0的元素位于數(shù)組的最左邊。

序列將最終排列成從小到大的順序。下面函數(shù)中的參數(shù)ac是數(shù)組中元素的數(shù)目，也就是n。

(C語(yǔ)言的數(shù)組名都轉(zhuǎn)成指針，傳遞給函數(shù)，所以需要傳遞數(shù)組中元素的數(shù)目ac給函數(shù)，詳細(xì)見(jiàn)"Expert C Programming: Deep C Secrets"一書(shū))

起始數(shù)列 （unsorted）

有序數(shù)列 (sorted)

冒泡排序 (Bubble Sort)

對(duì)于一個(gè)已經(jīng)排序好的序列，它的任意兩個(gè)相鄰元素，都應(yīng)該滿足a[i-1] <= a[i]的關(guān)系。冒泡排序相當(dāng)暴力的實(shí)現(xiàn)了這一目標(biāo)：不斷掃描相鄰元素，看它們是否違章。一旦違章，立即糾正。在冒泡排序時(shí)，計(jì)算機(jī)從右向左遍歷數(shù)組，比較相鄰的兩個(gè)元素。如果兩個(gè)元素的順序是錯(cuò)的，那么sorry，請(qǐng)兩位互換。如果兩個(gè)元素的順序是正確的，則不做交換。經(jīng)過(guò)一次遍歷，我們可以保證最小的元素(泡泡)處于最左邊的位置。

然而，經(jīng)過(guò)這么一趟，冒泡排序不能保證所有的元素已經(jīng)按照次序排列好。我們需要再次從右向左遍歷數(shù)組元素，進(jìn)行冒泡排序。這一次遍歷，我們不用考慮最左端的元素，因?yàn)樵撛匾呀?jīng)是最小的。遍歷結(jié)束后，繼續(xù)重復(fù)掃描…… 總共可能進(jìn)行n-1次的遍歷。

如果某次遍歷過(guò)程中，沒(méi)有發(fā)生交換，bingo，這個(gè)數(shù)組已經(jīng)排序好，可以中止排序。如果起始時(shí)，最大的元素位于最左邊，那么冒泡算法必須經(jīng)過(guò)n-1次遍歷才能將數(shù)組排列好，而不能提前完成排序。

/*By Vamei*/
/*swap the neighbors if out of order*/void bubble_sort(int a[], 
int ac)
{    /*use swap*/
    int i,j;    int sign;    for (j = 
0; j < ac-1; j++) {
        sign = 
0;        for(i = ac-1; i > j; i--)
        {            if(a[i-1] > a[i]) {
                sign = 
1;
                swap(a+i, a+i-1);
            }
        }        if (sign == 
0) 
break;
    }
}

插入排序 (Insertion Sort)

假設(shè)在新生報(bào)到的時(shí)候，我們將新生按照身高排好隊(duì)(也就是排序)。如果這時(shí)有一名學(xué)生加入，我們將該名學(xué)生加入到隊(duì)尾。如果這名學(xué)生比前面的學(xué)生低，那么就讓該學(xué)生和前面的學(xué)生交換位置。這名學(xué)生最終會(huì)換到應(yīng)在的位置。這就是插入排序的基本原理。

對(duì)于起始數(shù)組來(lái)說(shuō)，我們認(rèn)為最初，有一名學(xué)生，也就是最左邊的元素(i=0)，構(gòu)成一個(gè)有序的隊(duì)伍。

隨后有第二個(gè)學(xué)生(i=1)加入隊(duì)伍，第二名學(xué)生交換到應(yīng)在的位置；隨后第三個(gè)學(xué)生加入隊(duì)伍，第三名學(xué)生交換到應(yīng)在的位置…… 當(dāng)n個(gè)學(xué)生都加入隊(duì)伍時(shí)，我們的排序就完成了。

/*By Vamei*//*insert the next element 
  into the sorted part*/void insert_sort(int a[], int ac)
{    /*use swap*/
    int i,j;    
    for (j=1; j < ac; j++) 
    {
        i = j-1;        while((i>=0) && (a[i+1] < a[i])) 
        {
            swap(a+i+1, a+i);
            i--;
        }
    }
}

選擇排序 (Selection Sort)

排序的最終結(jié)果：任何一個(gè)元素都不大于位于它右邊的元素 (a[i] <= a[j], if i <= j)。所以，在有序序列中，最小的元素排在最左的位置，第二小的元素排在i=1的位置…… 最大的元素排在最后。

選擇排序是先找到起始數(shù)組中最小的元素，將它交換到i=0；然后尋找剩下元素中最小的元素，將它交換到i=1的位置…… 直到找到第二大的元素，將它交換到n-2的位置。這時(shí)，整個(gè)數(shù)組的排序完成。

/*By Vamei*//*find the smallest of the rest,
  then append to the sorted part*/void select_sort(int a[], int ac) 
{    /*use swap*/
    int i,j;    int min_idx;    for (j = 0; j < ac-1; j++) 
    {
        min_idx = j;        for (i = j+1; i < ac; i++) 
        {            if (a[i] < a[min_idx]) 
            {
                min_idx = i;
            }
        }
        swap(a+j, a+min_idx);
    }    
}

希爾排序 （Shell Sort）

我們?cè)诿芭菖判蛑刑岬剑顗牡那闆r發(fā)生在大的元素位于數(shù)組的起始。這些位于數(shù)組起始的大元素需要多次遍歷，才能交換到隊(duì)尾。這樣的元素被稱為烏龜(turtle)。

烏龜元素的原因在于，冒泡排序總是相鄰的兩個(gè)元素比較并交換。所以每次從右向左遍歷，大元素只能向右移動(dòng)一位。(小的元素位于隊(duì)尾，被稱為兔子(rabbit)元素，它們可以很快的交換到隊(duì)首。)

希爾排序是以更大的間隔來(lái)比較和交換元素，這樣，大的元素在交換的時(shí)候，可以向右移動(dòng)不止一個(gè)位置，從而更快的移動(dòng)烏龜元素。比如，可以將數(shù)組分為4個(gè)子數(shù)組（i=4k, i=4k+1, i=4k+2, i=4k+3），對(duì)每個(gè)子數(shù)組進(jìn)行冒泡排序。比如子數(shù)組i=0，4，8，12...。此時(shí)，每次交換的間隔為4。

完成對(duì)四個(gè)子數(shù)組的排序后，數(shù)組的順序并不一定能排列好。希爾排序會(huì)不斷減小間隔，重新形成子數(shù)組，并對(duì)子數(shù)組冒泡排序…… 當(dāng)間隔減小為1時(shí)，就相當(dāng)于對(duì)整個(gè)數(shù)組進(jìn)行了一次冒泡排序。隨后，數(shù)組的順序就排列好了。

希爾排序不止可以配合冒泡排序，還可以配合其他的排序方法完成。

/*By Vamei*//*quickly sort the turtles at the tail of the array*/void shell_sort(int a[], int ac)
{    int step;    int i,j;    int nsub;    int *sub;    /* initialize step */
    step = 1;    while(step < ac) step = 3*step + 1;    /* when step becomes 1, it's equivalent to the bubble sort*/
    while(step > 1) {       /* step will go down to 1 at most */
       step = step/3 + 1;       for(i=0; i<step; i++) {           /* pick an element every step, 
              and combine into a sub-array */
           nsub = (ac - i - 1)/step + 1;            
           sub = (int *) malloc(sizeof(int)*nsub);           for(j=0; j<nsub; j++) {
               sub[j] = a[i+j*step]; 
           }           /* sort the sub-array by bubble sorting. 
              It could be other sorting methods */
           bubble_sort(sub, nsub);           /* put back the sub-array*/
           for(j=0; j<nsub; j++) {
               a[i+j*step] = sub[j];
           }           /* free sub-array */
           free(sub);
       }    
    }
}

Shell Sorting依賴于間隔(step)的選取。一個(gè)常見(jiàn)的選擇是將本次間隔設(shè)置為上次間隔的1/1.3。見(jiàn)參考書(shū)籍。

歸并排序 (Merge Sort)

如果我們要將一副按照數(shù)字大小排序。此前已經(jīng)有兩個(gè)人分別將其中的一半排好順序。那么我們可以將這兩堆向上放好，假設(shè)小的牌在上面。此時(shí)，我們將看到牌堆中最上的兩張牌。

我們?nèi)蓮埮浦行〉哪菑埲〕龇旁谑种小蓚€(gè)牌堆中又是兩張牌暴露在最上面，繼續(xù)取小的那張放在手中…… 直到所有的牌都放入手中，那么整副牌就排好順序了。這就是歸并排序。

下面的實(shí)現(xiàn)中，使用遞歸：

/*By Vamei*//*recursively merge two sorted arrays*/void merge_sort(int *a, int ac)
{    int i, j, k;    
    int ac1, ac2;    int *ah2, *ah3;    int *container;    /*base case*/    
    if (ac <= 1) return;    /*split the array into two*/
    ac1 = ac/2;
    ac2 = ac - ac1;
    ah2 = a + 0;
    ah3 = a + ac1;    /*recursion*/
    merge_sort(ah2, ac1);
    merge_sort(ah3, ac2); 
    /*merge*/
    i = 0;
    j = 0;
    k = 0;
    container = (int *) malloc(sizeof(int)*ac);    while(i<ac1 && j<ac2) {        if (ah2[i] <= ah3[j]) {
            container[k++] = ah2[i++];
        } 
        else {
            container[k++] = ah3[j++];
        }
    }    while (i < ac1) {
        container[k++] = ah2[i++];
    }    while (j < ac2) {
        container[k++] = ah3[j++];
    }    /*copy back the sorted array*/
    for(i=0; i<ac; i++) {
        a[i] = container[i];
    }    /*free space*/
    free(container);
}

快速排序 (Quick Sort)

我們依然考慮按照身高給學(xué)生排序。在快速排序中，我們隨便挑出一個(gè)學(xué)生，以該學(xué)生的身高為參考(pivot)。然后讓比該學(xué)生低的站在該學(xué)生的右邊，剩下的站在該學(xué)生的左邊。

很明顯，所有的學(xué)生被分成了兩組。該學(xué)生右邊的學(xué)生的身高都大于該學(xué)生左邊的學(xué)生的身高。

我們繼續(xù)，在低身高學(xué)生組隨便挑出一個(gè)學(xué)生，將低身高組的學(xué)生分為兩組(很低和不那么低)。同樣，將高學(xué)生組也分為兩組(不那么高和很高)。

如此繼續(xù)細(xì)分，直到分組中只有一個(gè)學(xué)生。當(dāng)所有的分組中都只有一個(gè)學(xué)生時(shí)，則排序完成。

在下面的實(shí)現(xiàn)中，使用遞歸:

/*By Vamei*//*select pivot, put elements (<= pivot) to the left*/void quick_sort(int a[], int ac)
{    /*use swap*/
    /* pivot is a position, 
       all the elements before pivot is smaller or equal to pvalue */
    int pivot;    /* the position of the element to be tested against pivot */
    int sample;    /* select a pvalue.  
       Median is supposed to be a good choice, but that will itself take time.
       here, the pvalue is selected in a very simple wayi: a[ac/2] */
    /* store pvalue at a[0] */
    swap(a+0, a+ac/2);
    pivot = 1; 
    /* test each element */
    for (sample=1; sample<ac; sample++) {        if (a[sample] < a[0]) {
            swap(a+pivot, a+sample);
            pivot++;
        }
    }    /* swap an element (which <= pvalue) with a[0] */
    swap(a+0,a+pivot-1);    /* base case, if only two elements are in the array,
       the above pass has already sorted the array */
    if (ac<=2) return;    else {        /* recursion */
        quick_sort(a, pivot);
        quick_sort(a+pivot, ac-pivot);
    }
}

理想的pivot是采用分組元素中的中位數(shù)。然而尋找中位數(shù)的算法需要另行實(shí)現(xiàn)。也可以隨機(jī)選取元素作為pivot，隨機(jī)選取也需要另行實(shí)現(xiàn)。為了簡(jiǎn)便，我每次都采用中間位置的元素作為pivot。 

堆排序 (Heap Sort)

堆(heap)是常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。它是一個(gè)有優(yōu)先級(jí)的隊(duì)列。最常見(jiàn)的堆的實(shí)現(xiàn)是一個(gè)有限定操作的Complete Binary Tree。這個(gè)Complete Binary Tree保持堆的特性，也就是父節(jié)點(diǎn)(parent)大于子節(jié)點(diǎn)(children)。因此，堆的根節(jié)點(diǎn)是所有堆元素中最小的。堆定義有插入節(jié)點(diǎn)和刪除根節(jié)點(diǎn)操作，這兩個(gè)操作都保持堆的特性。

我們可以將無(wú)序數(shù)組構(gòu)成一個(gè)堆，然后不斷取出根節(jié)點(diǎn)，最終構(gòu)成一個(gè)有序數(shù)組。

堆的更詳細(xì)描述請(qǐng)閱讀參考書(shū)目。

下面是堆的數(shù)據(jù)結(jié)構(gòu)，以及插入節(jié)點(diǎn)和刪除根節(jié)點(diǎn)操作。你可以很方便的構(gòu)建堆，并取出根節(jié)點(diǎn)，構(gòu)成有序數(shù)組。

/* By Vamei 
   Use an big array to implement heap
   DECLARE: int heap[MAXSIZE] in calling function
   heap[0] : total nodes in the heap
   for a node i, its children are i*2 and i*2+1 (if exists)
   its parent is i/2  */void insert(int new, int heap[]) 
{    int childIdx, parentIdx;
    heap[0] = heap[0] + 1;
    heap[heap[0]] = new;    
    /* recover heap property */
    percolate_up(heap);
}static void percolate_up(int heap[]) {    int lightIdx, parentIdx;
    lightIdx  = heap[0];
    parentIdx = lightIdx/2;    /* lightIdx is root? && swap? */
    while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {        /* swap */
        swap(heap + lightIdx, heap + parentIdx); 
        lightIdx  = parentIdx;
        parentIdx = lightIdx/2;
    }
}int delete_min(int heap[]) 
{    int min;    if (heap[0] < 1) {        /* delete element from an empty heap */
        printf("Error: delete_min from an empty heap.");
        exit(1);
    }    /* delete root 
       move the last leaf to the root */
    min = heap[1];
    swap(heap + 1, heap + heap[0]);
    heap[0] -= 1;    /* recover heap property */
    percolate_down(heap); 
    return min;
}static void percolate_down(int heap[]) {    int heavyIdx;    int childIdx1, childIdx2, minIdx;    int sign; /* state variable, 1: swap; 0: no swap */
    heavyIdx = 1;    do {
        sign     = 0;
        childIdx1 = heavyIdx*2;
        childIdx2 = childIdx1 + 1;        if (childIdx1 > heap[0]) {            /* both children are null */
            break; 
        }        else if (childIdx2 > heap[0]) {            /* right children is null */
            minIdx = childIdx1;
        }        else {
            minIdx = (heap[childIdx1] < heap[childIdx2]) ?
                          childIdx1 : childIdx2;
        }        if (heap[heavyIdx] > heap[minIdx]) {            /* swap with child */
            swap(heap + heavyIdx, heap + minIdx);
            heavyIdx = minIdx;
            sign = 1;
        }
    } while(sign == 1);
}

除了上面的算法，還有諸如Bucket Sorting, Radix Sorting涉及。我會(huì)在未來(lái)實(shí)現(xiàn)了相關(guān)算法之后，補(bǔ)充到這篇文章中。相關(guān)算法的時(shí)間復(fù)雜度分析可以參考書(shū)目中找到。我自己也做了粗糙的分析。如果博客園能支持?jǐn)?shù)學(xué)公式的顯示，我就把自己的分析過(guò)程貼出來(lái)，用于引玉。

上面的各個(gè)代碼是我自己寫(xiě)的，只進(jìn)行了很簡(jiǎn)單的測(cè)試。如果有錯(cuò)漏，先謝謝你的指正。

最后，上文中用到的交換函數(shù)為：

/* By Vamei *//* exchange the values pointed by pa and pb*/void swap(int *pa, int *pb)
{    int tmp;
    tmp = *pa;    *pa = *pb;    *pb = tmp;
}

上述就是小編為大家分享的排序算法及其C實(shí)現(xiàn)是怎樣的了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。