我們這里話不多說(shuō)，排序重要性大家都很清楚，所以我們直接開(kāi)始。

我們就按照這張圖來(lái)一一實(shí)現(xiàn)吧！

一.直接插入排序與希爾排序.

這個(gè)是我之前寫過(guò)的內(nèi)容了，大家可以通過(guò)鏈接去看看詳細(xì)內(nèi)容。

算法之插入排序及希爾排序（C語(yǔ)言版）-CSDN博客

這里就直接賦上代碼了

//直接插入排序(升序)
void Insertsort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){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 Shellsort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 2;//gap = gap / 3 + 1;//先一組組排好//for (int i = 0; i < gap; i++)//{//	for (int j = i; j < n - gap; j += gap)//	{//		int end = j;//		int tmp = arr[end + gap];//		while (end >= 0)//		{//			if (tmp < arr[end])//			{//				arr[end + gap] = arr[end];//				end-=gap;//			}//			else//			{//				break;//			}//		}//		arr[end + gap] = tmp;//	}//}//多組并排for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tmp;}}
}

我們還是分析下他們的時(shí)間復(fù)雜度吧！

插入排序是通過(guò)進(jìn)行比較來(lái)插入的，最壞的情況就是都要比較，所以是O(N^2)，最好情況就是本生就是順序且有序的。

而希爾排序則不同，大家現(xiàn)在當(dāng)下只需知道大概在O(1.3N)左右即可

二.選擇排序

選擇排序的思想就是：找到最值的兩個(gè)數(shù)，分別放在首尾，然后再選擇次一級(jí)的，知道排好。是不是非常簡(jiǎn)單，所以這里我們上代碼：

//選擇排序(升序)
void Swap(int* p, int* q)
{int* tmp = *p;*p = *q;*q = tmp;
}
void Selectsort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min = begin;int max = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[min])min = i;if (arr[i] > arr[max])max = i;}Swap(&arr[begin], &arr[min]);//注意：這里一定要留意max的值是不是begin位置，如果是，前一個(gè)交換會(huì)影響到后一個(gè)，所以要找到正確的位置if (max == begin)max = min;Swap(&arr[end], &arr[max]);begin++;end--;}
}

三.堆排序

這個(gè)之前也實(shí)現(xiàn)過(guò)了，可以看鏈接：

堆排序（C語(yǔ)言版）-CSDN博客

這里還是貼下代碼：

void Adjustup(int* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
void Adjustdown(int* arr,int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child + 1] > arr[child]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void Heapsort(int* arr, int n)
{//建大堆/*for (int i = 1; i < n; i++){Adjustup(arr, i);}*/for (int i = (n - 1 - 1) / 2; i >= 0; i--){Adjustdown(arr,i,n);}//堆刪除int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);Adjustdown(arr,0, end);end--;}
}

四.冒泡排序和快速排序

這是一個(gè)可以說(shuō)是最簡(jiǎn)單的排序了，實(shí)現(xiàn)的關(guān)鍵就是想好兩層循環(huán)的條件就行了，我之前也實(shí)現(xiàn)過(guò)了，大家可以去之前我的文章看看，這里給大家一個(gè)鏈接吧！

冒泡排序即相關(guān)想法-CSDN博客

這里直接上代碼了，學(xué)到這還不會(huì)冒泡，建議別在看這個(gè)文章了，需要去補(bǔ)就前面的了。

//冒泡排序（升序）
void Bubblesort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1])Swap(&arr[j], &arr[j + 1]);}}
}

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

下面開(kāi)始我們可以說(shuō)是非常難的部分了----快速排序

我們先直接學(xué)hoare版本吧！

注意：hoare的版本是將key取開(kāi)頭的元素

如果我們按照升序排列，我們要先走右邊的，這樣才能保證相遇的點(diǎn)其值一定比key點(diǎn)的小，原因如下：

相遇分為以下兩種情況：

1.左邊相遇右邊，即右邊停止后左邊一直走，沒(méi)有找到比key大的元素直到相遇，而相遇點(diǎn)是右邊找小找到的，說(shuō)明相遇點(diǎn)比key點(diǎn)小（升序）

2.右邊相遇左邊，即左邊停止后右邊一直走，沒(méi)有找到比key小的元素直到相遇，而相遇點(diǎn)是左邊找大找到的，說(shuō)明相遇點(diǎn)比key點(diǎn)大。（降序）

下面我們實(shí)現(xiàn)吧！

//快速排序（升序）
void Swap(int* p, int* q)
{int* tmp = *p;*p = *q;*q = tmp;
}
void Quicksort(int* arr, int begin, int end)//注意end到底是啥？如果是元素個(gè)數(shù)，下面的right要減1，如果是最后一個(gè)元素下標(biāo)，end=right
{//遞歸結(jié)束條件if (begin >= end)return;int left = begin;int right = end - 1;int key = begin;while (left < right){//先右while (left < right && arr[right] >= arr[key])//右找小{right--;}//再左while (left < right && arr[left] <= arr[key])//左找大{left++;}Swap(&arr[left], &arr[right]);}//相遇點(diǎn)和key交換Swap(&arr[left], &arr[key]);//第一次完成//下面是遞歸部分key = left;Quicksort(arr, 0, key);Quicksort(arr, key + 1,end);
}

這個(gè)就是hoare版本了，學(xué)到這你可能會(huì)問(wèn)一下問(wèn)題：

1.為什么左邊要找大，右邊要找小？

我們?nèi)绻派?#xff0c;是不是從小到大的順序，如果交換的左右不是大和小，那么你確定是在排序

2.key為啥就是數(shù)組開(kāi)頭元素呢？

這個(gè)其實(shí)只是hoare版本的key找法，實(shí)際上還有其他方法的，下面我們就講解下其他key找法。

//三數(shù)取中法
int Mid(int* arr,int begin, int end)
{int mid = (begin + end-1) / 2;if (arr[begin] > arr[end]){if (arr[mid] > arr[end]){if (arr[begin] > arr[mid])return mid;elsereturn begin;}return end;}else{if (arr[mid] > arr[begin]){if (arr[end] > arr[mid])return mid;elsereturn end;}return begin;}
}

對(duì)于上面的內(nèi)容要注意我們都是end表示為最后一個(gè)元素是第幾個(gè)元素，而非所在的數(shù)組下標(biāo)。

下面我們將其改成數(shù)組下標(biāo)，再寫一遍hoare版本的快排。

//三數(shù)取中法
int Mid(int* arr,int begin, int end)
{int mid = (begin + end) / 2;if (arr[begin] > arr[end]){if (arr[mid] > arr[end]){if (arr[begin] > arr[mid])return mid;elsereturn begin;}return end;}else{if (arr[mid] > arr[begin]){if (arr[end] > arr[mid])return mid;elsereturn end;}return begin;}
}
void Quicksort(int* arr, int begin, int end)//end表示最后一個(gè)元素下標(biāo)
{if (begin >= end)return;int left = begin;int right = end;int key = begin;while (left < right){while (left < right && arr[right] >= arr[key])right--;while (left < right && arr[left] <= arr[key])left++;Swap(&arr[left], &arr[right]);}Swap(&arr[left], &arr[key]);key = left;Quicksort(arr, 0, key - 1);Quicksort(arr, key + 1, end);
}

注意改變之處。

大家可能會(huì)發(fā)現(xiàn)hoare版本的快排有非常多的點(diǎn)需要注意，于是后人就寫出了以下兩種不同的寫法，對(duì)其進(jìn)行改進(jìn)。

挖坑法

挖坑法是指先將一個(gè)數(shù)據(jù)儲(chǔ)存在數(shù)組外面，然后還是右邊找小，左邊找大，找到就將該位置的數(shù)放在原先取出的位置，然后現(xiàn)在的位置即是一個(gè)新的坑，一直上述操作直到左右相遇，然后將最開(kāi)始保存的數(shù)據(jù)放進(jìn)相遇位置。

下面我們實(shí)現(xiàn)它：

//挖坑法
void partQuicksort(int* arr, int begin, int end)//end表示最后一個(gè)元素下標(biāo)
{if (begin >= end)return;int left = begin;int right = end;int key = arr[begin];int hole = begin;//坑while (left < right){while (left < right && arr[right] >= key)right--;arr[hole] = arr[right];hole = right;while (left < right && arr[left] <= key)left++;arr[hole] = arr[left];hole = left;}arr[hole] = key;partQuicksort(arr, begin, hole - 1);partQuicksort(arr, hole + 1, end);
}

//前后指針?lè)?void part2Quicksort(int* arr, int begin, int end)//end表示下標(biāo)
{if (begin >= end)return;int prev = begin;int cur = begin + 1;int key = begin;while (cur <= end){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[key]);key = prev;part2Quicksort(arr, 0, key - 1);part2Quicksort(arr, key + 1, end);	
}

對(duì)于快排還可以優(yōu)化，例如：我們這里實(shí)現(xiàn)時(shí)發(fā)現(xiàn)，大部分的遞歸都是在元素非常小的時(shí)候，所以如果我們可以將這部分改成其他排序，是不是可以節(jié)省一部分空間。

我們以hoare版本為例：

void Quicksort2(int* arr, int begin, int end)//end表示最后一個(gè)元素下標(biāo)
{if (begin >= end)return;//如果元素小于等于10，利用其他排序，這里我們選擇插入排序if (end - begin + 1 <= 10){Insertsort(arr+begin, end - begin + 1);//注意這里數(shù)組也要變}else{int left = begin;int right = end;int key = begin;while (left < right){while (left < right && arr[right] >= arr[key])right--;while (left < right && arr[left] <= arr[key])left++;Swap(&arr[left], &arr[right]);}Swap(&arr[left], &arr[key]);key = left;Quicksort(arr, 0, key - 1);Quicksort(arr, key + 1, end);}
}

快排學(xué)到現(xiàn)在了，大家是不是覺(jué)得自己行了？？？現(xiàn)在我請(qǐng)你實(shí)現(xiàn)快排的非遞歸，請(qǐng)問(wèn)你如何實(shí)現(xiàn)呢？

//快排非遞歸
int Quicksort3(int* arr, int begin, int end)
{//我們這里就用挖坑法實(shí)現(xiàn)int hole = begin;int key = arr[begin];while (begin < end){while (begin < end && arr[end] >= key)end--;arr[hole] = arr[end];hole = end;while (begin < end && arr[begin] <= key)begin++;arr[hole] = arr[begin];hole = begin;}arr[hole] = key;return hole;
}
void QuicksortNone(int* arr, int begin, int end)
{SS s1;StackInit(&s1);StackPush(&s1,begin);StackPush(&s1, end);while (!StackEmpty(&s1)){int right = StackTop(&s1);StackPop(&s1);int left = StackTop(&s1);StackPop(&s1);int key = Quicksort3(arr, left, right);if (left < key - 1){StackPush(&s1, left);StackPush(&s1,key-1);}if (right > key + 1){StackPush(&s1,key+1);StackPush(&s1,right);}}StackDestory(&s1);
}

五.歸并排序

//歸并排序
void _Mergesort(int* arr, int begin, int end, int* tmp)
{if (begin >= end)return;//先遞歸int mid = (begin + end) / 2;_Mergesort(arr, begin, mid, tmp);_Mergesort(arr, mid + 1, end,tmp);//并int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[i++] = arr[begin1++];}else{tmp[i++] = arr[begin2++];}}while (begin1 <= end1){tmp[i++] = arr[begin1++];}while (begin2 <= end2){tmp[i++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, (end - begin + 1)*sizeof(int));
}
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//檢查if (tmp == NULL){perror(tmp);return;}_Mergesort(arr, 0, n-1, tmp);free(tmp);tmp = NULL;
}

當(dāng)然，歸并排序也可以非遞歸實(shí)現(xiàn)，由于實(shí)現(xiàn)過(guò)于復(fù)雜，所以我們現(xiàn)在就先不是實(shí)現(xiàn)了，以后我們會(huì)講的。

大家加油！