冒泡法排序c++

1、冒泡排序是非常容易理解和實現(xiàn)，以從小到大排序舉例： 設(shè)數(shù)組長度為N。1 比較相鄰的前后二個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個數(shù)據(jù)交換。2 這樣對數(shù)組的第 0個數(shù)據(jù)到N-1個數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個數(shù)據(jù)就“沉” 到數(shù)組第N-1個位置。3. N=N-1，如果N不為0就重復(fù)前面二步，否則排序完成。 按照定義很容易寫出代碼：/冒泡排序1void BubbleSort1(i nt a, i nt n)int i, j;for (i = 0; i < n; i+)for (j = 1; j < n - i; j+)if (aj - 1 > aj)Swap(aj - 1, a

2、j);true,否則為 false。下面對其進(jìn)行優(yōu)化，設(shè)置一個標(biāo)志，如果這一趟發(fā)生了交換，則為 明顯如果有一趟沒有發(fā)生交換，說明排序已經(jīng)完成。/冒泡排序2void BubbleSort2(int a, int n)int j, k;bool flag;k = n;flag = true;while (flag)flag = false;for (j = 1; j < k; j+)if (aj - 1 > aj)Swap(aj - 1, aj);flag = true;k-;再做進(jìn)一步的優(yōu)化。如果有 100個數(shù)的數(shù)組，僅前面10個無序，后面90個都已排好序 且都大于前面10個數(shù)字，那

3、么在第一趟遍歷后，最后發(fā)生交換的位置必定小于10,且這個位置之后的數(shù)據(jù)必定已經(jīng)有序了，記錄下這位置，第二次只要從數(shù)組頭部遍歷到這個位置就可以了。/冒泡排序3void BubbleSort3(int a, int n)int j, k;int flag;flag = n;while (flag > 0)k = flag;flag = 0;for (j = 1; j < k; j+)if (aj - 1 > aj)Swap(aj - 1, aj); flag = j;冒泡排序畢竟是一種效率低下的排序方法，在數(shù)據(jù)規(guī)模很小時，可以采用。數(shù)據(jù)規(guī)模比 較大時，最好用其它排序方法。白話經(jīng)典

4、算法系列之二直接插入排序的三種實現(xiàn)分類：白話經(jīng)典算法系列2011-08-06 19:2723895人閱讀評論(32)收藏舉報算法直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。設(shè)數(shù)組為a0n-1。1. 初始時，a0自成1個有序區(qū)，無序區(qū)為a仁n-1。令i=12. 將ai并入當(dāng)前的有序區(qū)a0i-1中形成a0i的有序區(qū)間。3. i+并重復(fù)第二步直到i=n-1。排序完成。下面給出嚴(yán)格按照定義書寫的代碼(由小到大排序)：cpp view plaincopyprint?1. void In

5、 sertsort1( int a, int n)2. 3. int i, j, k;4. for (i = 1; i < n; i+)5. 6. /為ai在前面的a0.i-1有序區(qū)間中找一個合適的位置7. for (j = i - 1; j >= 0; j-)8. if (aj < ai)9. break;10.10. /如找到了一個合適的位置11. if (j != i - 1)12. 13. /將比ai大的數(shù)據(jù)向后移14. int temp = ai;15. for (k = i - 1; k > j; k-)16. ak + 1 = ak;17. /將ai放到正

6、確位置上18. ak + 1 = temp;19. 20. 21. 這樣的代碼太長了，不夠清晰?，F(xiàn)在進(jìn)行一下改寫，將搜索和數(shù)據(jù)后移這二個步驟合并。即每次ai先和前面一個數(shù)據(jù)ai-1比較，如果ai > ai-1說明a0i也是有序的，無須 調(diào)整。否則就令j=i-1,temp=ai。然后一邊將數(shù)據(jù)aj向后移動一邊向前搜索，當(dāng)有數(shù)據(jù) aj<ai時停止并將temp放到aj + 1處。cpp view plaincopyprint?1. void In sertsort2( int a, int n)2. 3. int i, j;4. for (i = 1; i < n; i+)5. i

7、f (ai < ai - 1)6. 7. int temp = ai;8. for (j = i - 1; j >= 0 && aj > temp; j-)9. aj + 1 = aj;10. aj + 1 = temp;11. 12. 再對將aj插入到前面a0j-1的有序區(qū)間所用的方法進(jìn)行改寫，用數(shù)據(jù)交換代替數(shù)據(jù) 后移。如果aj前一個數(shù)據(jù)aj-1 > aj，就交換aj和aj-1，再j-直到aj-1 <= aj。 這樣也可以實現(xiàn)將一個新數(shù)據(jù)新并入到有序區(qū)間。cpp view plaincopyprint?1. void In sertsort3(

8、int a, int n)2. 3. int i, j;4. for (i = 1; i < n; i+)5. for (j = i - 1; j >= 0 && aj > aj + 1; j-)6. Swap(aj, aj + 1);7. 白話經(jīng)典算法系列之三希爾排序的實現(xiàn)分類：白話經(jīng)典算法系列2011-08-08 11:4118668人閱讀評論(27)收藏舉報 算法shell優(yōu)化c希爾排序的實質(zhì)就是分組插入排序，該方法又稱縮小增量排序， 因DL . Shell于1959年提出而得名。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列(由相隔某個“增

9、量” 的元素組成的)分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個序列中 的元素基本有序(增量足夠小)時，再對全體元素進(jìn)行一次直接插入排序。因為直接插 入排序在兀素基本有序的情況下(接近最好情況)，效率是很咼的，因此希爾排序在時 間效率上比前兩種方法有較大提高。以 n=10 的一個數(shù)組 49, 38, 65, 97, 26, 13, 27, 49, 55, 4 為例第一次 gap = 10 / 2 = 549 38 65 97 26 13 27 49 55 41A 1B2A 2B3A 3B4A 4B5A 5B1A,1B, 2A,2B等為分組標(biāo)記，數(shù)字相同的表示在同一組，大寫字母表示是

10、該組的第幾個 元素，每次對同一組的數(shù)據(jù)進(jìn)行直接插入排序。即分成了五組(49, 13) (38, 27) (65, 49)(97, 55) (26, 4)這樣每組排序后就變成了 (13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。 第二次 gap = 5 / 2 = 2排序后13 27 49 55 4 49 38 65 97 261A 1B 1C 1D 1E2A 2B 2C 2D 2E第三次gap = 2 / 2 = 14 26 13 27 38 49 49 55 97 651A 1B 1C 1D 1E 1F 1G 1H 1I 1J第四次gap = 1

11、/ 2 = 0排序完成得到數(shù)組：4 13 26 27 38 49 49 55 65 97下面給出嚴(yán)格按照定義來寫的希爾排序cpp view plaincopyprint?1. void shellsort1(int a, int n)2. 3. int i, j, gap;4.4. for (gap = n / 2; gap > 0; gap /= 2) / 步長5. for (i = 0; i < gap; i+) / 直接插入排序6. 7. for (j = i + gap; j < n; j += gap)8. if (aj < aj - gap)9. 10. i

12、nt temp = aj;11. int k = j - gap;12. while (k >= 0 && ak > temp)13. 14. ak + gap = ak;15. k -= gap;16. 17. ak + gap = temp;18. 19. 20. 很明顯，上面的shellsort1代碼雖然對直觀的理解希爾排序有幫助，但代碼量太大了，不夠簡潔清晰。因此進(jìn)行下改進(jìn)和優(yōu)化，以第二次排序為例，原來是每次從1A到1E,從2A到2E，可以改成從1B開始，先和1A比較，然后取2B與2A比較，再取1C與前面 自己組的數(shù)據(jù)比較.。這種每次從數(shù)組第gap個元素開始

13、，每個元素與自己組的數(shù)據(jù) 進(jìn)行直接插入排序顯然也是正確的。cpp view plaincopyprint?1. void shellsort2( int a, int n)2. 3. int j, gap;4.4. for (gap = n / 2; gap > 0; gap /= 2)5. for (j = gap; j < n; j+)從數(shù)組第gap個元素開始6. if (aj < aj - gap)/每個元素與自己組的數(shù)據(jù)進(jìn)行直接插入排序7. 8. int temp = aj;9. int k = j - gap;10. while (k >= 0 && ak > temp)11. 12. ak + gap = ak;13. k -= gap;14. 15. ak + gap = temp;16. 17. 再將直接插入排序部分用白話經(jīng)典算法系列之二直接插入排序的三種實現(xiàn)中直接插入排序的第三種方法來改寫下：cpp view plaincopyprint?1. void shellsort3( int a, int n)2. 3. int i, j, gap;4.4. for (gap = n / 2; gap > 0; gap /= 2)5.