您好,登錄后才能下訂單哦!
小編這次要給大家分享的是C++如何實現(xiàn)雙向冒泡排序算法,文章內(nèi)容豐富,感興趣的小伙伴可以來了解一下,希望大家閱讀完這篇文章之后能夠有所收獲。
一、概念(來源于百度百科)
傳統(tǒng)冒泡算法原理
冒泡排序算法的運作如下:(從后往前)
1.比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
2.對每一對相鄰元素作同樣的工作,從開始第一對到結(jié)尾的最后一對。在這一點,最后的元素應該會是最大的數(shù)。
3.針對所有的元素重復以上的步驟,除了最后一個。
4.持續(xù)每次對越來越少的元素重復上面的步驟,直到?jīng)]有任何一對數(shù)字需要比較。
雙向冒泡算法原理
雙向冒泡排序算法的運作如下:
1.傳統(tǒng)冒泡氣泡排序的雙向進行,先讓氣泡排序由左向右進行,再來讓氣泡排序由右往左進行,如此完成一次排序的動作
2.使用left與right兩個旗標來記錄左右兩端已排序的元素位置。
一個排序的例子如下所示:
排序前:45 19 77 81 13 28 18 19 77 11
往右排序:19 45 77 13 28 18 19 77 11 [81]
向左排序:[11] 19 45 77 13 28 18 19 77 [81]
往右排序:[11] 19 45 13 28 18 19 [77 77 81]
向左排序:[11 13] 19 45 18 28 19 [77 77 81]
往右排序:[11 13] 19 18 28 19 [45 77 77 81]
向左排序:[11 13 18] 19 19 28 [45 77 77 81]
往右排序:[11 13 18] 19 19 [28 45 77 77 81]
向左排序:[11 13 18 19 19] [28 45 77 77 81]
如上所示,括號中表示左右兩邊已排序完成的部份,當left >= right時,則排序完成。
二、實現(xiàn)程序:
#include <iostream> #include <ctime> const int MAX = 30; // 交換兩個數(shù) void Swap(int &x, int &y) { int temp; temp = x; x = y; y = temp; } // 雙向冒泡排序 void twoBubbleSort(int arr[], int len) { int left, right, shift, i; // shift為記錄左右兩端已排序的元素位置 left = 0; right = len - 1; shift = 1; while(left < right) { // 往右排序 for(i = left; i < right; i++) { if(arr[i] > arr[i+1]) { // 第一個數(shù)比第二個數(shù)大,交換 Swap(arr[i], arr[i+1]); shift = i; } } right = shift; for(i = right-1; i >= left; i--) { // 向左排序 if(arr[i] > arr[i+1]) { // 第一個數(shù)比第二個數(shù)大,交換 Swap(arr[i], arr[i+1]); shift = i + 1; } } left = shift; } } int main(int argc, const char * argv[]) { // insert code here... int arr[MAX], i; srand((int)time(NULL)); // 設置時間為隨機點 std::cout << "排序前:"; for(i = 0; i < MAX; i++) { arr[i] = rand() % 100; std::cout << arr[i] << " "; } // 調(diào)用雙向冒泡排序函數(shù) twoBubbleSort(arr, MAX); std::cout << "\n排序后:"; for(i = 0; i < MAX; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }
運行結(jié)果:
看完這篇關(guān)于C++如何實現(xiàn)雙向冒泡排序算法的文章,如果覺得文章內(nèi)容寫得不錯的話,可以把它分享出去給更多人看到。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。