冒泡法排序c++

1、冒泡排序是非常容易理解和實(shí)現(xiàn)，以從小到大排序舉例：設(shè)數(shù)組長(zhǎng)度為N。1比較相鄰的前后二個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個(gè)數(shù)據(jù)交換。2這樣對(duì)數(shù)組的第0個(gè)數(shù)據(jù)到N-1個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第N-1個(gè)位置。3N=N-1，如果N不為0就重復(fù)前面二步，否則排序完成。按照定義很容易寫出代碼：/冒泡排序1void BubbleSort1(int a, int n) int i, j; for (i = 0; i n; i+) for (j = 1; j aj) Swap(aj - 1, aj);下面對(duì)其進(jìn)行優(yōu)化，設(shè)置一個(gè)標(biāo)志，如果這一趟發(fā)生了交換，則為true，否則為fa

2、lse。明顯如果有一趟沒(méi)有發(fā)生交換，說(shuō)明排序已經(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 aj) Swap(aj - 1, aj); flag = true; k-; 再做進(jìn)一步的優(yōu)化。如果有100個(gè)數(shù)的數(shù)組，僅前面10個(gè)無(wú)序，后面90個(gè)都已排好序且都大于前面10個(gè)數(shù)字，那么在第一趟遍歷后，最后發(fā)生交換的位置必定小于10，且這個(gè)位置之后的數(shù)據(jù)必定已經(jīng)有序了，記錄下這位置，第二次只要從數(shù)組頭部遍歷

3、到這個(gè)位置就可以了。/冒泡排序3void BubbleSort3(int a, int n)int j, k;int flag;flag = n;while (flag 0)k = flag;flag = 0;for (j = 1; j aj)Swap(aj - 1, aj);flag = j;冒泡排序畢竟是一種效率低下的排序方法，在數(shù)據(jù)規(guī)模很小時(shí)，可以采用。數(shù)據(jù)規(guī)模比較大時(shí)，最好用其它排序方法。白話經(jīng)典算法系列之二 直接插入排序的三種實(shí)現(xiàn) 分類： 白話經(jīng)典算法系列2011-08-06 19:2723895人閱讀評(píng)論(32)收藏舉報(bào)算法直接插入排序(Insertion Sort)的基本思想是：

4、每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。設(shè)數(shù)組為a0n-1。1. 初始時(shí)，a0自成1個(gè)有序區(qū)，無(wú)序區(qū)為a1.n-1。令i=12. 將ai并入當(dāng)前的有序區(qū)a0i-1中形成a0i的有序區(qū)間。3. i+并重復(fù)第二步直到i=n-1。排序完成。下面給出嚴(yán)格按照定義書(shū)寫的代碼（由小到大排序）：cpp view plaincopyprint?1. void Insertsort1(int a, int n) 2. 3. int i, j, k; 4. for (i = 1; i = 0; j-) 8. if (aj j; k-) 17. ak

5、 + 1 = ak; 18. /將ai放到正確位置上 19. ak + 1 = temp; 20. 21. 22. void Insertsort1(int a, int n)int i, j, k;for (i = 1; i = 0; j-)if (aj j; k-)ak + 1 = ak;/將ai放到正確位置上ak + 1 = temp;這樣的代碼太長(zhǎng)了，不夠清晰?，F(xiàn)在進(jìn)行一下改寫，將搜索和數(shù)據(jù)后移這二個(gè)步驟合并。即每次ai先和前面一個(gè)數(shù)據(jù)ai-1比較，如果ai ai-1說(shuō)明a0i也是有序的，無(wú)須調(diào)整。否則就令j=i-1,temp=ai。然后一邊將數(shù)據(jù)aj向后移動(dòng)一邊向前搜索，當(dāng)有數(shù)據(jù)aj

6、ai時(shí)停止并將temp放到aj + 1處。cpp view plaincopyprint?1. void Insertsort2(int a, int n) 2. 3. int i, j; 4. for (i = 1; i n; i+) 5. if (ai = 0 & aj temp; j-) 9. aj + 1 = aj; 10. aj + 1 = temp; 11. 12. void Insertsort2(int a, int n)int i, j;for (i = 1; i n; i+)if (ai = 0 & aj temp; j-)aj + 1 = aj;aj + 1 = temp

7、;再對(duì)將aj插入到前面a0j-1的有序區(qū)間所用的方法進(jìn)行改寫，用數(shù)據(jù)交換代替數(shù)據(jù)后移。如果aj前一個(gè)數(shù)據(jù)aj-1 aj，就交換aj和aj-1，再j-直到aj-1 = aj。這樣也可以實(shí)現(xiàn)將一個(gè)新數(shù)據(jù)新并入到有序區(qū)間。cpp view plaincopyprint?1. void Insertsort3(int a, int n) 2. 3. int i, j; 4. for (i = 1; i = 0 & aj aj + 1; j-) 6. Swap(aj, aj + 1); 7. 白話經(jīng)典算法系列之三 希爾排序的實(shí)現(xiàn) 分類： 白話經(jīng)典算法系列2011-08-08 11:4118668人閱讀評(píng)

8、論(27)收藏舉報(bào)算法shell優(yōu)化c希爾排序的實(shí)質(zhì)就是分組插入排序，該方法又稱縮小增量排序，因DLShell于1959年提出而得名。該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。以n=10的一個(gè)數(shù)組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例第一次 gap = 10 /

9、2 = 549 38 65 97 26 13 27 49 55 41A 1B2A 2B3A 3B4A 4B5A 5B1A,1B，2A,2B等為分組標(biāo)記，數(shù)字相同的表示在同一組，大寫字母表示是該組的第幾個(gè)元素， 每次對(duì)同一組的數(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

10、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 / 2 = 0 排序完成得到數(shù)組：4 13 26 27 38 49 49 55 65 97下面給出嚴(yán)格按照定義來(lái)寫的希爾排序cpp view plaincopyprint?1. void shellsort1(int a, int n) 2. 3. int i, j, gap; 4.5. for (gap = n / 2; gap 0; gap /= 2) /步長(zhǎng) 6. for (i = 0; i gap

11、; i+) /直接插入排序 7. 8. for (j = i + gap; j n; j += gap) 9. if (aj = 0 & ak temp) 14. 15. ak + gap = ak; 16. k -= gap; 17. 18. ak + gap = temp; 19. 20. 21. void shellsort1(int a, int n)int i, j, gap;for (gap = n / 2; gap 0; gap /= 2) /步長(zhǎng)for (i = 0; i gap; i+) /直接插入排序for (j = i + gap; j n; j += gap) if (

12、aj = 0 & ak temp)ak + gap = ak;k -= gap;ak + gap = temp;很明顯，上面的shellsort1代碼雖然對(duì)直觀的理解希爾排序有幫助，但代碼量太大了，不夠簡(jiǎn)潔清晰。因此進(jìn)行下改進(jìn)和優(yōu)化，以第二次排序?yàn)槔?，原?lái)是每次從1A到1E，從2A到2E，可以改成從1B開(kāi)始，先和1A比較，然后取2B與2A比較，再取1C與前面自己組內(nèi)的數(shù)據(jù)比較.。這種每次從數(shù)組第gap個(gè)元素開(kāi)始，每個(gè)元素與自己組內(nèi)的數(shù)據(jù)進(jìn)行直接插入排序顯然也是正確的。cpp view plaincopyprint?1. void shellsort2(int a, int n) 2. 3. i

13、nt j, gap; 4.5. for (gap = n / 2; gap 0; gap /= 2) 6. for (j = gap; j n; j+)/從數(shù)組第gap個(gè)元素開(kāi)始 7. if (aj = 0 & ak temp) 12. 13. ak + gap = ak; 14. k -= gap; 15. 16. ak + gap = temp; 17. 18. void shellsort2(int a, int n)int j, gap;for (gap = n / 2; gap 0; gap /= 2)for (j = gap; j n; j+)/從數(shù)組第gap個(gè)元素開(kāi)始if (aj

14、 = 0 & ak temp)ak + gap = ak;k -= gap;ak + gap = temp;再將直接插入排序部分用 白話經(jīng)典算法系列之二 直接插入排序的三種實(shí)現(xiàn) 中直接插入排序的第三種方法來(lái)改寫下：cpp view plaincopyprint?1. void shellsort3(int a, int n) 2. 3. int i, j, gap; 4.5. for (gap = n / 2; gap 0; gap /= 2) 6. for (i = gap; i = 0 & aj aj + gap; j -= gap) 8. Swap(aj, aj + gap); 9. void shellsort3(int a, int n)int i, j, gap;for (gap = n / 2; gap 0; gap /= 2