柚子快報(bào)邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)（常見的排序算法）

http://yzkb.51969.com/

1.插入排序

1.1直接插入排序

在[0? end]區(qū)間上有序，然后將（end+1）的數(shù)據(jù)與前面有序的數(shù)據(jù)進(jìn)行比較，將（end+1）的數(shù)據(jù)插入，這樣[0? end+1]區(qū)間上就是有序的，然后再向后進(jìn)行比較。

例如：想要數(shù)據(jù)調(diào)整為升，數(shù)組（end+1）位置的數(shù)據(jù)，前面是比它小的數(shù)據(jù)，后面是比它大的數(shù)據(jù)。

時間復(fù)雜度：O（N^2）?

動圖顯示：

實(shí)現(xiàn)代碼：

//插入排序(升序) void intsertsort(int* arr, int num );

?

參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//插入排序(升序)

void intsertsort(int* arr, int num )

{

for (int i = 0;i

{

//只考慮一次排序，在[0，end]上是有序的

int end = i;

int tmp = arr[end + 1];

while (end >= 0)

{

if (tmp < arr[end])

{

arr[end + 1] = arr[end];

end--;

}

else

{

break;

}

}

arr[end + 1] = tmp;

}

}

1.2希爾排序

希爾排序是從直接插入排序演化而來的，分為兩步，一個步是預(yù)處理，另一步是直接插入排序。

預(yù)處理：預(yù)處理是將原來的數(shù)據(jù)處理的盡可能有序，讓數(shù)據(jù)盡可能的在最終排序完成的位置附近，這樣就可以避免直接插入排序 數(shù)組（end+1）位置的數(shù)直接與[0? end]這個區(qū)間的數(shù)全部比較。

時間復(fù)雜度：O(N*logN)?

動圖演示：

實(shí)現(xiàn)代碼：

//希爾排序

void shellsort(int* arr, int num)；

函數(shù)參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//希爾排序(升序)

#include

//*希爾排序

//*1.預(yù)排序

//*2.插入排序

//*時間復(fù)雜度O（N^1.3）

//*

void shellsort(int* arr, int num)

{

int gap = num;

while (gap > 1)

{

//保證最后一次是1，gap不是1時實(shí)現(xiàn)預(yù)排序，是1時實(shí)現(xiàn)插入排序

gap = gap / 3 + 1;

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

{

int end = i;

int tmp = arr[end + gap];

while (end >= 0)

{

if (tmp < arr[end])

{

arr[end + gap] = arr[end];

end=end-gap;

}

else

{

break;

}

}

arr[end + gap] = tmp;

}

}

}

注：在gap不等于1的時候，是在執(zhí)行預(yù)處理，當(dāng)gap等于1的時候?qū)嵲趯?shí)現(xiàn)直接插入排序。

2.選擇排序

2.1選擇排序

選擇排序，就是一趟選擇出一個數(shù)組中的一個最大值或者最小值

時間復(fù)雜度：O(N^2)

動圖演示：?

實(shí)現(xiàn)代碼：

//選擇排序 void selectsort(int* arr, int num)

函數(shù)參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//交換函數(shù)

void swap(int*x, int* y)

{

int tmp = *x;

*x = *y;

*y = tmp;

}

//選擇排序

void selectsort(int* arr, int num)

{

//提升效率，可以同時進(jìn)行最大值和最小值的排序

int begin = 0, end = num ;

while (begin < end)

{

int imin = begin, imax = begin;

for (int i = begin; i < end; i++)

{

if (arr[i] > arr[imax])

{

imax = i;

}

if (arr[i] < arr[imin])

{

imin = i;

}

}

if (begin == imax)

imax = imin;

//放置最小值和最大值

swap(&arr[imin], &arr[begin]);

swap(&arr[imax], &arr[end - 1]);

begin++;

end--;

}

}

注：實(shí)現(xiàn)函數(shù)中是一趟找出數(shù)組中的最大值和最小值，這算是一種優(yōu)化。

2.2堆排序?

先堆數(shù)組進(jìn)行堆排序，升序建大堆，降序建小堆，下面用小堆舉例子，數(shù)組的首元素一定是數(shù)組的最大數(shù)，將首元素與數(shù)組的最后一個數(shù)進(jìn)行交換，然后對數(shù)組[0? end-1]區(qū)間進(jìn)行向下調(diào)整。繼續(xù)，直到真?zhèn)€數(shù)組有序。

時間復(fù)雜度：O（N*logN）

動圖演示：

注：上面演示的數(shù)組一開始已經(jīng)建大堆。

實(shí)現(xiàn)代碼：

//向下調(diào)整函數(shù) void downjust_big(HPDataType* root, int num,int tmp)

參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)，需要向下調(diào)整的位置

//向下調(diào)整創(chuàng)建大堆 void downjust_big_heap(HPDataType* arr, int num)

參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//大堆升序 void downjust_arry_up(HPDataType* arr, int num)

參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//交換函數(shù) void Swap(HPDataType* x, HPDataType* y)

參數(shù)：指向需要交換元素的兩個指針

//交換函數(shù)

void Swap(HPDataType* x, HPDataType* y)

{

HPDataType tmp = *x;

*x = *y;

*y = tmp;

}

//向下調(diào)整函數(shù)

void downjust_big(HPDataType* root, int num,int tmp)

{

assert(root);

int parent = tmp;

//假設(shè)左孩子和右孩子中大的那個是左孩子

int child = parent * 2 + 1;

//如果孩子節(jié)點(diǎn)不在堆中，就直接結(jié)束

while (child < num)

{

//（1）如果右孩子大于左孩子

//（2）如果沒有右孩子，那么左孩子一定是最大的

if (root[child] < root[child + 1] && (child + 1) < num)

{

//將最大的孩子修改為右孩子

child++;

}

if (root[parent] < root[child])

{

Swap(&root[parent], &root[child]);

parent = child;

child = parent * 2 + 1;

}

else

{

//直接跳出循環(huán)

break;

}

}

}

//向下調(diào)整創(chuàng)建大堆

void downjust_big_heap(HPDataType* arr, int num)

{

assert(arr);

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

{

downjust_big(arr, num, i);

}

}

//大堆升序

void downjust_arry_up(HPDataType* arr, int num)

{

assert(arr);

downjust_big_heap(arr, num);

while (num)

{

Swap(&arr[0], &arr[num - 1]);

num--;

downjust_big(arr, num, 0);

}

}

3.交換排序?

3.1冒泡排序?

冒泡排序，實(shí)際上就是兩兩比較，滿足條件的兩兩交換，一趟可以選擇出數(shù)組中的最大值后者最小值（取決于升序還是降序），直到將數(shù)據(jù)中的全部數(shù)據(jù)排序完成。

時間復(fù)雜度：N(N^2)?

動圖演示：?

實(shí)現(xiàn)代碼：

//冒泡排序

void BubbleSort(int* arr, int n)?;

函數(shù)參數(shù)：指向數(shù)組首元素的指針，數(shù)組中的元素個數(shù)

//冒泡排序（升序）

//* 時間復(fù)雜度O（N^2）

void swap(int* x, int* y)

{

int tmp = *x;

*x = *y;

*y = tmp;

}

void BubbleSort(int* arr, int n)

{

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

{

int flag = 1;

//一次遍歷

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

{

if (arr[i] > arr[i + 1])

{

swap(&arr[i], &arr[i + 1]);

flag = -1;

}

}

if (flag == 1)

break;

}

}

3.2快速排序??

快速排序：就是選擇一個數(shù)據(jù)，將數(shù)組中的數(shù)分為小于該數(shù)和大于該數(shù)的兩個部分，小于該數(shù)的部分在該數(shù)的左邊，大于的放在該數(shù)的右邊。然后該數(shù)的位置為分界，然后在兩個小區(qū)間重復(fù)上面的操作。?

時間復(fù)雜度：O(N*logN)?

代碼演示：

hoare法：

?挖坑法：

前后指針法：

初學(xué)者適合先看挖坑法進(jìn)行一個理解。?

實(shí)現(xiàn)代碼：

//快速排序（hoare） void QuickSort(int* arr, int left, int right)?;

參數(shù)：指向數(shù)組首元素的指針，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置

//快速排序

void QuickSort(int* arr, int left, int right)

{

if (left >= right)

return;

int begin = left, end = right;

int keyi = begin;

while (begin < end)

{

//左邊當(dāng)鑰匙時，是右邊開始移動

//當(dāng)找到一個比keyi小的數(shù)字時，停下來

while (begin= arr[keyi])

{

end--;

}

//右邊開始移動

while (begin

{

begin++;

}

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

}

//begin和end相遇

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

keyi = begin;

//接下來就是遞歸

//標(biāo)準(zhǔn)值左右兩邊

QuickSort(arr, left, keyi - 1);

QuickSort(arr, keyi+1,right);

}

注：選擇最左邊的數(shù)為標(biāo)志數(shù)，那么那就不許從右邊進(jìn)行開始比較。?

//快速排序（挖坑法） void QuickSort(int* arr, int left, int right)；

參數(shù)：指向數(shù)組首元素的指針，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置

//快速排序（挖坑法）

void QuickSort(int* arr, int left, int right)

{

if (left >= right)

return;

int begin = left, end = right;

int keyi = arr[left];

while (begin < end)

{

//左邊當(dāng)鑰匙時，是右邊開始移動

//當(dāng)找到一個比keyi小的數(shù)字時，停下來

while (begin < end && arr[end] >=keyi)

{

end--;

}

arr[begin] = arr[end];

//右邊開始移動

while (begin < end && arr[begin] <= keyi)

{

begin++;

}

arr[end] = arr[begin];

}

//begin和end相遇

arr[end] = keyi;

keyi = begin;

//接下來就是遞歸

//標(biāo)準(zhǔn)值左右兩邊

QuickSort(arr, left, keyi - 1);

QuickSort(arr, keyi + 1, right);

}

//快速排序（前后指針法）?

void QuickSort(int* arr, int left, int right)

參數(shù)：指向數(shù)組首元素的指針，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置

void QuickSort(int* arr, int left, int right)

{

if (left >= right)

return;

int prev = left, cur = left + 1;

int keyi = left;

while (cur<=right)

{

//cur指針找比arr[keyi]小的數(shù)值

if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])

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

cur++;

}

swap(&arr[keyi], &arr[prev]);

keyi = prev;

//接下來就是遞歸

//標(biāo)準(zhǔn)值左右兩邊

QuickSort(arr, left, keyi - 1);

QuickSort(arr, keyi + 1, right);

}

由于快速排序使用遞歸，如果數(shù)據(jù)過大，就很容易出現(xiàn)棧的溢出，因此需要改為非遞歸。

//快速排序（非遞歸）

實(shí)際上，非遞歸是使用了遞歸的邏輯，只不過是使用棧數(shù)據(jù)結(jié)構(gòu)來儲存需要進(jìn)行快速排序的兩個區(qū)間。

void QuickSortNonR(int* arr, int left, int right)?

參數(shù)：指向數(shù)組首元素的指針，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置

//棧的定義

typedef int STDataType;

typedef struct Stack

{

STDataType* a;

int top; // 棧頂（指向棧頂元素的下一位）

int capacity; // 容量

}Stack;

// 初始化棧

void StackInit(Stack* ps)

{

assert(ps);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

// 入棧 (對應(yīng)順序表的尾插)

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

//判斷插入時的空間

if (ps->top == ps->capacity)

{

//判斷棧是否申請空間

ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* new = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType));

if (new == NULL)

{

perror("StackPush::realloc");

}

else

{

ps->a = new;

}

}

//尾插

ps->a[ps->top] = data;

ps->top++;

}

// 出棧 (對應(yīng)于順序表的尾刪)

void StackPop(Stack* ps)

{

assert(ps);

ps->top--;

}

// 獲取棧頂元素

STDataType StackTop(Stack* ps)

{

assert(ps);

return ps->a[ps->top-1];

}

// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0

int StackEmpty(Stack* ps)

{

assert(ps);

//棧為空返回1，棧不為空返回0

if (ps->top == 0)

{

return 0;

}

else

{

return 1;

}

}

// 銷毀棧

void StackDestroy(Stack* ps)

{

assert(ps);

ps->capacity = ps->top = 0;

free(ps->a);

ps->a = NULL;

}

//快速排序（非遞歸）

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

{

//非遞歸實(shí)際上就是使用棧來模擬遞歸

Stack ps;

StackInit(&ps);

//將區(qū)間數(shù)放入棧中

StackPush(&ps, left);

StackPush(&ps, right);

while (StackEmpty(&ps))

{

//取出棧的區(qū)間

int end = StackTop(&ps);

StackPop(&ps);

int begin = StackTop(&ps);

StackPop(&ps);

//去除區(qū)間只有一個數(shù)值，和區(qū)間沒有數(shù)值

if (begin < end)

{

int keyi = begin;

int prev = begin;

int cur = begin + 1;

while (cur <= end)

{

if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])

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

cur++;

}

swap(&arr[keyi], &arr[prev]);

keyi = prev;

//添加小區(qū)間,先添加右區(qū)間，在添加左區(qū)間

StackPush(&ps, keyi + 1);

StackPush(&ps, end);

StackPush(&ps, begin);

StackPush(&ps, keyi - 1);

}

}

//銷毀棧

StackDestroy(&ps);

}

?3.2.1快速排序優(yōu)化（三數(shù)取中）

如果我們只是單一的選擇數(shù)組的首元素作為比較的標(biāo)志數(shù)，那么我們就很容易取到過于大或者過于小的數(shù)，那么我們的時間復(fù)雜度就很容易偏向于O(N^2)?,所以使用三數(shù)取中，其取數(shù)組的首元素，尾元素和中間元素，在這個三個數(shù)中取中間的數(shù)，然后將中間的數(shù)與數(shù)組首位置的數(shù)據(jù)交換，然后進(jìn)行一個快速排序。

代碼實(shí)現(xiàn)：

//三數(shù)取中 int ThreeNumMiddle(int* arr, int left, int right)?

參數(shù)：指向數(shù)組首元素的指針，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置

//三數(shù)取中

int ThreeNumMiddle(int* arr, int left, int right)

{

int middle = (right + left) / 2;

if (arr[left] > arr[right])

{

if (arr[right] > arr[middle])

return right;

else

{

if (arr[left] > arr[middle])

return middle;

else

return left;

}

}

else

{

if (arr[middle] > arr[right])

return right;

else

{

if (arr[left] > arr[middle])

return left;

else

return middle;

}

}

}

3.2.2快速排序優(yōu)化（小區(qū)間優(yōu)化）?

快速排序是一個前序遍歷，這個排序的區(qū)間的劃分上很像二叉樹，最終小區(qū)間的數(shù)量會非常多，其實(shí)當(dāng)區(qū)間足夠小的時候，不同排序之間的時間差異不是很大，當(dāng)區(qū)間差小于一個數(shù)時，使用直接插入排序，這樣會很節(jié)約很多分區(qū)間的時間花費(fèi)。?

//小區(qū)間優(yōu)化??

//三數(shù)取中

int ThreeNumMiddle(int* arr, int left, int right)

{

int middle = (right + left) / 2;

if (arr[left] > arr[right])

{

if (arr[right] > arr[middle])

return right;

else

{

if (arr[left] > arr[middle])

return middle;

else

return left;

}

}

else

{

if (arr[middle] > arr[right])

return right;

else

{

if (arr[left] > arr[middle])

return left;

else

return middle;

}

}

}

//插入排序(升序)

void intsertsort(int* arr, int num)

{

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

{

//只考慮一次排序，在[0，end]上是有序的

int end = i;

int tmp = arr[end + 1];

while (end >= 0)

{

if (tmp < arr[end])

{

arr[end + 1] = arr[end];

end--;

}

else

{

break;

}

}

arr[end + 1] = tmp;

}

}

void QuickSort(int* arr, int left, int right)

{

if (left >= right)

return;

//小區(qū)間優(yōu)化

//在小區(qū)間中使用快速排序

if ((right - left) <= 5)

{

intsertsort(arr + left, right - left + 1);

return;

}

//三數(shù)取中

int middle = ThreeNumMiddle(arr, left, right);

swap(&arr[left], &arr[middle]);

int prev = left, cur = left + 1;

int keyi = left;

while (cur<=right)

{

//cur指針找比arr[keyi]小的數(shù)值

if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])

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

cur++;

}

swap(&arr[keyi], &arr[prev]);

keyi = prev;

//接下來就是遞歸

//標(biāo)準(zhǔn)值左右兩邊

QuickSort(arr, left, keyi - 1);

QuickSort(arr, keyi + 1, right);

}

4.歸并排序?

4.1歸并排序?

歸并排序，如其其名，先歸，指將數(shù)組進(jìn)行一個劃分將區(qū)間中只剩一個數(shù)，然后將這個區(qū)間與它相鄰的區(qū)間進(jìn)行比較，將兩個區(qū)間的數(shù)據(jù)進(jìn)行一個排序，插入到一個中間數(shù)組中。?

動圖演示：

代碼實(shí)現(xiàn)：

?//歸并排序(遞歸版) void MergeSort(int* arr, int num)

參數(shù)：指向數(shù)組首元素的指針，數(shù)組中元素的數(shù)量

//子函數(shù)（實(shí)現(xiàn)主要功能）（遞歸） void _MergeSort(int* arr, int* tmp, int left, int right)

參數(shù)：指向數(shù)組首元素的指針，指向中間臨時數(shù)組首元素的地址，指向數(shù)組最左邊位置，指向數(shù)組最右邊位置?

//子函數(shù)（實(shí)現(xiàn)主要功能）（遞歸）

void _MergeSort(int* arr, int* tmp, int left, int right)

{

//區(qū)間中只有一個數(shù)直接跳出循環(huán)

if (left >= right)

return;

int middle = (left + right) / 2 ;

//左區(qū)間

_MergeSort(arr, tmp, left, middle);

//右區(qū)間

_MergeSort(arr, tmp, middle+1, right);

int begin1 = left, begin2 = middle + 1;

int end1 = middle, end2 = right;

int i = begin1;

//一次比較

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

{

//將小的數(shù)放數(shù)組中

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

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

else

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

}

//循環(huán)左右兩個數(shù)組一個又一個讀取完成

while (begin1 <= end1)

{

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

}

while (begin2 <= end2)

{

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

}

//將調(diào)序的結(jié)果復(fù)制到原數(shù)組中

memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));

}

//歸并排序(遞歸版)

void MergeSort(int* arr, int num)

{

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

if (tmp == NULL)

{

perror("MergeSort::malloc");

exit(1);

}

//調(diào)用子函數(shù)

_MergeSort(arr, tmp, 0, num-1);

//釋放空間

free(tmp);

tmp = NULL;

}

//歸并排序（非遞歸） void MergeSortNonR(int* arr, int num)?

//子函數(shù)（非遞歸） void _MergeSortNonR(int* arr, int* tmp, int left, int right)

//子函數(shù)（非遞歸）

void _MergeSortNonR(int* arr, int* tmp, int left, int right)

{

int gap = 1;

int n = right - left + 1;

while (gap

{

for (int j = left; j <=right;j=j+2*gap )

{

int begin1 = j, begin2 = j + gap;

int end1 = j + gap - 1, end2 = j + 2*gap - 1;

int i = j;

//數(shù)組越界的問題

//[begin1 end1]和[begin2 end2]

//對應(yīng)于end1大于n和begin2 > n的情況

if (begin2 > right)

break;

//對應(yīng)end2 > n 的情況

if (end2 > right)

{

end2 = right;

}

//一次比較

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

{

//將小的數(shù)放數(shù)組中

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

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

else

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

}

//循環(huán)左右兩個數(shù)組一個又一個讀取完成

while (begin1 <= end1)

{

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

}

while (begin2 <= end2)

{

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

}

//將調(diào)序的結(jié)果復(fù)制到原數(shù)組中

memcpy(arr + j, tmp + j, sizeof(int)* (end2-j+1));

}

gap = 2 * gap;

}

}

//歸并排序（非遞歸）

void MergeSortNonR(int* arr, int num)

{

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

if (tmp == NULL)

{

perror("MergeSort::malloc");

exit(1);

}

//調(diào)用子函數(shù)

_MergeSortNonR(arr, tmp, 0, num - 1);

//釋放空間

free(tmp);

tmp = NULL;

}

gap是一個區(qū)間差，區(qū)間差成倍數(shù)的增加，這樣最終會出現(xiàn)一個越界的情況，每一次會分為連個區(qū)間 [begin1? end1]? [begin2? end2]? begin1是不可能越界的，越界的可能是end1 begin2 和end 2

end1越界：說明end1，begin2和end2都是越界的。這也就是說只有一個區(qū)間是有效區(qū)間，那么就不需要兩個區(qū)間進(jìn)行比較，直接退出。

begin2越界：這個情況和end1越界是一樣的，只有一個有效區(qū)間，可以直接退出。

end2越界，說明有兩個區(qū)間，一個區(qū)間有效，一個區(qū)間部分有效，end2越界說明它大于數(shù)組的最左邊的位置，那么那個部分有效的區(qū)間中的有效區(qū)間實(shí)際上就是[begin2? right],直接將end2賦值為rigth，就可以進(jìn)行兩個區(qū)間的比較。

?總結(jié)?

? ? ? ? ?上面介紹了幾種常見的數(shù)據(jù)結(jié)構(gòu)的排序方法，一些排序的理解是比較復(fù)雜的，所以需要自己畫相應(yīng)的圖，一步一步的推演排序的過程。同時有什么錯誤或者問題可以在評論區(qū)進(jìn)行交流。?

柚子快報(bào)邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)（常見的排序算法）

http://yzkb.51969.com/

推薦閱讀