C++ 數據結構算法學習筆記(32) -五大排序算法

選擇算法

如下若有多個女生的身高需要做排序:

在這里插入圖片描述

常規思維:

第一步先找出所有候選美女中身高最高的，與最后一個數交換

在這里插入圖片描述

第二步再找出除最后一位美女外其它美女中的最高者，與倒數第二個美女交換位置

在這里插入圖片描述

再找出除最后兩位美女外其它美女中的最高者，與倒數第三個美女交換位置，因為倒數第三個本身已是最大的，所以實際無需交換.

在這里插入圖片描述

重復以上步驟，直到最后只剩下一人，此時，所有的美女均已按照身高由矮到高的順序排列

在這里插入圖片描述

代碼實現:

#include<stdio.h>
#include<stdlib.h>
void swap(int* num1, int* num2)//交換兩個變量的值
{int temp = *num1;*num1 = *num2;*num2 = temp;
}void SelectSort1(int arr[], int len) {for (int i = 0; i < len - 1; i++) {int max = 0;for (int j = 1; j < len - i; j++) { //查找未排序的元素if (arr[j] > arr[max]) { //找到目前最小值max = j;}}//printf("max:%dbeauties%d\n",max,len-i-1);if (max != (len - i - 1)) {swap(&arr[max], &arr[len - i - 1]);}}
}
void SelectSort2(int arr[], int len) {int i, j;for (i = 0; i < len - 1; i++){int min = i;for (j = i + 1; j < len; j++) { //查找未排序的元素if (arr[j] < arr[min]) { //找到目前最小值min = j; //記錄最小值}}swap(&arr[min], &arr[i]); //交換}
}
int main(void) {int beauties[] = { 163,161,158,165,171,170,163,159,162 };int len = sizeof(beauties) / sizeof(beauties[0]);SelectSort2(beauties, len);for (int i = 0; i < len; i++) {printf("%d ", beauties[i]);}system("pause");
}

冒泡算法

當我們采用前面的選擇排序時，我們仍然要將候選者遍歷5遍，才能完成最終的排序，但其實，本身這些美女出了第一個外，已經很有序了，我們只需要把第一個和第二個交換，然后又和第三個交換，如此循環，直到和最后一個交換后，整個數組基本就有序了！

在這里插入圖片描述

當然，并不是每次都這么幸運，像下面的情況就會更復雜一些，一趟并不能完全解決問題，我們需要多趟才能解決問題.

在這里插入圖片描述

經過上述五步后,得到的結果:

在這里插入圖片描述

此時,我們只保障了最后一個數是最大的,并不能保障前面的數一定會有序,所以,我們繼續按照上面五步對剩下的5個數繼續進行一次排序,數組就變得有序了. 以上過程就是冒泡排序:通過重復地遍歷未排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢得像泡泡一樣“浮”到數列的頂端,故而得名

代碼實現:

#include <iostream>
#include <string>using namespace std;void swap(int* tmp1, int* tmp2)
{int tmp3 = *tmp1;*tmp1 = *tmp2;*tmp2 = tmp3;
}int main()
{int height2[] = { 156,162,161,172,167,169,155 };int height[] = { 155,158,161,163,172,174 };int size = sizeof(height) / sizeof(height[0]);for (int i = 0; i < size-1; i++){bool sorted = true;for (int j = 0; j < size-i-1; j++){if (height[j] > height[j+1]){	sorted = false;swap(&height[j], &height[j + 1]);}}if (sorted == true)	break;}for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

插入排序

在這里插入圖片描述

首先,我們只考慮第一個元素,從第一個元素171開始，該元素可以認為已經被排序；

在這里插入圖片描述

取下一個元素161并記錄，并讓161所在位置空出來,在已經排序的元素序列中從后向前掃描；
該元素（171）大于新元素，將該元素移到下一位置；
171前已經沒有最大的元素了,則將161插入到空出的位置
取下一個元素163，并讓163所在位置空出來,在已經排序的元素序列中從后向前掃描；
該元素（171）大于新元素163，將該元素移到下一位置
繼續取171前的元素新元素比較,直到找到已排序的元素小于或者等于新元素的位置；新元素大于161,則直接插入空位中
重復步驟2~7，直到完成排序

插入排序:它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

具體算法描述如下：

從第一個元素開始，該元素可以認為已經被排序；
取出下一個元素，在已經排序的元素序列中從后向前掃描；
如果該元素（已排序）大于新元素，將該元素移到下一位置；重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置；重復步驟2~5

代碼實現::

#include <iostream>
#include <string>using namespace std;void InsertSort(int* height, int size) 
{int current = 0;int preIndex = 0;for (int i = 1; i < size; i++){current = height[i];preIndex = i-1;while (preIndex >= 0 && height[preIndex] > current){height[preIndex + 1] = height[preIndex];preIndex--;}height[preIndex + 1] = current;}
}int main()
{int height[] = { 152,163,161,159,172,170,168,151 };int size = (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout << "The sorting result is" << endl;for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

希爾排序

插入排序雖好,但是某些特殊情況也有很多缺點,比如像下面這種情況

在這里插入圖片描述

169前的元素基本不用插入操作就已經有序,元素1和2的排序幾乎要移動數組前面的所有元素!!!于是,有個老帥哥就提出了優化此問題的希爾排序!

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。

希爾排序是把記錄按下表的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的元素越來越多，當增量減至1時，所有元素被分成一組,實際上等同于執行一次上面講過的插入排序，算法便終止。

希爾排序的基本步驟：

選擇增量：gap=length/2，縮小增量：gap=gap/2

增量序列：用序列表示增量選擇，{n/2,(n/2)/2,…,1}

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：

選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列個數k，對序列進行k趟排序；

每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m的子序列，分別對各子表進行直接插入排序;

僅增量因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

在這里插入圖片描述

#include <iostream>
#include <string>
using namespace std;void InsertSort(int arr[], int len)
{int gap = len / 2;for (; gap > 0; gap = gap / 2) {for (int i = gap; i < len; i++) {int current = arr[i];int j = 0;for (j = i - gap; j >= 0 && arr[j] > current; j -= gap) {arr[j + gap] = arr[j];}arr[j + gap] = current;}}
}int main()
{int height[] = { 152,163,161,159,172,170,168,151 };int size = (sizeof(height) / sizeof(height[0]));InsertSort(height, size);cout << "The sorting result is" << endl;for (int i = 0; i < size; i++){cout << height[i] << " ";}system("pause");return 0;
}

歸并排序

當兩個組數據已經有序，我們可以通過如下方式（以下簡稱歸并大法）讓兩組數據快速有序

在這里插入圖片描述

我們可以依次從兩組中取最前面的那個最小元素依次有序放到新的數組中，然后再把新數組中有序的數據拷貝到原數組中，快速完成排序
在這里插入圖片描述

具體步驟:

對于下面這一組待排序的數組

在這里插入圖片描述

先以中間為界，把其均分為A和B兩個數組（如果是奇數個，允許兩組數相差一個）

在這里插入圖片描述

如果A和B兩組數據能夠有序，則我們可以通過上面的方式讓數組快速排好序。此時，A組有4個成員，B組有5個成員,但兩個數組都無序，然后我們可以采用分治法繼續對A組和B組進行均分，以A組為例，又可以均分A1和A2兩個組如下：

在這里插入圖片描述

均分后，A1組和A2組仍然無序，繼續利用分治法細分，以A1組為例，A1又可分成如下兩組

在這里插入圖片描述

數組細分到一個元素后，這時候，我們就可以采用歸并法借助一個臨時數組將數組A1有序化！ A2同理！

在這里插入圖片描述

依次類推，將A1組和A2組歸并成有序的A組，B組同理！

在這里插入圖片描述

最后，將A和B組使用歸并大法合并，就得到了完整的有序的結果！

在這里插入圖片描述

代碼實現:

#include <iostream>
#include <string>using namespace std;//void mergeAdd_demo(int arr[], int left, int mid, int right)
//{
//	int temp[64] = { 0 };
//	int i = left;
//	int j = mid;
//	int k = 0;
//
//	while (i < mid && j <= right)
//	{
//		if (arr[i] < arr[j])
//		{
//			temp[k++] = arr[i++];
//		}
//		else
//		{
//			temp[k++] = arr[j++];
//		}
//	}
//	while (i < mid)
//	{
//		temp[k++] = arr[i++];
//	}
//
//	while (j <= right)
//	{
//		temp[k++] = arr[j++];
//	}
//
//	memcpy(arr + left, temp, sizeof(int) * (right - left + 1));
//}void mergeAdd(int arr[], int left, int mid, int right, int* temp)
{//int temp[64] = { 0 };int i = left;int j = mid;int k = left;while (i < mid && j <= right){if (arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while (i < mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
}void mergeSort(int arr[], int left, int right, int* temp)
{int mid = 0;if (left < right){mid = left+(right-left)/2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);mergeAdd(arr, left, mid+1, right, temp);}
}int main()
{int height[] = { 10,11,12,13,2,4,5,8 };int len = sizeof(height) / sizeof(height[0]);int* temp = new int[len];//int mid = len / 2;mergeSort(height, 0, len - 1, temp);//mergeAdd(height, 0, mid, len - 1,temp);for (int i = 0; i < len; i++){cout << height[i] << " ";}system("pause");return 0;
}

快速排序

具體做法為:

每次選取第一個數為基準數；
然后使用“乾坤挪移大法”將大于和小于基準的元素分別放置于基準數兩邊；
繼續分別對基準數兩側未排序的數據使用分治法進行細分處理，直至整個序列有序。

對于下面待排序的數組:

在這里插入圖片描述

代碼實現:

#include <iostream>
#include <string>using namespace std;
int partition(int arr[], int low, int high)
{int i = low;int j = high;int base = arr[low];if (low < high){while (i < j){while (i < j && arr[j] >= base){j--;}if (i < j){arr[i++] = arr[j];}while (i < j && arr[i] < base){i++;}if (i < j){arr[j--] = arr[i];}}arr[i] = base;}return i;
}void QuickSort(int* arr, int low, int high)
{if (low < high){int index = partition(arr, low, high);QuickSort(arr, low, index - 1);QuickSort(arr, index + 1, high);}
}int main()
{int arr[] = { 163,161,158,165,171,170,163,159,162 };int len = sizeof(arr) / sizeof(arr[0]);//int index = partition(arr, 0, len - 1);QuickSort(arr, 0, len - 1);cout << "Executing the Quick Sort, result as" << endl;for (int i = 0; i < len; i++){cout << arr[i] << " ";}system("pause");return 0;
}