八大排序算法

1、八大排序排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。 我們這里說說八大排序就是內(nèi)部排序。         當(dāng)n較大，則應(yīng)采用時間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。   快速排序：是目前基于比較的內(nèi)部排序中被認為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短； 1.插入排序直接插入排序(Straight Insertion Sort)

2、基本思想:將一個記錄插入到已排序好的有序表中，從而得到一個新記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。要點：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。直接插入排序示例：如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。算法的實現(xiàn)：cpp view plaincopyprint?void print(int a, int n ,int i

3、)      cout<<i <<":"      for(int j= 0; j<8; j+)          cout<<aj <<" "      

4、      cout<<endl;        void InsertSort(int a, int n)        for(int i= 1; i<n; i+)         

5、60;if(ai < ai-1)               /若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入              int j= i-1;       &

6、#160;       int x = ai;        /復(fù)制為哨兵，即存儲待排序元素              ai = ai-1;          

7、 /先后移一個元素              while(x < aj)  /查找在有序表的插入位置                  aj+1 = aj;    

8、              j-;         /元素后移                         

9、0;  aj+1 = x;      /插入到正確位置                    print(a,n,i);           /打印每趟排序的結(jié)果  &#

10、160;               int main()      int a8 = 3,1,5,7,2,4,9,6;      InsertSort(a,8);      print(a,8,8);  &#

11、160; void print(int a, int n ,int i)cout<<i <<":"for(int j= 0; j<8; j+)cout<<aj <<" "cout<<endl;void InsertSort(int a, int n)for(int i= 1; i<n; i+)if(ai < ai-1) /若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入int j= i-1;int x = ai; /復(fù)制為哨兵，即存儲待排序元素ai =

12、 ai-1; /先后移一個元素while(x < aj) /查找在有序表的插入位置aj+1 = aj;j-; /元素后移aj+1 = x; /插入到正確位置print(a,n,i);/打印每趟排序的結(jié)果int main()int a8 = 3,1,5,7,2,4,9,6;InsertSort(a,8);print(a,8,8);效率：時間復(fù)雜度：O（n2）.其他的插入排序有二分插入排序，2-路插入排序。  2. 插入排序希爾排序（Shells Sort）希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序基本思想：先

13、將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。操作方法：選擇一個增量序列t1，t2，tk，其中ti>tj，tk=1； 按增量序列個數(shù)k，對序列進行k 趟排序； 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。希爾排序的示例：算法實現(xiàn)： 我們簡單處理增量序列：增量序列d = n/2 ,n/4, n/8 .1 n為要排序數(shù)的個數(shù)即：先將要排序的一組記錄按某個增量d（n/2,n為

14、要排序數(shù)的個數(shù)）分成若干組子序列，每組中記錄的下標(biāo)相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。cpp view plaincopyprint?void print(int a, int n ,int i)      cout<<i <<":"    

15、0; for(int j= 0; j<8; j+)          cout<<aj <<" "            cout<<endl;    /*  * 直接插入排序的

16、一般形式  *  * param int dk 縮小增量，如果是直接插入排序，dk=1  *  */    void ShellInsertSort(int a, int n, int dk)        for(int i= dk; i<n; +i)

17、          if(ai < ai-dk)          /若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入              int j = i-dk; &#

18、160;               int x = ai;           /復(fù)制為哨兵，即存儲待排序元素              ai = 

19、ai-dk;         /首先后移一個元素              while(x < aj)     /查找在有序表的插入位置             &

20、#160;    aj+dk = aj;                  j -= dk;             /元素后移       

21、;                     aj+dk = x;            /插入到正確位置            &

22、#160;       print(a, n,i );                  /*  * 先按增量d（n/2,n為要排序數(shù)的個數(shù)進行希爾排序  *  */  void shellSort(int a,

23、0;int n)        int dk = n/2;      while( dk >= 1  )          ShellInsertSort(a, n, dk);     

24、0;    dk = dk/2;          int main()      int a8 = 3,1,5,7,2,4,9,6;      /ShellInsertSort(a,8,1); /直接插入排序     

25、 shellSort(a,8);           /希爾插入排序      print(a,8,8);    void print(int a, int n ,int i)cout<<i <<":"for(int j= 0; j<8; j+)cout<<aj <<" "cout&l

26、t;<endl;/* * 直接插入排序的一般形式 * * param int dk 縮小增量，如果是直接插入排序，dk=1 * */void ShellInsertSort(int a, int n, int dk)for(int i= dk; i<n; +i)if(ai < ai-dk)/若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入int j = i-dk;int x = ai;/復(fù)制為哨兵，即存儲待排序元素ai = ai-dk;/首先后移一個元素while(x < aj)/查找在有序表的插入位置aj+dk = aj;j -= dk; /元素后移a

27、j+dk = x;/插入到正確位置print(a, n,i );/* * 先按增量d（n/2,n為要排序數(shù)的個數(shù)進行希爾排序 * */void shellSort(int a, int n)int dk = n/2;while( dk >= 1 )ShellInsertSort(a, n, dk);dk = dk/2;int main()int a8 = 3,1,5,7,2,4,9,6;/ShellInsertSort(a,8,1); /直接插入排序shellSort(a,8); /希爾插入排序print(a,8,8);希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于增量因子序

28、列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。3. 選擇排序簡單選擇排序（Simple Selection Sort）基本思想：在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。簡單選擇排序的示例： 

29、;操作方法：第一趟，從n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；以此類推.第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關(guān)鍵碼最小的記錄與第i 個記錄交換，直到整個序列按關(guān)鍵碼有序。算法實現(xiàn)：cpp view plaincopyprint?void print(int a, int n ,int i)      cout<<"第"<<

30、i+1 <<"趟 : "      for(int j= 0; j<8; j+)          cout<<aj <<"  "          

31、0; cout<<endl;    /*  * 數(shù)組的最小值  *  * return int 數(shù)組的鍵值  */  int SelectMinKey(int a, int n, int i)        int k = i;

32、      for(int j=i+1 j< n; +j)           if(ak > aj) k = j;            return k;   &#

33、160;  /*  * 選擇排序  *  */  void selectSort(int a, int n)      int key, tmp;      for(int i = 0; i< n; +i)   &

34、#160;       key = SelectMinKey(a, n,i);           /選擇最小的元素          if(key != i)         &

35、#160;    tmp = ai;  ai = akey; akey = tmp; /最小元素與第i位置元素互換                    print(a,  n , i);  

36、0;       int main()      int a8 = 3,1,5,7,2,4,9,6;      cout<<"初始值："      for(int j= 0; j<8; j+)   &#

37、160;      cout<<aj <<"  "            cout<<endl<<endl;      selectSort(a, 8);      print(a,8,8);

38、    void print(int a, int n ,int i)cout<<"第"<<i+1 <<"趟 : "for(int j= 0; j<8; j+)cout<<aj <<" "cout<<endl;/* * 數(shù)組的最小值 * * return int 數(shù)組的鍵值 */int SelectMinKey(int a, int n, int i)int k = i;for(int j=i+1 ;j< n;

39、+j) if(ak > aj) k = j;return k;/* * 選擇排序 * */void selectSort(int a, int n)int key, tmp;for(int i = 0; i< n; +i) key = SelectMinKey(a, n,i); /選擇最小的元素if(key != i)tmp = ai; ai = akey; akey = tmp; /最小元素與第i位置元素互換print(a, n , i);int main()int a8 = 3,1,5,7,2,4,9,6;cout<<"初始值："for(int

40、j= 0; j<8; j+)cout<<aj <<" "cout<<endl<<endl;selectSort(a, 8);print(a,8,8); 簡單選擇排序的改進二元選擇排序簡單選擇排序，每趟循環(huán)只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環(huán)確定兩個元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進后對n個數(shù)據(jù)進行排序，最多只需進行n/2趟循環(huán)即可。具體實現(xiàn)如下：cpp view plaincopyprint?void SelectSort(int r,i

41、nt n)       int i ,j , min ,max, tmp;      for (i=1 i <= n/2;i+)             / 做不超過n/2趟選擇排序  

42、0;        min = i; max = i  /分別記錄最大和最小關(guān)鍵字記錄位置          for (j= i+1; j<= n-i; j+)           &

43、#160;   if (rj > rmax)                    max = j  continue              

44、0;                 if (rj< rmin)                    min = j     

45、60;                               /該交換操作還可分情況討論以提高效率        tmp = ri-1; ri-1 = r

46、min; rmin = tmp;        tmp = rn-i; rn-i = rmax; rmax = tmp;              void SelectSort(int r,int n) int i ,j , min ,max, tmp;for (i=

47、1 ;i <= n/2;i+) / 做不超過n/2趟選擇排序 min = i; max = i ; /分別記錄最大和最小關(guān)鍵字記錄位置for (j= i+1; j<= n-i; j+) if (rj > rmax) max = j ; continue ; if (rj< rmin) min = j ; /該交換操作還可分情況討論以提高效率 tmp = ri-1; ri-1 = rmin; rmin = tmp; tmp = rn-i; rn-i = rmax; rmax = tmp; 4. 選擇排序堆排序（Heap Sort）堆排序是一種樹形選擇排序，是對直接選擇排序

48、的有效改進?；舅枷耄憾训亩x如下：具有n個元素的序列（k1,k2,.,kn),當(dāng)且僅當(dāng)滿足時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值，根結(jié)點（堆頂元素）的值是最小(或最大)的。如：（a）大頂堆序列：（96, 83,27,38,11,09)  (b)  小頂堆序列：（12，36，24，85，47，30，53，91）初始時把要排序的n個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調(diào)整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到

49、n 個元素中最小(或最大)的元素，這時堆的根節(jié)點的數(shù)最?。ɑ蛘咦畲螅?。然后對前面(n-1)個元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的有序序列。稱這個過程為堆排序。因此，實現(xiàn)堆排序需解決兩個問題：1. 如何將n 個待排序的數(shù)建成堆；2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個元素，使其成為一個新堆。首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調(diào)整過程。調(diào)整小頂堆的方法：1）設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂（最后一個元素與堆頂進行交換

50、），堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。2）將根結(jié)點與左、右子樹中較小元素的進行交換。3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點不滿足堆的性質(zhì)，則重復(fù)方法 （2）.4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點不滿足堆的性質(zhì)。則重復(fù)方法 （2）.5）繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。如圖：再討論對n 個元素初始建堆的過程。建堆方法：對初始序列建堆的過程，就是一個反復(fù)進行篩選的過程。1）n 個結(jié)點的完全二叉樹，則最后一個結(jié)點是第個結(jié)點的子樹。2）篩選從第個結(jié)點為根的子樹開始，該子樹成為堆。3）

51、之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(jié)點。如圖建堆初始過程：無序序列：（49，38，65，97，76，13，27，49）                                       

52、                       算法的實現(xiàn)：從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)。cpp view plaincopyprint?void print(int a, int n) 

53、0;    for(int j= 0; j<n; j+)          cout<<aj <<"  "            cout<<endl;    

54、0;     /*  * 已知Hsm除了Hs 外均滿足堆的定義  * 調(diào)整Hs,使其成為大頂堆.即將對第s個結(jié)點為根的子樹篩選,   *  * param H是待調(diào)整的堆數(shù)組  * param s是待調(diào)整的數(shù)組元素的位置  * param length是數(shù)組的長度  *  */ 

55、 void HeapAdjust(int H,int s, int length)        int tmp  = Hs;      int child = 2*s+1; /左孩子結(jié)點的位置。(i+1 為當(dāng)前調(diào)整結(jié)點的右孩子結(jié)點的位置)      

56、;while (child < length)           if(child+1 <length && Hchild<Hchild+1)  / 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點大的孩子結(jié)點)             &

57、#160;+child                     if(Hs<Hchild)   / 如果較大的子結(jié)點大于父結(jié)點              Hs = Hchild;

58、60;/ 那么把較大的子結(jié)點往上移動，替換它的父結(jié)點              s = child;       / 重新設(shè)置s ,即待調(diào)整的下一個結(jié)點的位置              child&#

59、160;= 2*s+1;            else             / 如果當(dāng)前待調(diào)整結(jié)點大于它的左右孩子，則不需要調(diào)整，直接退出               bre

60、ak;                    Hs = tmp;         / 當(dāng)前待調(diào)整的結(jié)點放到比其大的孩子結(jié)點位置上            prin

61、t(H,length);        /*  * 初始堆進行調(diào)整  * 將H0.length-1建成堆  * 調(diào)整完之后第一個元素是序列的最小的元素  */  void BuildingHeap(int H, int length)         /最后一

62、個有孩子的節(jié)點的位置 i=  (length -1) / 2      for (int i = (length -1) / 2  i >= 0; -i)          HeapAdjust(H,i,length);   

63、; /*  * 堆排序算法  */  void HeapSort(int H,int length)        /初始堆      BuildingHeap(H, length);      /從最后一個元素開始對序列進行調(diào)整    &

64、#160; for (int i = length - 1; i > 0; -i)                /交換堆頂元素H0和堆中最后一個元素          int temp = H

65、i; Hi = H0; H0 = temp;          /每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調(diào)整          HeapAdjust(H,0,i);           int main()

66、      int H10 = 3,1,5,7,2,4,9,6,10,8;      cout<<"初始值："      print(H,10);      HeapSort(H,10);      /selectSort(a, 

67、;8);      cout<<"結(jié)果："      print(H,10);      void print(int a, int n)for(int j= 0; j<n; j+)cout<<aj <<" "cout<<endl;/* * 已知Hsm除了Hs 外均滿足堆的定義 * 調(diào)整Hs,使其成為大頂堆.即將對第s個結(jié)點

68、為根的子樹篩選, * * param H是待調(diào)整的堆數(shù)組 * param s是待調(diào)整的數(shù)組元素的位置 * param length是數(shù)組的長度 * */void HeapAdjust(int H,int s, int length)int tmp = Hs;int child = 2*s+1; /左孩子結(jié)點的位置。(i+1 為當(dāng)前調(diào)整結(jié)點的右孩子結(jié)點的位置) while (child < length) if(child+1 <length && Hchild<Hchild+1) / 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點大的孩子結(jié)點)+child ;if

69、(Hs<Hchild) / 如果較大的子結(jié)點大于父結(jié)點Hs = Hchild; / 那么把較大的子結(jié)點往上移動，替換它的父結(jié)點s = child; / 重新設(shè)置s ,即待調(diào)整的下一個結(jié)點的位置child = 2*s+1; else / 如果當(dāng)前待調(diào)整結(jié)點大于它的左右孩子，則不需要調(diào)整，直接退出 break;Hs = tmp;/ 當(dāng)前待調(diào)整的結(jié)點放到比其大的孩子結(jié)點位置上print(H,length);/* * 初始堆進行調(diào)整 * 將H0.length-1建成堆 * 調(diào)整完之后第一個元素是序列的最小的元素 */void BuildingHeap(int H, int length) /最后

70、一個有孩子的節(jié)點的位置 i= (length -1) / 2for (int i = (length -1) / 2 ; i >= 0; -i)HeapAdjust(H,i,length);/* * 堆排序算法 */void HeapSort(int H,int length) /初始堆BuildingHeap(H, length);/從最后一個元素開始對序列進行調(diào)整for (int i = length - 1; i > 0; -i)/交換堆頂元素H0和堆中最后一個元素int temp = Hi; Hi = H0; H0 = temp;/每次交換堆頂元素和堆中最后一個元素之后，都

71、要對堆進行調(diào)整HeapAdjust(H,0,i); int main()int H10 = 3,1,5,7,2,4,9,6,10,8;cout<<"初始值："print(H,10);HeapSort(H,10);/selectSort(a, 8);cout<<"結(jié)果："print(H,10);分析:設(shè)樹深度為k，。從根到葉的篩選，元素比較次數(shù)至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：        

72、60;                        而建堆時的比較次數(shù)不超過4n 次，因此堆排序最壞情況下，時間復(fù)雜度也為：O(nlogn )。 5. 交換排序冒泡排序（Bubble Sort）基本思想：在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)

73、現(xiàn)它們的排序與排序要求相反時，就將它們互換。冒泡排序的示例： 算法的實現(xiàn)：cpp view plaincopyprint?void bubbleSort(int a, int n)      for(int i =0  i< n-1; +i)           for(int j =

74、0;0; j < n-i-1; +j)               if(aj > aj+1)                       

75、0;        int tmp = aj  aj = aj+1   aj+1 = tmp;                         

76、60;        void bubbleSort(int a, int n)for(int i =0 ; i< n-1; +i) for(int j = 0; j < n-i-1; +j) if(aj > aj+1)int tmp = aj ; aj = aj+1 ; aj+1 = tmp;冒泡排序算法的改進對冒泡排序常見的改進方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換，如果進行某一趟排序時并沒有進行數(shù)據(jù)交換，則說明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免

77、不必要的比較過程。本文再提供以下兩種改進算法：1設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。改進后算法如下:cpp view plaincopyprint?void Bubble_1 ( int r, int n)       int i= n -1;  /初始時,最后位置保持不變  

78、0;   while ( i> 0)            int pos= 0; /每趟開始時,無記錄交換          for (int j= 0; j< i; j+)   

79、60;          if (rj> rj+1)                   pos= j; /記錄交換的位置            

80、;       int tmp = rj; rj=rj+1;rj+1=tmp;                         i= pos; /為下一趟排序作準(zhǔn)備    

81、0;         void Bubble_1 ( int r, int n) int i= n -1; /初始時,最后位置保持不變while ( i> 0) int pos= 0; /每趟開始時,無記錄交換for (int j= 0; j< i; j+)if (rj> rj+1) pos= j; /記錄交換的位置 int tmp = rj; rj=rj+1;rj+1=tmp; i= pos; /為下一趟排序作準(zhǔn)備 2傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用

82、在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。改進后的算法實現(xiàn)為:cpp view plaincopyprint?void Bubble_2 ( int r, int n)      int low = 0;       int high= n -1; /設(shè)置變量的初始

83、值      int tmp,j;      while (low < high)           for (j= low; j< high; +j) /正向冒泡,找到最大者      

84、0;       if (rj> rj+1)                   tmp = rj; rj=rj+1;rj+1=tmp;            &#

85、160;            -high;                 /修改high值, 前移一位          for ( j=high; j>low

86、; -j) /反向冒泡,找到最小者              if (rj<rj-1)                   tmp = rj; rj=rj-1;rj-1=tmp;  &

87、#160;                     +low;                  /修改low值,后移一位       &#

88、160;    void Bubble_2 ( int r, int n)int low = 0; int high= n -1; /設(shè)置變量的初始值int tmp,j;while (low < high) for (j= low; j< high; +j) /正向冒泡,找到最大者if (rj> rj+1) tmp = rj; rj=rj+1;rj+1=tmp; -high;/修改high值, 前移一位for ( j=high; j>low; -j) /反向冒泡,找到最小者if (rj<rj-1) tmp = rj; rj=

89、rj-1;rj-1=tmp;+low;/修改low值,后移一位 6. 交換排序快速排序（Quick Sort）基本思想：1）選擇一個基準(zhǔn)元素,通常選擇第一個元素或者最后一個元素,2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的 元素值比基準(zhǔn)值大。3）此時基準(zhǔn)元素在其排好序后的正確位置4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進行排序，直到整個序列有序。快速排序的示例：（a）一趟排序的過程：（b）排序的全過程算法的實現(xiàn)： 遞歸實現(xiàn)：cpp view plaincopyprint?void print(int&#

90、160;a, int n)      for(int j= 0; j<n; j+)          cout<<aj <<"  "            cout<<

91、endl;      void swap(int *a, int *b)        int tmp = *a;      *a = *b;      *b = tmp;     

92、; int partition(int a, int low, int high)        int privotKey = alow;                       &#

93、160;     /基準(zhǔn)元素      while(low < high)                                

94、60;  /從表的兩端交替地向中間掃描          while(low < high  && ahigh >= privotKey) -high;  /從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端        

95、;  swap(&alow, &ahigh);          while(low < high  && alow <= privotKey ) +low;          swap(&alow, &ahi

96、gh);            print(a,10);      return low;        void quickSort(int a, int low, int high)      if(low

97、 < high)          int privotLoc = partition(a,  low,  high);  /將表一分為二          quickSort(a,  low,  privotLoc -1);

98、0;         /遞歸對低子表遞歸排序          quickSort(a,   privotLoc + 1, high);        /遞歸對高子表遞歸排序        

99、    int main()      int a10 = 3,1,5,7,2,4,9,6,10,8;      cout<<"初始值："      print(a,10);      quickSort(a,0,9);  &#

100、160;   cout<<"結(jié)果："      print(a,10);      void print(int a, int n)for(int j= 0; j<n; j+)cout<<aj <<" "cout<<endl;void swap(int *a, int *b)int tmp = *a;*a = *b;*b = tmp;int partit

101、ion(int a, int low, int high)int privotKey = alow;/基準(zhǔn)元素while(low < high) /從表的兩端交替地向中間掃描while(low < high && ahigh >= privotKey) -high; /從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端swap(&alow, &ahigh);while(low < high && alow <= privotKey ) +low;swap(&alow, &

102、ahigh);print(a,10);return low;void quickSort(int a, int low, int high)if(low < high)int privotLoc = partition(a, low, high); /將表一分為二quickSort(a, low, privotLoc -1);/遞歸對低子表遞歸排序quickSort(a, privotLoc + 1, high);/遞歸對高子表遞歸排序int main()int a10 = 3,1,5,7,2,4,9,6,10,8;cout<<"初始值："print(a,

103、10);quickSort(a,0,9);cout<<"結(jié)果："print(a,10);分析：快速排序是通常被認為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄?？焖倥判蚴且粋€不穩(wěn)定的排序方法。 快速排序的改進在本改進算法中,只對長度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復(fù)雜度有所降低，且

104、當(dāng)k取值為 8 左右時,改進算法的性能最佳。算法思想如下：cpp view plaincopyprint?void print(int a, int n)      for(int j= 0; j<n; j+)          cout<<aj <<"  " 

105、0;          cout<<endl;      void swap(int *a, int *b)        int tmp = *a;      *a = *b;      *b = tmp;      int partition(int a, int low, int high)