當前位置:首頁 » 操作系統 » 奇偶排序演算法

奇偶排序演算法

發布時間: 2025-01-07 09:53:37

㈠ 順序表的排序演算法

給你舉一些比較常用的排序法:

交換排序法
冒泡排序 | 雞尾酒排序 | 奇偶排序 | 梳排序 | 侏儒排序 | 快速排序 |臭皮匠演算法 | Bogo排序
選擇排序法
選擇排序 | 堆排序 | Smooth排序 | 笛卡爾樹排序 | 錦標賽排序 | 循環排序
插入排序法
插入排序 | 希爾排序 | 二叉查找樹排序 | 圖書館排序 | Patience排序
歸並排序法
歸並排序 | 多相歸並排序 | Strand排序
分布排序法
美國旗幟排序 | 珠排序 | 桶排序 | 爆炸排序 | 計數排序 | 鴿巢排序 | 相鄰圖排序 | 基數排序 | 閃電排序
混合排序法
Tim排序 | 內省排序 | Spread排序 | 反移排序 | J排序
其他
雙調排序器 | Batcher歸並網路 | 兩兩排序網路

㈡ 用C++交換排序

所謂交換,就是根據序列中兩個記錄值的比較結果來對換這兩個記錄在序列中的位置。交換排序的特點是:將鍵值較大的記錄向序列的尾部移動,鍵值較小的記錄向序列的前部移動。常見的交換排序有冒泡排序(Bubble Sort),雞尾酒排序(Cocktail Sort),奇偶排序(OddEven Sort),地精排序(Gnome Sort),快速排序(Quick Sort),臭皮匠排序(Stooge Sort),梳排序(Comb Sort),Bogo排序(Bogo sort)。下面介紹前六種:
(一)冒泡排序
最差時間復雜度:O(n^2)
最優時間復雜度:O(n)
平均時間復雜度:O(n^2)
最差空間復雜度:總共O(n),需要輔助空間O(1)
穩定性:穩定
冒泡排序(Bubble Sort),它重復地走訪過要排序的數列,一次比較兩個元素如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
冒泡排序演算法的運作如下:
1.比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
2.對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數。
3.針對所有的元素重復以上的步驟,除了最後一個。
4.持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。

實現代碼:

[cpp] view plain
void BubbleSort(int *a, int len)
{
for (int i=0; i<len; i++)
{
for (int j=len-1; j>i; j--)
{
if (a[j]<a[j-1])
swap(a[j], a[j-1]);
}
}
}

(二)雞尾酒排序

最差時間復雜度:O(n^2)
最優時間復雜度:O(n)
平均時間復雜度:O(n^2)
穩定性:穩定
雞尾酒排序(Cocktail sort),是冒泡排序的一種變形。它與冒泡排序的不同之處在於排序時是以雙向在序列中進行排序。數組中的數字本是無規律的排放,先對數組從左到右進行冒泡排序(升序),把最大值放到最右端,然後對數組從右到左進行冒泡排序(降序),把最小的數字放到最左端。然後再以此類推,以此改變冒泡的方向,並不斷縮小未排序元素的范圍。直到在一趟雙向冒泡後沒有發生交換,排序結束。

實現代碼:

[cpp] view plain
void CocktailSort(int* a, int len)
{
int bottom = 0;
int top = len-1;
bool swapped = true;

while (swapped)
{
swapped = false;
for (int i=bottom; i<top; i++)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
top = top-1;

for (int i=top; i>bottom; i--)
{
if (a[i]<a[i-1])
{
swap(a[i], a[i-1]);
swapped = true;
}
}
bottom = bottom+1;
}
}

(三)奇偶排序

最差時間復雜度:O(n^2)
穩定性:穩定
奇偶排序(OddEven Sort),是一種相對簡單的排序演算法,最初發明用於有本地互聯的並行計算。此演算法通過比較數組中相鄰的(奇-偶)位置數字對,如果該奇偶對是錯誤的順序(第一個大於第二個),則交換。下一步重復該操作,但針對所有的(偶-奇)位置數字對。如此交替下去,直到不發生交換,則排序結束。
在並行計算排序中,使用該演算法,每個處理器對應處理一個值,並僅有與左右鄰居的本地互連。所有處理器可同時與鄰居進行比較、交換操作,交替以奇-偶、偶-奇的順序。該演算法由Habermann在1972年最初發表並展現了在並行處理上的效率。但在單處理器串列運行此演算法,類似冒泡排序,較為簡單但效率並不特別高。

實現代碼:

[cpp] view plain
void OddEvenSort(int *a, int len)
{
bool swapped = true;
while (swapped)
{
swapped = false;
for (int i=0; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
for (int i=1; i<len-1; i=i+2)
{
if (a[i]>a[i+1])
{
swap(a[i], a[i+1]);
swapped = true;
}
}
}
}

(四)地精排序

最差時間復雜度:O(n^2)
最優時間復雜度:O(n)
平均時間復雜度:O(n^2)
穩定性:穩定
地精排序(Gnome Sort),被Dick Grune稱為最簡單的排序演算法。整個演算法只有一層循環,默認情況下前進冒泡,一旦遇到冒泡的情況發生就往回冒,直到把這個數字放好,然後繼續前進,前進到數組最後一個數結束。此排序演算法雖然代碼極短,但效率不高。

實現代碼:

[cpp] view plain
void GnomeSort(int *a, int len)
{
int i=0;
while (i<len)
{
if (i==0 || a[i-1]<=a[i]){
i++;
}
else {
swap(a[i], a[i-1]);
i--;
}
}
}

(五)快速排序

最差時間復雜度:O(n^2)
最優時間復雜度:O(nlogn)
平均時間復雜度:O(nlogn)
穩定性:不穩定
快速排序(Quick Sort),使用分治法策略來把一個串列分為兩個子串列,左邊子串的值總小於右邊的子串。此演算法的三個步驟:
1.分解:將數組A[l...r]劃分成兩個(可能空)子數組A[l...p-1]和A[p+1...r],使得A[l...p-1]中的每個元素都小於等於A(p),而且,小於等於A[p+1...r]中的元素。下標p也在這個劃分過程中計算。
2.解決:通過遞歸調用快速排序,對數組A[l...p-1]和A[p+1...r]排序。
3.合並:因為兩個子數組時就地排序,將它們的合並並不需要操作,整個數組A[l..r]已經排序。

實現代碼(其他實現方法見「三種快速排序演算法的實現」):

[cpp] view plain
int partition(int* a, int left, int right)
{
int x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}

void quickSort(int* a, int left, int right)
{
if (left<right)
{
int p = partition(a, left, right);

quickSort(a, left, p-1);
quickSort(a, p+1, right);
}
}

(六)臭皮匠排序

最差時間復雜度:O(n^2.7)
臭皮匠排序(Stooge Sort),是一種低效的排序演算法,在《演算法導論》第二版第7章的思考題中被提到,是由Howard Fine等教授提出的所謂「漂亮的」排序演算法。將數列平分為三個子串,依次遞歸排序前兩個子串、後兩個子串、前兩個子串,最後確保整個數列有序。此演算法在最壞情況下的遞歸式為T(n) = 3T(2n/3) + 1。由主定理很容易知道它的演算法復雜性為:T(n) = O(n^log(3/2, 3))。很顯然log(3/2, 3))>2,也就是說這個演算法比插入排序的O(n^2)性能還差。

實現代碼:

[cpp] view plain
void StoogeSort(int *a, int i, int j)
{
if(a[i]>a[j])
swap(a[i], a[j]);
if((i+1)>=j)
return;
int k = (j-i+1)/3;
StoogeSort(a, i, j-k);
StoogeSort(a, i+k, j);
StoogeSort(a, i, j-k);
}

熱點內容
演算法與外賣 發布:2025-01-08 14:33:14 瀏覽:149
為什麼安卓不用c開發 發布:2025-01-08 14:24:09 瀏覽:650
神奇寶貝伺服器怎麼進入 發布:2025-01-08 14:22:35 瀏覽:339
sqlserverclient 發布:2025-01-08 14:05:11 瀏覽:235
方舟蘋果如何開伺服器 發布:2025-01-08 14:05:04 瀏覽:506
php助手 發布:2025-01-08 14:01:37 瀏覽:23
apache開啟php 發布:2025-01-08 14:00:51 瀏覽:984
詞庫伺服器搭建 發布:2025-01-08 13:51:32 瀏覽:539
0777編程 發布:2025-01-08 13:50:04 瀏覽:727
java數據導入excel 發布:2025-01-08 13:25:38 瀏覽:629