c語言排序方法有：1、簡單選擇排序，基于O（n2）時間復(fù)雜度的排序算法；2、冒泡排序；3、簡單插入排序；4、希爾排序；5、歸并排序，基于歸并操作的一種排序算法；6、快速排序，屬于分治法的一種；7、堆排序等。

本教程操作環(huán)境：windows7系統(tǒng)、C++17版本、Dell G3電腦。

1.選擇排序-簡單選擇排序

選擇排序是最簡單的一種基于O（n2）時間復(fù)雜度的排序算法，基本思想是從i=0位置開始到i=n-1每次通過內(nèi)循環(huán)找出i位置到n-1位置的最?。ù螅┲?。

算法實(shí)現(xiàn)：

void selectSort(int arr[], int n) {    int i, j , minValue, tmp;    for(i = 0; i < n-1; i++)     {         minValue = i;        for(j = i + 1; j < n; j++)         {            if(arr[minValue] > arr[j])             {                 minValue = j;             }         }        if(minValue != i)         {             tmp = arr[i];             arr[i] = arr[minValue];             arr[minValue] = tmp;         }     } }void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n"); }void main() {    int arr[10] = {2,5,6,4,3,7,9,8,1,0};     printArray(arr, 10);     selectSort(arr, 10);     printArray(arr, 10);    return; }

如實(shí)現(xiàn)所示，簡單的選擇排序復(fù)雜度固定為O(n2)，每次內(nèi)循環(huán)找出沒有排序數(shù)列中的最小值，然后跟當(dāng)前數(shù)據(jù)進(jìn)行交換。由于選擇排序通過查找最值的方式排序，循環(huán)次數(shù)幾乎是固定的，一種優(yōu)化方式是每次循環(huán)同時查找最大值和最小值可以是循環(huán)次數(shù)減少為（n/2），只是在循環(huán)中添加了記錄最大值的操作，原理一樣，本文不再對該方法進(jìn)行實(shí)現(xiàn)。

2.冒泡排序

冒泡排序在一組需要排序的數(shù)組中，對兩兩數(shù)據(jù)順序與要求順序相反時，交換數(shù)據(jù)，使大的數(shù)據(jù)往后移，每趟排序?qū)⒆畲蟮臄?shù)放在最后的位置上，如下：

算法實(shí)現(xiàn)：

void bubbleSort(int arr[], int n) {    int i, j, tmp;    for(i = 0; i < n - 1; i++)     {        for(j = 1; j < n; j++)         {            if(arr[j] < arr[j - 1])             {                 tmp = arr[j];                 arr[j] = arr[j - 1];                 arr[j - 1] = tmp;             }         }     } }void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n"); }void main() {    int arr[10] = {2,5,6,4,3,7,9,8,1,0};     printArray(arr, 10);     bubbleSort(arr, 10);     printArray(arr, 10);    return; }

如上是一種最簡單的實(shí)現(xiàn)方式，需要注意的可能是i, j的邊界問題，這種方式固定循環(huán)次數(shù)，肯定可以解決各種情況，不過算法的目的是為了提升效率，根據(jù)冒泡排序的過程圖可以看出這個算法至少可以從兩點(diǎn)進(jìn)行優(yōu)化：
1)對于外層循環(huán)，如果當(dāng)前序列已經(jīng)有序，即不再進(jìn)行交換，應(yīng)該不再進(jìn)行接下來的循環(huán)直接跳出。
2)對于內(nèi)層循環(huán)后面最大值已經(jīng)有序的情況下應(yīng)該不再進(jìn)行循環(huán)。

優(yōu)化代碼實(shí)現(xiàn)：

void bubbleSort_1(int arr[], int n) {    int i, nflag, tmp;    do     {         nflag = 0;        for(i = 0; i < n - 1; i++)         {            if(arr[i] > arr[i + 1])             {                 tmp = arr[i];                 arr[i] = arr[i + 1];                 arr[i + 1] = tmp;                 nflag = i + 1;             }         }         n = nflag;     }while(nflag); }

如上，當(dāng)nflag為0時，說明本次循環(huán)沒有發(fā)生交換，序列已經(jīng)有序不用再循環(huán)，如果nflag>0則記錄了最后一次發(fā)生交換的位置，該位置以后的序列都是有序的，循環(huán)不再往后進(jìn)行。

3.插入排序-簡單插入排序

插入排序是將一個記錄插入到已經(jīng)有序的序列中，得到一個新的元素加一的有序序列，實(shí)現(xiàn)上即將第一個元素看成一個有序的序列，從第二個元素開始逐個插入得到一個完整的有序序列，插入過程如下：

如圖，插入排序第i個元素與相鄰前一個元素比較，如果與排序順序相反則與前一個元素交換位置，循環(huán)直到合適的位置。

算法實(shí)現(xiàn)：

void insertSort(int arr[], int n) {    int i, j, tmp;    for(i = 1; i < n; i++)     {        for(j = i; j > 0; j--)         {            if(arr[j] < arr[j-1])             {                 tmp = arr[j];                 arr[j] = arr[j-1];                 arr[j-1] = tmp;             }            else             {                break;             }         }     }    return; }void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; }void main() {    int arr[10] = {2,5,6,4,3,7,9,8,1,0};     printArray(arr, 10);     insertSort(arr, 10);     printArray(arr, 10);    return; }

如上，前面提到選擇排序不管什么情況下都是固定為O(n2)的算法，插入算法雖然也是O(n2)的算法，不過可以看出，在已經(jīng)有序的情況下，插入可以直接跳出循環(huán)，在極端情況下（完全有序）插入排序可以是O（n）的算法。不過在實(shí)際完全亂序的測試用例中，與本文中的選擇排序相比，相同序列的情況下發(fā)現(xiàn)插入排序運(yùn)行的時間比選擇排序長，這是因?yàn)檫x擇排序每次外循環(huán)只與選擇的最值進(jìn)行交換，而插入排序則需要不停與相鄰元素交換知道合適的位置，交換的三次賦值操作同樣影響運(yùn)行時間，因此下面對這一點(diǎn)進(jìn)行優(yōu)化：

優(yōu)化后實(shí)現(xiàn)：

void insertSort_1(int arr[], int n) {    int i, j, tmp, elem;    for(i = 1; i < n; i++)     {         elem = arr[i];        for(j = i; j > 0; j--)         {            if(elem < arr[j-1])             {                 arr[j] = arr[j-1];             }            else             {                break;             }         }         arr[j] = elem;     }    return; }

優(yōu)化代碼將需要插入的值緩存下來，將插入位置之后的元素向后移一位，將交換的三次賦值改為一次賦值，減少執(zhí)行時間。

4.插入排序-希爾排序

希爾排序的基本思想是先取一個小于n的整數(shù)d1作為第一個增量，把全部元素分組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量d2 < d1重復(fù)上述的分組和排序，直至所取的增量 =1( < …< d2 < d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?，希爾排序主要是根?jù)插入排序的一下兩種性質(zhì)對插入排序進(jìn)行改進(jìn)：

1)插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達(dá)到線性排序的效率。

2)但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位

排序過程如下：

算法實(shí)現(xiàn)：基于一種簡單的增量分組方式｛n/2,n/4,n/8……,1｝

void shellSort(int arr[], int n) {    int i, j, elem;    int k = n/2;    while(k>=1)     {        for(i = k; i < n; i ++)         {             elem = arr[i];            for(j = i; j >= k; j-=k)             {                if(elem < arr[j-k])                 {                     arr[j] = arr[j-k];                 }                else                 {                    break;                 }             }             arr[j] = elem;         }         k = k/2;     } }void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; }void main() {    int arr[10] = {2,5,6,4,3,7,9,8,1,0};     printArray(arr, 10);     shellSort(arr, 10);     printArray(arr, 10);    return; }

5.歸并排序

歸并排序是基于歸并操作的一種排序算法，歸并操作的原理就是將一組有序的子序列合并成一個完整的有序序列，即首先需要把一個序列分成多個有序的子序列，通過分解到每個子序列只有一個元素時，每個子序列都是有序的，在通過歸并各個子序列得到一個完整的序列。

合并過程：

把序列中每個單獨(dú)元素看作一個有序序列，每兩個單獨(dú)序列歸并為一個具有兩個元素的有序序列，每兩個有兩個元素的序列歸并為一個四個元素的序列依次類推。兩個序列歸并為一個序列的方式：因?yàn)閮蓚€子序列都是有序的（假設(shè)由小到大），所有每個子序列最左邊都是序列中最小的值，整個序列最小值只需要比較兩個序列最左邊的值，所以歸并的過程不停取子序列最左邊值中的最小值放到新的序列中，兩個子序列值取完后就得到一個有序的完整序列。

歸并的算法實(shí)現(xiàn)：

void merge(int arr[], int l, int mid, int r) {    int len,i, pl, pr;    int *tmp = NULL;      len = r - l + 1;     tmp = (int*)malloc(len * sizeof(int));  //申請存放完整序列內(nèi)存     memset(tmp, 0x0, len * sizeof(int));      pl = l;     pr = mid + 1;     i  = 0;    while(pl <= mid && pr <= r)  //兩個子序列都有值，比較最小值     {        if(arr[pl] < arr[pr])         {              tmp[i++] = arr[pl++];         }        else         {             tmp[i++] = arr[pr++];         }     }    while(pl <= mid)        //左邊子序列還有值，直接拷貝到新序列中     {         tmp[i++] = arr[pl++];     }    while(pr <= r)      //右邊子序列還有值     {         tmp[i++] = arr[pr++];     }    for(i = 0; i < len; i++)     {         arr[i+l] = tmp[i];     }    free(tmp);    return; }

歸并的迭代算法：

迭代算法如上面所說，從單個元素開始合并，子序列長度不停增加直到得到一個長度為n的完整序列。

#include<stdio.h>#include<stdlib.h>#include<string.h>void merge(int arr[], int l, int mid, int r) {    int len,i, pl, pr;    int *tmp = NULL;      len = r - l + 1;     tmp = (int*)malloc(len * sizeof(int));  //申請存放完整序列內(nèi)存     memset(tmp, 0x0, len * sizeof(int));      pl = l;     pr = mid + 1;     i  = 0;    while(pl <= mid && pr <= r)  //兩個子序列都有值，比較最小值     {        if(arr[pl] < arr[pr])         {              tmp[i++] = arr[pl++];         }        else         {             tmp[i++] = arr[pr++];         }     }    while(pl <= mid)        //左邊子序列還有值，直接拷貝到新序列中     {         tmp[i++] = arr[pl++];     }    while(pr <= r)      //右邊子序列還有值     {         tmp[i++] = arr[pr++];     }    for(i = 0; i < len; i++)     {         arr[i+l] = tmp[i];     }    free(tmp);    return;  }int min(int x, int y) {    return (x > y)? y : x; }/* 歸并完成的條件是得到子序列長度等于n，用sz表示當(dāng)前子序列的長度。從1開始每次翻倍直到等于n。根據(jù)上面歸并的方法，從i=0開始分組，下一組坐標(biāo)應(yīng)該i + 2*sz，第i組第一個元素為arr[i],最右邊元素應(yīng)該為arr[i+2*sz -1]，遇到序列最右邊元素不夠分組的元素個數(shù)時應(yīng)該取n-1,中間的元素為arr[i+sz -1],依次類推進(jìn)行歸并得到完整的序列 */void mergeSortBu(int arr[], int n) {    int sz, i, mid,l, r;    for(sz = 1; sz < n; sz+=sz)     {        for(i = 0; i < n - sz; i += 2*sz)         {             l = i;             r = i + sz + sz;             mid = i + sz -1;             merge(arr, l, mid, min(r-1, n-1));         }     }    return; }void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; }void main() {    int arr[10] = {2,5,6,4,3,7,9,8,1,0};     printArray(arr, 10);     mergeSortBu(arr, 10);     printArray(arr, 10);    return; }

另一種是通過遞歸的方式，遞歸方式可以理解為至頂向下的操作，即先將完整序列不停分解為子序列，然后在將子序列歸并為完整序列。

遞歸算法實(shí)現(xiàn)：

void mergeSort(int arr[], int l, int r) {    if(l >= r)     {         return;     }    int mid = (l + r)/2;     mergeSort(arr, l, mid);     mergeSort(arr, mid+1, r);     merge(arr, l, mid, r);     return; }

對于歸并算法大家可以考慮到由于子序列都是有序的，所有如果左邊序列的最大值都比右邊序列的最小值小，那么整個序列就是有序的，不需要進(jìn)行merge操作，因此可以在每次merge操作加一個if(arr[mid] > arr[mid+1])判斷進(jìn)行優(yōu)化,這種優(yōu)化對于近乎有序的序列非常有效果，不過對于一般的情況會有一次判斷的額外開銷，可以根據(jù)具體情況處理。

6.快速排序

快速排序跟歸并排序類似屬于分治法的一種，基本思想是通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。

排序過程如圖：

因此，快速排序每次排序?qū)⒁粋€序列分為兩部分，左邊部分都小于等于右邊部分，然后在遞歸對左右兩部分進(jìn)行快速排序直到每部分元素個數(shù)為1時則整個序列都是有序的，因此快速排序主要問題在怎樣將一個序列分成兩部分，其中一部分所有元素都小于另一部分，對于這一塊操作我們叫做partition,原理是先選取序列中的一個元素做參考量，比它小的都放在序列左邊，比它大的都放在序列右邊。

算法實(shí)現(xiàn)：

快速排序-單路快排：

如上：我們選取第一個元素v作為參考量及arr[l],定義j變量為兩部分分割哨兵，變量i從l+1開始遍歷每個變量，如果當(dāng)前變量e > v則i++檢測下一個元素，如果當(dāng)前變量e < v 則e與arr[j+1]交換，可以看到arr[j+1]由交換前大于v變成小于v arr[i]變成大于v，同時對i++，j++，始終保持：arr[l+1….j] < v, arr[j+1….i-1] > v

代碼實(shí)現(xiàn)：

#include <stdio.h>void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; }void swap(int *a, int *b) {    int tmp;      tmp = *a;     *a  = *b;     *b  = tmp;    return; }//arr[l+1...j] < arr[l], arr[j+1,..i)>arr[l]static int partition(int arr[], int l, int r) {    int i, j;     i = l + 1;     j = l;    while(i <= r)     {        if(arr[i] > arr[l])         {             i++;         }        else         {             swap(&arr[j + 1], &arr[i]);             i++;             j++;         }     }     swap(&arr[l], &arr[j]);    return j; }static void _quickSort(int arr[], int l, int r) {    int key;    if(l >= r)     {        return;     }     key = partition(arr, l, r);     _quickSort(arr, l, key - 1);     _quickSort(arr, key + 1, r); }void quickSort(int arr[], int n) {     _quickSort(arr, 0, n - 1);    return; }void main() {    int arr[10] = {1,5,9,8,7,6,3,4,0,2};      printArray(arr, 10);     quickSort(arr, 10);     printArray(arr, 10); }

因?yàn)橛凶兞縤從左到右依次遍歷序列元素，所有這種方式叫單路快排，不過細(xì)心的同學(xué)可以發(fā)現(xiàn)我們忽略了考慮e等于v的情況，這種快排方式一大缺點(diǎn)就是對于高重復(fù)率的序列即大量e等于v的情況會退化為O（n2）算法，原因在大量e等于v的情況劃分情況會如下圖兩種情況：

解決這種問題的一另種方法：

快速排序-兩路快排：

兩路快排通過i和j同時向中間遍歷元素，e==v的元素分布在左右兩個部分，不至于在多重復(fù)元素時劃分嚴(yán)重失衡。依舊去第一個元素arr[l]為參考量，始終保持arr[l+1….i) <= arr[l], arr(j…r] >=arr[l]原則.

代碼實(shí)現(xiàn)：

//arr[l+1....i) <=arr[l], arr(j...r] >=arr[l]static int partition2(int arr[], int l, int r) {    int i, j;      i = l + 1 ;     j = r;    while(i <= j)     {        while(i <= j && arr[j] > arr[l])         /*注意arr[j] >arr[l] 不是arr[j] >= arr[l]*/         {             j--;         }        while(i <= j && arr[i] < arr[l])         {             i++;         }        if(i < j)         {             swap(&arr[i], &arr[j]);             i++;             j--;         }     }     swap(&arr[j],&arr[l]);    return j; }

針對重復(fù)元素比較多的情況還有一種實(shí)現(xiàn)方式：

快速排序-三路快排：

三路快排是在兩路快排的基礎(chǔ)上對e==v的情況做單獨(dú)的處理，對于重復(fù)元素非常多的情況優(yōu)勢很大：

如上：取arr[l]為參考量，定義變量lt為小于v和等于v的分割點(diǎn)，變量i為遍歷指針，gt為大于v和未遍歷元素分割點(diǎn)，gt指向未遍歷元素，邊界條件跟個人定義有關(guān)本文始終保持arr[l+1…lt] < v,arr[lt+1….i-1],arr(gt…..r]>v的狀態(tài)。

代碼實(shí)現(xiàn)：

#include <stdio.h>void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; } void swap(int *a, int *b) {    int tmp;      tmp = *a;    *a  = *b;    *b  = tmp;    return; }  static void _quickSort3(int arr [ ],int l,int r) {    int i, lt, gt;    if(l >= r)     {        return;     }     i = l + 1;    lt = l;    gt = r ;    while(i <= gt)     {        if(arr[i] < arr[l])         {             swap(&arr[lt + 1], &arr[i]);            lt ++;             i++;         }        else if(arr[i] > arr[l])         {             swap(&arr[i], &arr[gt]);            gt--;         }        else         {             i++;         }     }      swap(&arr[l], &arr[gt]);     _quickSort3(arr, l, lt);     _quickSort3(arr, gt + 1, r);    return; }  void quickSort(int arr[], int n) {     _quickSort3(arr, 0, n - 1);    return; }  void main() {    int arr[10] = {1,5,9,8,7,6,3,4,0,2};      printArray(arr, 10);     quickSort(arr, 10);     printArray(arr, 10); }

三路快排在重復(fù)率比較高的情況下比前兩種有較大優(yōu)勢，但就完全隨機(jī)情況略差于兩路快排，可以根據(jù)具體情況進(jìn)行合理選擇，另外本文在選取參考值時為了方便一直選擇第一個元素為參考值，這種方式對于近乎有序的序列算法會退化到O（n2），因此一般選取參考值可以隨機(jī)選擇參考值或者其他選擇參考值的方法然后再與arr[l]交換，依舊可以使用相同的算法。

7.堆排序

堆其實(shí)一種樹形結(jié)構(gòu)，以二叉堆為例，是一顆完全二叉樹（即除最后一層外每個節(jié)點(diǎn)都有兩個子節(jié)點(diǎn)，且非滿的二叉樹葉節(jié)點(diǎn)都在最后一層的左邊位置），二叉樹滿足每個節(jié)點(diǎn)都大于等于他的子節(jié)點(diǎn)(大頂堆)或者每個節(jié)點(diǎn)都小于等于他的子節(jié)點(diǎn)（小頂堆），根據(jù)堆的定義可以得到堆滿足頂點(diǎn)一定是整個序列的最大值（大頂堆）或者最小值（小頂堆）。如下圖：

堆排序就是一種基于堆得選擇排序，先將需要排序的序列構(gòu)建成堆，在每次選取堆頂點(diǎn)的最大值和最小值知道完成整個堆的遍歷。

用數(shù)組表示堆：

二叉堆作為樹的一種，通常用結(jié)構(gòu)體表示，為了排序的方便，我們通常使用數(shù)組來表示堆，如下圖：

將一個堆按圖中的方式按層編號可以得到如下結(jié)論：

1）節(jié)點(diǎn)的父節(jié)點(diǎn)編號滿足parent(i) = i/2

2）節(jié)點(diǎn)的左孩子編號滿足 left child (i) = 2*i

3）節(jié)點(diǎn)右孩子滿足 right child (i) = 2*i + 1

由于數(shù)組編號是從0開始對上面結(jié)論修改得到：

parent(i) = (i-1)/2

left child (i) = 2*i + 1

right child (i) = 2*i + 2

堆的兩種操作方式：

根據(jù)堆的主要性質(zhì)（父節(jié)點(diǎn)大于兩個子節(jié)點(diǎn)或者小于兩個子節(jié)點(diǎn)），可以得到堆的兩種主要操作方式，以大頂堆為例：

a）如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)將子節(jié)點(diǎn)上移（shift up）

b）如果父節(jié)點(diǎn)小于兩個子節(jié)點(diǎn)中的最大值則父節(jié)點(diǎn)下移（shift down）

shift up:

如果往已經(jīng)建好的堆中添加一個元素，如下圖，此時不再滿足堆的性質(zhì)，堆遭到破壞，就需要執(zhí)行shift up 操作將添加的元素上移調(diào)整直到滿足堆的性質(zhì)。

調(diào)整堆的方法：

1）7號位新增元素48與其父節(jié)點(diǎn)[i/2]=3比較大于父節(jié)點(diǎn)的32不滿足堆性質(zhì)，將其與父節(jié)點(diǎn)交換。

2）此時新增元素在3號位，再與3號位父節(jié)點(diǎn)[i/2]=1比較，小于1號位的62滿足堆性質(zhì)，不再交換，如果此步驟依舊不滿足堆性質(zhì)則重復(fù)1步驟直到滿足堆的性質(zhì)或者到根節(jié)點(diǎn)。

3）堆調(diào)整完成。

代碼實(shí)現(xiàn)：

代碼中基于數(shù)組實(shí)現(xiàn)，數(shù)組下表從0開始，父子節(jié)點(diǎn)關(guān)系如用數(shù)組表示堆

/*parent(i) = (i-1)/2   left child  (i) = 2*i + 1   right child (i) = 2*i + 2*/void swap(int *a, int *b) {    int tmp;      tmp = *a;    *a  = *b;    *b  = tmp;    return; }   void shiftUp(int arr[], int n, int k)  {    while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2])     {         swap(&arr[k], &arr[(k-1)/2]);         k = (k - 1)/2;     }    return;  }

shift down:

與shift up相反，如果從一個建好的堆中刪除一個元素，此時不再滿足堆的性質(zhì)，此時應(yīng)該怎樣來調(diào)整堆呢？

如上圖，將堆中根節(jié)點(diǎn)元素62刪除調(diào)整堆的步驟為：

1）將最后一個元素移到刪除節(jié)點(diǎn)的位置

2）與刪除節(jié)點(diǎn)兩個子節(jié)點(diǎn)中較大的子節(jié)點(diǎn)比較，如果節(jié)點(diǎn)小于較大的子節(jié)點(diǎn)，與子節(jié)點(diǎn)交換，否則滿足堆性質(zhì)，完成調(diào)整。

3）重復(fù)步驟2，直到滿足堆性質(zhì)或者已經(jīng)為葉節(jié)點(diǎn)。

4）完成堆調(diào)整

代碼實(shí)現(xiàn)：

 void shiftDown(int arr[], int n, int k)  {    int j = 0 ;     while(2*k + 1 < n)      {         j = 2 *k + 1;    //標(biāo)記兩個子節(jié)點(diǎn)較大的節(jié)點(diǎn)，初始為左節(jié)點(diǎn)         if (j + 1 < n && arr[j] < arr[j+1])         {             j ++;            }        if(arr[k] < arr[j])         {             swap(&arr[k], &arr[j]);             k = j;         }        else         {            break;         }      }     return;  }

知道了上面兩種堆的操作后，堆排序的過程就非常簡單了

1）首先將待排序序列建成堆，由于最后一層即葉節(jié)點(diǎn)沒有子節(jié)點(diǎn)所以可以看成滿足堆性質(zhì)的節(jié)點(diǎn)，第一個可能出現(xiàn)不滿足堆性質(zhì)的節(jié)點(diǎn)在第一個父節(jié)點(diǎn)的位置，假設(shè)最后一個葉子節(jié)點(diǎn)為（n – 1） 則第一個父節(jié)點(diǎn)位置為(n-1-1)/2,只需要依次對第一個父節(jié)點(diǎn)之前的節(jié)點(diǎn)執(zhí)行shift down操作到根節(jié)點(diǎn)后建堆完成。

2）建堆完成后（以大頂堆為例）第一個元素arr[0]必定為序列中最大值，將最大值提取出來（與數(shù)組最后一個元素交換），此時堆不再滿足堆性質(zhì)，再對根節(jié)點(diǎn)進(jìn)行shift down操作，依次循環(huán)直到根節(jié)點(diǎn)，排序完成。

代碼實(shí)現(xiàn)：

#include<stdio.h>/*parent(i) = (i-1)/2   left child  (i) = 2*i + 1   right child (i) = 2*i + 2*/void swap(int *a, int *b) {    int tmp;      tmp = *a;    *a  = *b;    *b  = tmp;    return; }   void shiftUp(int arr[], int n, int k)  {    while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2])     {         swap(&arr[k], &arr[(k-1)/2]);         k = (k - 1)/2;     }    return;  }   void shiftDown(int arr[], int n, int k)  {    int j = 0 ;     while(2*k + 1 < n)      {         j = 2 *k + 1;        if (j + 1 < n && arr[j] < arr[j+1])         {             j ++;            }        if(arr[k] < arr[j])         {             swap(&arr[k], &arr[j]);             k = j;         }        else         {            break;         }      }     return;  }   void heapSort(int arr[], int n)  {    int i = 0;    for(i = (n - 1 -1)/2; i >=0; i--)     {         shiftDown(arr, n, i);     }    for(i = n - 1; i > 0; i--)     {         swap(&arr[0], &arr[i]);         shiftDown(arr, i, 0);     }    return;  }   void printArray(int arr[], int n) {    int i;    for(i = 0; i < n; i++)     {        printf("%d ", arr[i]);     }    printf("n");    return; }  void main() {    int arr[10] = {1,5,9,8,7,6,3,4,0,2};      printArray(arr, 10);     heapSort(arr, 10);     printArray(arr, 10); }

推薦教程：《C#》