柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 常見排序算法

http://yzkb.51969.com/

文章目錄

冒泡排序插入排序希爾排序選擇排序堆排快速排序遞歸版前后指針版

用棧實現(xiàn)快排歸并排序用循環(huán)方式歸并

冒泡排序

冒泡排序應(yīng)該是最先學(xué)到的一種排序算法，也是最簡單的一種排序算法。 思路就是，從最前面開始兩兩比較大的放后面。但是要注意一個問題每走一趟就把這趟最大的放后面了，所以要控制一下單趟和多趟。這里用兩個循環(huán)解決。

//冒泡排序

void BubbleSort(int* a, int n)

{

for (int j = 0; j < n; j++)

{

// 單趟

int flag = 0;

for (int i = 1; i < n - j; i++)

{

if (a[i - 1] > a[i])

{

swap(&a[i - 1], &a[i]);

flag = 1;

}

}

if (flag == 0)

{

break;

}

}

}

時間復(fù)雜度：最壞情況：O(N^2) ??????最好情況：O(N) 空間復(fù)雜度：O(1)

插入排序

先思考單趟，設(shè)定end位置的下一個位置為tmp，并把tmp位置的值用一個臨時變量存起來。然后進(jìn)入循環(huán)，如果tmp的值小于end位置的值就讓end位置的值覆蓋end+1位置的值，讓end的值往后走，end下標(biāo)位置–。如果tmp位置的值大于end位置的值就把tmp位置的值放入end位置的后面，這里的循環(huán)判斷條件是end>0。這是單趟的思路，然后用for循環(huán)讓end從下標(biāo)為0位置開始，用這個單趟的思路走多趟進(jìn)行排序。

//插入排序

void InsertSort(int* a, int n)

{

for (int i = 0; i < n - 1; i++)

{

int end = i;

int tmp = a[end + 1];

while (end > 0)

{

if (tmp < a[end])

{

a[end + 1] = a[end];

end--;

}

else

{

break;

}

}

a[end + 1] = tmp;

}

}

時間復(fù)雜度：最壞情況下為O(NN)，此時待排序列為逆序，或者說接近逆序 ??????最好情況下為O(N)，此時待排序列為升序，或者說接近升序。 空間復(fù)雜度：O(1)*

希爾排序

希爾排序跟插入排序有異曲同工之處，但是希爾排序是對插入排序的優(yōu)化，在希爾排序中用到了gap，gap值隨著排序的進(jìn)行會減小當(dāng)gap>1時都是預(yù)排序。當(dāng)gap==1時數(shù)組就接近有序了，然后在對這個序列進(jìn)行一次插入排序這時排序就很快了。

每次走gap步其他和插入排序思路一樣。要注意一下i的范圍的取值，i要小于n-gap，如果i超過了n-gap走到了n-gap后面的位置i再加gap的話就越界了。i++多組并行走gap步優(yōu)化預(yù)處理的過程。隨著gap值的變化gap會越來越小，gap為1時預(yù)處理完畢，其實gap為1時就相當(dāng)于插入排序。

//希爾排序

void ShellSort(int* a, int n)

{

int gap = n;

while (gap > 0)

{

gap = gap / 3 + 1;

}

//進(jìn)入循環(huán)多組并行

for (int i = 0; i < n - gap; i++)

{

int end = i;

int tmp = i + gap;

while (end > 0)

{

if (a[end] > tmp)

{

a[end + gap] = a[end];

end--;

}

else

{

break;

}

}

a[end + gap] = tmp;

}

}

時間復(fù)雜度：O(n^(1.3-2))

選擇排序

定義begin位置也就是下標(biāo)為0位置為最大和最小位置。從begin+1位置開始遍歷數(shù)組，如果有值大于maxi位置的值，就賦這個位置下標(biāo)為最大位置。如果有值小于mini位置的值，就賦這個位置下標(biāo)為最小位置。然后把最大值與之前end位置的值交換位置，最小位置的值與之前begin位置的值交換位置。這次交換完之后，因為while循環(huán)判斷條件是begin

//選擇排序

void SelecSort(int* a, int n)

{

int begin = 0;

int end = n - 1;

while (begin < end)

{

int maxi = begin;

int mini = begin;

for (int i = begin + 1; i < n; i++)

{

while (a[i] > a[maxi])

{

maxi = i;

}

while (a[i] < a[mini])

{

mini = i;

}

}

swap(&a[begin], &a[mini]);

if (begin == maxi)

{

maxi = mini;

}

swap(&a[end], &a[maxi]);

begin++;

end--;

}

}

時間復(fù)雜度為O(n^2)

堆排

堆排在之前二叉樹中的文章中有具體實現(xiàn)步驟，下面是二叉樹的文章： 添加鏈接描述

//向上調(diào)整建堆

void AdjustDown(int* a, int n, int parent)

{

// 先假設(shè)左孩子小

int child = parent * 2 + 1;

while (child < n) // child >= n說明孩子不存在，調(diào)整到葉子了

{

// 找出小的那個孩子

if (child + 1 < n && a[child + 1] > a[child])

{

++child;

}

if (a[child] > a[parent])

{

swap(&a[child], &a[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

//堆排

void HeapSort(int* a, int n)

{

// 向下調(diào)整建堆 O(N)

for (int i = (n - 1 - 1) / 2; i >= 0; i--)

{

AdjustDown(a, n, i);

}

// O(N*logN)

int end = n - 1;

while (end > 0)

{

swap(&a[0], &a[end]);

AdjustDown(a, end, 0);

--end;

}

}

快速排序

遞歸版

選出一個key作為其他值比較的值，一般是最左邊或者最右邊的值。把最左邊的下標(biāo)和最右邊的下標(biāo)定義為begin和end。左邊找大于key的值右邊找小于key的值。然后讓左邊找到的值與右邊找到的值交換位置，如果不大于key的值或者不小于key的值左邊繼續(xù)往右走右邊繼續(xù)往左走。當(dāng)begin和end相遇的時候，把相遇位置的值與key位置的值交換位置。然后把key的位置換到begin和end相遇位置，這樣這個區(qū)間就成[left,key1]key[key+1,right]。接著讓左區(qū)間和右區(qū)間繼續(xù)遞歸。

void QuickSort1(int* a, int left, int right)

{

if (left >= right)

{

return;

}

int keyi = left;

int begin = left;

int end = right;

while (begin < end)

{

//右邊找小

while (begin a[keyi])

{

end--;

}

//左邊找大

while (begin < end && a[begin] < a[keyi])

{

begin++;

}

swap(&a[begin], &a[end]);

}

//把keyi位置換到中間

swap(&a[keyi], &a[end]);

keyi = begin;

//遞歸接著進(jìn)行排序

QuickSort1(a, left, keyi - 1);

QuickSort1(a, keyi + 1, right);

}

}

如果這個要排序的數(shù)組非常長，end要找比key小的但這個數(shù)組是升序的。end就得從這個數(shù)組的最右邊走很長一段距離才能找到小。這時我們可以用三數(shù)取中來優(yōu)化算法。 三數(shù)取中就是找到left的值和right的值和left和它倆中間的值，比較誰是中間值。中間值的當(dāng)key。

//三數(shù)取中

int GetMidi(int* a, int left, int right)

{

int midi = (left + right) / 2;

if (a[left] < a[midi])

{

if (a[midi] < a[right])

{

return midi;

}

else if (a[left] < a[right])

{

return right;

}

else

{

//a[left]>a[right]

return left;

}

}

else //(a[left]>a[midi])

{

if (a[right] < a[midi])

{

return midi;

}

else if (a[left] < a[right])

{

return left;

}

else

{

return right;

}

}

}

小區(qū)間優(yōu)化： 這里這個遞歸是和而二叉樹類似的，最下面一層的值占整個二叉樹的%50，有好多就浪費掉了。當(dāng)我們遞歸到一定程度時，可以采用插入排序來進(jìn)行優(yōu)化。

if ((right - left + 1) < 5)

{

InsertSort(a + left, right - left + 1);

}

優(yōu)化后代碼：

void QuickSort1(int* a, int left, int right)

{

if (left >= right)

{

return;

}

if ((right - left + 1) < 5)

{

InsertSort(a + left, right - left + 1);

}

else

{

//三數(shù)取中

int midi = GetMidi(a, left, right);

swap(&a[left], &a[midi]);

int keyi = left;

int begin = left;

int end = right;

while (begin < end)

{

//右邊找小

while (begin a[keyi])

{

end--;

}

//左邊找大

while (begin < end && a[begin] < a[keyi])

{

begin++;

}

swap(&a[begin], &a[end]);

}

//把keyi位置換到中間

swap(&a[keyi], &a[end]);

keyi = begin;

//遞歸接著進(jìn)行排序

QuickSort1(a, left, keyi - 1);

QuickSort1(a, keyi + 1, right);

}

}

前后指針版

選出一個key，一般是最左邊或是最右邊的。prev指針指向序列開頭，cur指針指向prev+1。若cur指向的內(nèi)容小于key，則prev先向后移動一位，然后交換prev和cur指針指向的內(nèi)容，然后cur指針++；若cur指向的內(nèi)容大于key，則cur指針直接++。如此進(jìn)行下去，直到cur到達(dá)end位置，此時將key和++prev指針指向的內(nèi)容交換即可。經(jīng)過一次單趟排序，最終也能使得key左邊的數(shù)據(jù)全部都小于key，key右邊的數(shù)據(jù)全部都大于key。 然后也還是將key的左序列和右序列再次進(jìn)行這種單趟排序，如此反復(fù)操作下去，直到左右序列只有一個數(shù)據(jù)，或是左右序列不存在時，便停止操作

int QuickSort2(int* a, int left, int right)

{

int key = left;

int mind = GetMidi(a, left, right);

swap(&a[mind], &a[left]);

int prev = left;

int cur = prev + 1;

while (cur <= right)

{

if (a[cur] < a[key] && ++prev != cur)

swap(&a[prev], &a[cur]);

cur++;

}

swap(&a[key], &a[prev]);

QuickSort2(arr, begin, keyi - 1);

QuickSort2(arr, keyi + 1, end);

}

用棧實現(xiàn)快排

把區(qū)間放入棧中，注意棧是先進(jìn)后出所以先入right后入left。然后取出這個區(qū)間進(jìn)行進(jìn)行排序，找到key的位置。[left,key-1]key[key+1,right],讓右區(qū)間入棧然后讓左區(qū)間入棧，取出左區(qū)間進(jìn)行排序找到新的key然后重復(fù)上述過程，類似遞歸的思想。左區(qū)間完了搞右區(qū)間。

int QuickSort2(int* a, int left, int right)

{

int key = left;

int mind = GetMidi(a, left, right);

swap(&a[mind], &a[left]);

int prev = left;

int cur = prev + 1;

while (cur <= right)

{

if (a[cur] < a[key] && ++prev != cur)

swap(&a[prev], &a[cur]);

cur++;

}

swap(&a[key], &a[prev]);

return prev;

}

#include"Stack.h"

//用棧實現(xiàn)快排

void QuickSortNonR(int* a, int left, int right)

{

ST st;

STInit(&st);

STPush(&st, right);//9

STPush(&st, left);//0

while (!STEmpty(&st))

{

int begin = STTop(&st);

STPop(&st);//0

int end = STTop(&st);

STPop(&st);//9

//[left,key-1]key[key+1,right]

int key = QuickSort2(a, begin, end);

if (key + 1 < right)

{

STPush(&st, right);

STPush(&st, key + 1);

}

if (left < key + 1)

{

STPush(&st, key + 1);

STPush(&st, left);

}

}

STDestroy(&st);

}

歸并排序

創(chuàng)建一個tmp數(shù)組，把之后歸并的數(shù)據(jù)先放入這個tmp數(shù)組中然后再放入原數(shù)組中。把begin到end區(qū)間找中間值分割開來。int mid = (begin + end) / 2; //[begin,mid][mid+1,end]。 然后讓兩個數(shù)組進(jìn)行比較，小的放到tmp數(shù)組中。有可能其中一個數(shù)組比較完之后另一個還有值，所以得判斷一下，把剩余的值放入tmp中。 這個也需要遞歸。

//歸并排序

void _MergeSort(int* a, int* tmp, int begin, int end)

{

if (begin >= end)

return;

int mid = (begin + end) / 2;

//[begin,mid][mid+1,end]

_MergeSort(a, tmp, begin, mid);

_MergeSort(a, tmp, mid + 1, end);

int begin1 = begin;

int end1 = mid;

int begin2 = mid + 1;

int end2 = end;

int i = begin;

while (begin1 <= end1 && begin2 <= end2)

{

if (a[begin1] < a[begin2])

{

tmp[i++] = a[begin1++];

}

else

{

tmp[i++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[i++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[i++] = a[begin2++];

}

memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));

}

void MergeSort(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int) * n);

if (tmp == NULL)

{

perror("malloc error");

return;

}

_MergeSort(a, tmp, 0, n - 1);

free(tmp);

tmp == NULL;

}

用循環(huán)方式歸并

void MergeSortNonR(int* a, int n)

{

int* tmp = (int*)malloc(sizeof(int) * n);

if (tmp == NULL)

{

perror("malloc fail");

return;

}

// gap每組歸并數(shù)據(jù)的數(shù)據(jù)個數(shù)

int gap = 1;

while (gap < n)

{

for (int i = 0; i < n; i += 2 * gap)

{

// [begin1, end1][begin2, end2]

int begin1 = i, end1 = i + gap - 1;

int begin2 = i + gap, end2 = i + 2 * gap - 1;

// 第二組都越界不存在，這一組就不需要歸并

if (begin2 >= n)

break;

// 第二的組begin2沒越界，end2越界了，需要修正一下，繼續(xù)歸并

if (end2 >= n)

end2 = n - 1;

int j = i;

while (begin1 <= end1 && begin2 <= end2)

{

if (a[begin1] < a[begin2])

{

tmp[j++] = a[begin1++];

}

else

{

tmp[j++] = a[begin2++];

}

}

while (begin1 <= end1)

{

tmp[j++] = a[begin1++];

}

while (begin2 <= end2)

{

tmp[j++] = a[begin2++];

}

memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));

}

printf("\n");

gap *= 2;

}

free(tmp);

tmp = NULL;

}

這里先一一歸并然后兩兩歸并然后四四歸并，依此類推。gap每組表示歸并數(shù)據(jù)的個數(shù)，比方說這個gap組中有兩個值，就是這兩個值進(jìn)行歸并，這gap組中有四個值，就兩兩歸并。i代表每組的歸并的起始位置。每循環(huán)一次就要讓gap*2，這樣才能滿足每組歸并數(shù)據(jù)的個數(shù)。 這里有一個問題需要注意： 第二組都越界不存在，這一組就不需要歸并 if (begin2 >= n) break;

第二的組begin2沒越界，end2越界了，需要修正一下，繼續(xù)歸并 if (end2 >= n) end2 = n - 1;

柚子快報激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 常見排序算法

http://yzkb.51969.com/

推薦閱讀