代碼參考《妙趣橫生的算法.C語言實現》

文章目錄

前言
1、順序查找
2、折半查找
3、直接插入排序
4、選擇排序
5、冒泡排序
6、希爾排序
7、快速排序
8、堆排序
9、排序算法性能比較
10、所有算法的code（C語言）

前言

本章總結查找和排序算法：順序查找、折半查找、直接插入排序、冒泡排序、簡單選擇排序、希爾排序、快速排序、堆排序以及排序算法性能比較。

1、順序查找

順序查找就是在文件的關鍵字結合key[1,2,…n]中找出與給定的關鍵字key相等的文件記錄。

步驟描述：

1、從文件的第一個記錄開始，將每個記錄的關鍵字與給定的關鍵字key進行比較

2、如果查找到某個記錄的關鍵字等于key，則查找成功，返回該記錄的地址。如果所有記錄的關鍵字都與key進行了比較，但都未匹配，則本次查找失敗，返回失敗標記-1

//順序查找：n表示記錄個數、key表示要查找記錄的關鍵字、key[]為存放所有記錄關鍵字順序表。
int sq_search(keytyped key[],int n,keytype key)
{int i;for (i=0;i<n;i++){if (key[i] == key){return i;}}return -1;
}

用結構體描述:

typedef struct {keytype key;		//keytype類型的關鍵字keydatatype data;		//記錄其中信息
}RecordType;
int sq_search(RecordType r[], int n, keytype key)
{int i;for (i = 0;i < n;i++){if (r[i].key == key)		//查找成功{return i;}}return -1;
}
//缺點：平均查找長度過大，查找效率較低

2、折半查找

只有在關鍵字的排序是有序的(遞增或遞減)情況下，才能應用折半查找的算法描述。

基本思想：

減少查找序列的長度，分而治之進行關鍵字的查找。

查找過程：先去定待查找記錄的所在反胃，然后逐漸縮小查找的范圍，直到找到為止(也可能查找失敗)

//基于遞增序列的折半查找
//n表示記錄個數、k表示要查找到的關鍵字、key[]關鍵字順序表
int bin_search(keytype key[], int n, keytype k)
{int low = 0, high = n - 1, mid;while (low <= high){mid = (low+high) / 2;if (key[mid] == k)return mid;if (k > key[mid])low = mid + 1;		//在后半序列中查找elsehigh = mid - 1;}return -1;					//查找失敗，返回-1
}

用結構體描述：

typedef struct {keytype key;			//關鍵字datatype data;			//記錄的信息
}RecordType;int bin_search(RecordType r[], int n, keytype key)
{int low = 0, high = n - 1, mid;while (low <= high){mid = (low + high) / 2;if (r[mid].key == key)return mid;if (key > r[mid].key)low = mid + 1;		//在后半序列中查找elsehigh = mid - 1;}return -1;					//查找失敗，返回-1
}

3、直接插入排序

排序可以理解為：
根據文件記錄的關鍵字值得遞增或者遞減關系將文件記錄的次序進行重新排列的過程。
或者是：將一個按值無序的數據序列轉換成為一個按值有序的數據序列的過程
直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表。

在日常生活中，經常碰到這樣一類排序問題：把新的數據插入到已經排好的數據列中。例如：一組從小到大排好順序的數據列{1,2,3,4,5,6,7,9,10}，通常稱之為有序列，我們用序號1,2,3，…表示數據的位置，欲把一個新的數據8插入到上述序列中。

完成這個工作的步驟：
①確定數據“8”在原有序列中應該占有的位置序號。數據“8”所處的位置應滿足小于或等于該位置右邊所有的數據，大于其左邊位置上所有的數據。

②將這個位置空出來，將數據“8”插進去。
直接插入排序(straight insertion sort)的做法是：
每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個數，然后把第二個數按大小插入到有序表中；第二趟把第三個數據與前兩個數從后向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。
直接插入排序是由兩層嵌套循環組成的。外層循環標識并決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的并將待比較數值置入其后一位置，結束該次循環。

#include<iostream>
using namespace std;
void Insertsort(int a[],int k)
{int i, j;for (i = 1;i < k;i++)//循環從第2個元素開始{if (a[i] < a[i - 1]){int temp = a[i];for (j = i - 1;j >= 0 && a[j] > temp;j--){a[j + 1] = a[j];}a[j + 1] = temp;//此處就是a[j+1]=temp;}}
}
int main()
{int a[] = { 98,76,109,34,67,190,80,12,14,89,1 };int k = sizeof(a) / sizeof(a[0]);Insertsort(a,k);for (int f = 0;f < k;f++){cout << a[f] << "  ";}return 0;
}

4、選擇排序

基本思想：第i趟排序從序列后n-i+1個元素中選擇一個最小的元素，與該n-i+1個元素的最前面那個元素進行位置交換，也就是與第i個位置上的元素進行交換,直道n=i-1；

直觀講，每一趟的選擇排序就是從序列中未排好順序的元素中選擇一個最小的元素，將鈣元素與這些未排好的元素中的第一個元素交換位置。

void Selectsort(int a[], int k)
{int i, j,min;int tmp;for (i = 0;i < k;i++){min = i;for (j = i + 1;j < k;i++){if (a[j] <= a[min]){min = j;}}if (min != i)      //如果找到比a[min]還要小的值就進行交換位置，否則不交換{tmp = a[min];a[min] = a[i];a[i] = tmp;}}
}

5、冒泡排序

基本思想描述：

1、將序列中的第一個元素和第二個元素進行比較，若前者大于后者，則將第一個元素與第二個元素進行位置交換，否則不交換

2、將第2個元素與第3個元素進行比較，同樣若前者大于后者，則將第2個元素與第3個元素進行位置交換，否則不交換。

3、以此類推，直到將第n-1個元素與第n個元素進行比較為止。此過程稱為第1趟冒泡排序，進過第21趟冒泡排序后，將長度為n的序列中最大的元素置于序列的尾部，即第n個位置上。

4、之后再進行第2趟…第n-1趟排序。冒泡排序完成。

改進思路：

以序列3 6 4 2 11 10 6為例：

第一趟bubblesort之后：

3 4 2 6 10 6 11

第二趟bubblesort之后：

3 2 4 6 6 10 11

第三趟bubblesort之后：

2 3 4 6 6 10 11

這時再進行冒泡排序就會發現，序列本身不會再發生變化，只有相鄰元素的比較，而沒有相鄰元素的交換，也就是說此時排序已經完成了。

所以可以這樣改進：

如果某一趟排序過程中只有元素之間的比較而沒有元素之間的位置交換，說明排序完成。

void ImprovedBubblesort(int a[], int n)
{int i, j;int tmp;int flag = 1;               //flag=1，說明本趟排序中仍有元素交換動作for (i = 0;i < n && flag==1;i++)       //趟次，一共n-1次{flag = 0;for (j = 0;j < n - 1;j++)  //元素交換{if (a[j] > a[i]){flag = 1;tmp = a[j];a[j] = a[i];a[i] = tmp;}}}
}

6、希爾排序

基本思路：

1、設定一個元素間隔增量gap，將參加排序的序列按照這個間隔數gap從第1個元素開始依次分成若干個子序列。

2、在子序列中可以采用其他的排序方法，例如冒泡排序。

3、縮小增量gap，重新將整個序列按照新的間隔數gap進行劃分，再分別對每個子序列排序。過程描述：縮小增量gap–>劃分序列–>將子序列排序

4、直到間隔數gap=1為止。

希爾排序過程：
在這里插入圖片描述
思考：如何確定間隔數gap？
數學上仍然是一個尚未解決的難題，但是經驗告訴我們一種比較常用且效果好的方法:
1、首先gap取值為序列長度的一半
2、后續排序過程中，后一趟排序的gap取值為前一趟排序gap的一半取值
算法描述：

void Shellsort(int a[], int n)
{int i, j;int tmp;int flag = 1;              int gap = n;            //第一次gap為nwhile (gap > 1){//確定gapgap = gap / 2;//以gap劃分子序列，每一次迭代都是一組子序列的一趟自排序(冒泡)do {flag = 0;for (i = 0;i < n - gap;i++){j = i + gap;if (a[j] < a[i]){flag = 1;tmp = a[j];a[j] = a[i];a[i] = tmp;}}} while (flag==1);}
}

7、快速排序

基本思想：
1、在當前的排序序列中任意選取一個元素，把該元素稱為基準元素或支點，把下雨等于基準元素的所有元素都移動到基準元素的前面，把大于基準元素的所有元素都移到基準元素的后面，這樣使得基準元素所處的位置恰好就是排序的最終位置，并且把當前參加排序的序列分為前后兩個序列。
2、上述的過程稱為一趟快速排序，即快速排序的一次劃分
3、接下來分別對這兩個子序列重復上述的排序操作（如果子序列長度大于1的話），直到所有元素都被移動到排序后他們應處的最終位置上。
效率之所以高：每一次元素的移動都是跳躍的，不會像冒泡排序只能在相鄰元素之間進行，元素移動的間隔較大，因此總的比較和移動次數減少

具體步驟：

1、假設序列a，設置兩個變量i、j.分別指向首元素和尾元素，設定i指向的首元素為基準元素

2、反復執行i++，直到i指向的元素>=基準元素，或者i指向尾部

3、反復執行j–，直到指向的元素<基準元素，或者j指向頭部

4、若此時i<j，將i和j指向的元素進行交換。（大的元素在后面）

5、完成第一次交換后，重復執行步驟1、2，直到i>=j位置

6、此時i>=j，然后將基準元素與j指向的元素交換位置，至此完成了原序列的第一次劃分

7、接下來分別對基準元素前后的子序列中長度大于1的子序列重復執行上述操作。

步驟分析：

對于每個子序列的操作又是一次劃分，因此這個算法具有遞歸性質。

每次劃分過程的基準元素仍可設定為子序列的第一個元素

//快速排序
void Quicksort(int a[], int s,int t)
{int i, j;if (s < t){//【1】設置兩個變量i、j.分別指向首元素和尾元素，設定i指向的首元素為基準元素i = s;j = t + 1;while (1){do i++;while(!(a[s]<=a[i] || i==t));               //【2】重復i++操作，直到i指向的元素>=基準元素，或者i指向尾部do j--;while (!(a[s]>=a[j] || j==s));              //【3】反復執行j--，直到指向的元素<基準元素，或者j指向頭部if (i < j)                                  //【5】若此時i<j，將i和j指向的元素進行交換。（大的元素在后面）{swap(a[j], a[i]);}else break;                                  //【5】完成第一次交換后，重復執行步驟1、2，直到i>=j位置}//【6】此時i>=j，然后將基準元素與j指向的元素交換位置，至此完成了原序列的第一次劃分swap(a[s],a[j]);//【7】接下來分別對基準元素前后的子序列中長度大于1的子序列重復執行上述操作。Quicksort(a,s,j-1);                             //前半序列Quicksort(a,j+1,t);                             //后半序列}
}

快速排序只適用于順序表線性結構或者數組序列的排序，不適合在鏈表上實現

8、堆排序

heapsort是選擇排序的改進。

首先了解一下堆的概念：

堆通常是一個可以被看做一棵完全二叉樹的數組對象。

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)

堆總是滿足下列性質：

1、堆中某個節點的值總是不大于或不小于其父節點的值；

2、堆總是一棵完全二叉樹。

了解一下完全二叉樹的概念：

https://blog.csdn.net/judgejames/article/details/87868602

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆

舉例：

序列{49,22,40,20,18,36,6,12,17}
在這里插入圖片描述
基于大頂堆的完全二叉樹表示的堆排序的核心思想可描述如下：

1、將原始序列構成一個堆(建立初始堆)

2、交換堆的第一個元素和堆的最后一個元素

3、將交換最大值元素之后的剩余元素所構成的序列再轉換成一個堆

4、重復上述2、3步驟n-1次

經過上述操作，就可以將一個無序的序列從小到大進行排序。

關鍵問題：

1、如何原始序列構成一個堆

2、如何將交換最大值元素之后的剩余元素所構成的序列再轉換成一個堆

第二個問題：

該二叉樹雖然不是一個堆，但是除了根結點外，其余任何一棵子樹仍然滿足堆的特性。

自上而下調整：將序號為i的結點與其左右孩子(2i 、2i+1)三個值中的最大值替換到序號為i的結點的位置上。

只要徹底地完成一次自上而下的調整，該二叉樹就會變成一個堆。

最后一步：交換第一個元素和新堆的最后一個元素的位置，也就是將最大的元素移至新堆的最后。

第一個問題：

如果原序列對應的完全二叉樹有n個結點，則：

1、初始化時，令序列號為i= Floor (n/2)，它對應于而擦函數中第 Floor (n/2)個結點(二叉樹中的結點按照層次編號，從1開始，從左到右，從上到下編號)

2、調用函數adjust調整

3、每執行完一次調整都執行一次i=i-1操作

4、重復步驟2、3，直到i==1時執行步驟5

5、最后再調用adjust函數調整一次。

這樣就完成調整了。

示例：初始序列為:{23,6,77,2,60,10,58,16,48,20}
在這里插入圖片描述
code:

//堆排序
//【1】將二叉樹調整為一個堆的函數：
//函數作用：將以第i個元素作為根結點的子樹調整為一個新的堆序列，前提是該子樹中除了根結點外其余的任何一個子樹仍然滿足堆的特性，如果該子樹除了根結點外其他子樹也不完全是
//堆結構的話，則不能僅通過依次調用adjust函數就將其調整為堆
//輸入：序列a   i:序列a中的元素下標
void BiTreeAdjustToHeap(int a[],int i,int n)
{int j;int tmp;tmp = a[i];j = 2 * i;      //j為i的左孩子結點序號while (j <= n){if (j < n && a[j] < a[j + 1]){j++;                //j為i的左右孩子中較大孩子的序號}if (tmp >= a[j])        //如果父結點值比孩子值還大就不需要調整了{break;}a[j / 2] = a[j];       //較大的子節點與父節點交換位置j = 2 * j;             //繼續向下調整}a[j / 2] = tmp;
}//【2】原始序列初始化函數
void InitHeap(int a[],int n)
{for(int i=n/2;i>=0;i--){BiTreeAdjustToHeap(a,i,n);}
}
//堆排序函數
void Heapsort(int a[], int n)
{int i = 0;//【1】原始序列初始化函數InitHeap(a,n);//【2】交換第1個和第n個元素，再將根結點向下調整for (i = n - 1;i >= 0;i--){swap(a[i+1],a[0]);BiTreeAdjustToHeap(a,0,i);      //將根結點向下調整}
}

需要把握的要點：

1、堆排序是針對線性序列的排序，之所以要采用完全二叉樹的形式解釋堆排序的過程，是出于方便解釋的需要

2、堆排序的第一步是將原序列變成一個對序列

3、一系列的交換調整操作。所謂交換就是將堆中第一個元素與本次調整范圍內的新堆的最后一個元素交換位置，使得較大的元素能夠置于序列的最后面，所謂調整就是將交換后的剩余元素從上至下調整為為一個新堆的過程。

4、通過2、3操作可以將一個無序序列從小到大偶愛徐

5、如果基于大頂堆進行堆排序，則排序后的序列從小到大。若是基于小頂堆，則從大到小。

9、排序算法性能比較

排序算法	平均時間	最壞情況	空間需求
直接插入排序	O(n^2)	O(n^2)	O(1)
冒泡排序	O(n^2)	O(n^2)	O(1)
簡單選擇排序	O(n^2)	O(n^2)	O(1)
希爾排序	O(nlog2n)	O(nlog2n)	O(1)
快速排序	O(nlog2n)	O(n^2)	O(nlog2n)
堆排序	O(nlog2n)	O(nlog2n)	O(1)

總結：

1、如果參加排序的序列最開始就是基本有序或者局部有序的，使用這直接插入排序和冒泡排序的效果較好，排序速度較快，最好的情況下(原序列按值有序)，時間復雜度O(n)

2、快速排序最快，堆排序空間消耗最小

3、序列中元素個數越小，采用冒泡排序排序算法、直接插入排序、簡單選擇排序較合適

當序列規模變大時，采用希爾排序、快速排序和堆排序比較合適

4、從穩定性來講：直接插入、冒泡是穩定的排序方法。簡單選擇排序、希爾排序、快速排序、堆排序是不穩定的排序算法

10、所有算法的code（C語言）

#include<iostream>
using namespace std;
void swap(int& a, int& b)
{//方法一：   int tmp = 0;tmp = b;b = a;a = tmp;//方法二：   //a = a+b;   //b = a-b;   //a = a -b;   //方法三：   //a ^= b ^= a ^= b;   //方法四：    冒泡和希爾和改進冒泡，使用這個方法不成功         //a = a+b-(b=a);   
}
//參考：https://blog.csdn.net/shangguanyunlan/article/details/51778378         //
void Insertsort(int a[],int k)
{int i, j;for (i = 1;i < k;i++)//循環從第2個元素開始{if (a[i] < a[i - 1]){int temp = a[i];for (j = i - 1;j >= 0 && a[j] > temp;j--){a[j + 1] = a[j];}a[j + 1] = temp;//此處就是a[j+1]=temp;}}
}
//選擇排序
void Selectsort(int a[], int k)
{int i, j,min;int tmp;for (i = 0;i < k;i++){min = i;for (j = i + 1;j < k;i++){if (a[j] <= a[min]){min = j;}}if (min != i)      //如果找到比a[min]還要小的值就進行交換位置，否則不交換{swap(a[min],a[i]);}}
}
//冒泡排序
void Bubblesort(int a[], int n)
{int i, j;int tmp;for (i=0;i<n;i++)       //趟次，一共n-1次{for (j = 0;j < n - 1;j++)  //元素交換{if (a[j] > a[i]){swap(a[j], a[i]);}}}
}
//改進的冒泡排序
void ImprovedBubblesort(int a[], int n)
{int i, j;int tmp;int flag = 1;               //flag=1，說明本趟排序中仍有元素交換動作for (i = 0;i < n && flag==1;i++)       //趟次，一共n-1次{flag = 0;for (j = 0;j < n - 1;j++)  //元素交換{if (a[j] > a[i]){flag = 1;swap(a[j], a[i]);}}}
}
//希爾排序
void Shellsort(int a[], int n)
{int i, j;int tmp;int flag = 1;              int gap = n;            //第一次gap為nwhile (gap > 1){//確定gapgap = gap / 2;//以gap劃分子序列，每一次迭代都是一組子序列的一趟自排序(冒泡)do {flag = 0;for (i = 0;i < n - gap;i++){j = i + gap;if (a[j] < a[i]){flag = 1;swap(a[j], a[i]);}}} while (flag==1);}
}
//快速排序
void Quicksort(int a[], int s,int t)
{int i, j;if (s < t){//【1】設置兩個變量i、j.分別指向首元素和尾元素，設定i指向的首元素為基準元素i = s;j = t + 1;while (1){do i++;while(!(a[s]<=a[i] || i==t));               //【2】重復i++操作，直到i指向的元素>=基準元素，或者i指向尾部do j--;while (!(a[s]>=a[j] || j==s));              //【3】反復執行j--，直到指向的元素<基準元素，或者j指向頭部if (i < j)                                  //【5】若此時i<j，將i和j指向的元素進行交換。（大的元素在后面）{swap(a[j], a[i]);}else break;                                  //【5】完成第一次交換后，重復執行步驟1、2，直到i>=j位置}//【6】此時i>=j，然后將基準元素與j指向的元素交換位置，至此完成了原序列的第一次劃分swap(a[s],a[j]);//【7】接下來分別對基準元素前后的子序列中長度大于1的子序列重復執行上述操作。Quicksort(a,s,j-1);                             //前半序列Quicksort(a,j+1,t);                             //后半序列}
}//堆排序
//【1】將二叉樹調整為一個堆的函數：
//函數作用：將以第i個元素作為根結點的子樹調整為一個新的堆序列，前提是該子樹中除了根結點外其余的任何一個子樹仍然滿足堆的特性，如果該子樹除了根結點外其他子樹也不完全是
//堆結構的話，則不能僅通過依次調用adjust函數就將其調整為堆
//輸入：序列a   i:序列a中的元素下標
void BiTreeAdjustToHeap(int a[],int i,int n)
{int j;int tmp;tmp = a[i];j = 2 * i;      //j為i的左孩子結點序號while (j <= n){if (j < n && a[j] < a[j + 1]){j++;                //j為i的左右孩子中較大孩子的序號}if (tmp >= a[j])        //如果父結點值比孩子值還大就不需要調整了{break;}a[j / 2] = a[j];       //較大的子節點與父節點交換位置j = 2 * j;             //繼續向下調整}a[j / 2] = tmp;
}//【2】原始序列初始化函數
void InitHeap(int a[],int n)
{for(int i=n/2;i>=0;i--){BiTreeAdjustToHeap(a,i,n);}
}
//堆排序函數
void Heapsort(int a[], int n)
{int i = 0;//【1】原始序列初始化函數InitHeap(a,n);//【2】交換第1個和第n個元素，再將根結點向下調整for (i = n - 1;i >= 0;i--){swap(a[i+1],a[0]);BiTreeAdjustToHeap(a,0,i);      //將根結點向下調整}
}
void show_sort_result(int a[],int k)
{for (int f = 0;f < k;f++){cout << a[f] << "  ";}printf("\n");
}
int main()
{int a[] = { 98,76,109,34,67,190,80,12,14,89,1 };int k = sizeof(a) / sizeof(a[0]);//printf("直接插入排序\n");//Insertsort(a,k);//show_sort_result(a,k);//printf("選擇排序\n");//Insertsort(a, k);//show_sort_result(a,k);//printf("冒泡排序\n");//Bubblesort(a, k);//show_sort_result(a, k);//printf("改進后的冒泡排序\n");//ImprovedBubblesort(a, k);//show_sort_result(a, k);//printf("希爾排序\n");//Shellsort(a, k);//show_sort_result(a, k);//printf("快速排序\n");//Quicksort(a,0,k-1);//show_sort_result(a, k);//printf("堆排序\n");//Heapsort(a,k-1);//show_sort_result(a, k);return 0;
}