C語言實現(xiàn)經(jīng)典排序算法的示例代碼
一、冒泡排序
1.原理
從數(shù)組的頭開始不斷比較相鄰兩個數(shù)的大小,不斷將較大的數(shù)右移,一個循環(huán)后,最大數(shù)移至最后一位,無序數(shù)組規(guī)模減一。不斷重復前面動作,知道數(shù)組完全有序。
2.實現(xiàn)
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubble_sort(int* arr, int len) { bool issort = false; while (!issort) { issort = true;//如果有序則直接退出 for (int i = 1; i < len; i++) { if (arr[i-1] > arr[i])//不斷比較相鄰兩個數(shù) { swap(&arr[i - 1], &arr[i]);//將較大的數(shù)不斷往右移 issort = false;//如果進行了交換則無序 } } len--;//無序規(guī)模減一 } }
3.算法分析
時間復雜度: 最好情況,當數(shù)組完全有序,則只需要進行一輪比較,時間復雜度為o(n);最壞情況為完全無序,每次比較后都要將該數(shù)移至數(shù)組末尾,時間復雜度為o(n ^2);平均時間復雜度為o(n ^2)。
空間復雜度: 冒泡排序為就地排序,空間復雜度為o(1)。
穩(wěn)定排序: 當數(shù)字相同時不會改變相對次序。
二、選擇排序
1.原理
數(shù)組前面為無序,后面為有序。剛開始全是無序,從中選擇一個最大值與最后一個無序數(shù)字進行交換,無序數(shù)組規(guī)模減一,有序數(shù)組規(guī)模加一。不斷循環(huán)前面操作,直到數(shù)組變?yōu)橛行驍?shù)組?;蛘咔懊鏋橛行驍?shù)組,后面為無序數(shù)組,不斷選擇最小值與無序數(shù)組的第一個數(shù)交換,前面的有序數(shù)組加一,后面的無序數(shù)組減一。
2.實現(xiàn)
void selection_sort(int* arr, int len) { int max_index; while (len) { max_index = 0; for (int i = 1; i < len; i++) { if (arr[max_index] < arr[i]) { max_index = i;//獲取最大值的索引 } } swap(&arr[max_index], &arr[len - 1]);//將最大值與最后一個值交換 len--;//無序規(guī)模減一 } }
3.算法分析
時間復雜度: 所有的復雜度為每次選擇最大值,不管數(shù)字的有序性,時間復雜度都為o(n)+o(n-1)+…+o(1)=o(n^2)。所以該算法平均復雜度、最好情況、最差情況都為o(n ^2)。
空間復雜度: 就地排序,空間復雜度為o(1)。
不穩(wěn)定性算法: 排序后相同元素的順序可能被打亂。例子:選擇最大進行排序。3,1,2,2* 第一輪排序后 2*,1,2,3 2的相對順序發(fā)生了改變。選擇最小進行排序,2*,2,3,1 第一輪排序后1,2,3,2*. 2的相對順序也被打亂。如果增加空間復雜度也能將選擇排序變成穩(wěn)定性排序。
三、插入排序
1.原理
數(shù)組前面為有序,后面為無序,將無序數(shù)組中的第一個數(shù)不斷插入有序數(shù)組中(具體實現(xiàn)為不斷比較相鄰兩數(shù)大小,前面一個數(shù)大于后一個數(shù),則交換順序,較小的數(shù)不斷前移),有序規(guī)模增加一,無序規(guī)模減小一。或者,數(shù)組前面為無序,后面為有序,通過將無序數(shù)組的最后一位數(shù)字插入有序數(shù)組中(具體實現(xiàn)為將無序數(shù)組的最后一位與相鄰的有序數(shù)組不斷比較,將無序數(shù)組不斷右移)。
2.實現(xiàn)
void insert_sort(int arr[], int len) { for (int i = 1; i < len; i++)//i前面為有序 { for (int j = i - 1; j >= 0; j--)//j為有序數(shù)的末尾 { bool issort = true;//當數(shù)組有序時能夠提前退出 if (arr[j] > arr[j + 1])//將無序數(shù)組的第一個數(shù)不斷與有序數(shù)組比較 { swap(&arr[j], &arr[j + 1]);//將無序數(shù)字插入有序數(shù)組合適的位置 issort = false; } if (issort) break; } } }
3.算法分析
時間復雜度: 插入排序和冒泡排序類似,最好情況完全有序則時間復雜度為o(n),最壞情況為完全無序時間復雜度為o(n^2),平均復雜度為o(n ^2)。
空間復雜度: 就地排序不需要額外空間,空間復雜度為o(1)。
穩(wěn)定性排序: 和冒泡排序類似。
四、希爾排序
1.原理
每次選擇一個增量進行分組,增量不斷減小到一(為插入排序),數(shù)組不斷變得有序,增量為一時變成完全有序。屬于插入排序的改進,通過增量進行分組,對每一組進行插入排序,相比于插入排序的優(yōu)勢在于,shell排序能夠大尺度的移動每一組的最小值,而插入排序得挨著進行比較,所以shell排序效率更高。
增量為6:
每一組只有兩個數(shù),分別比較兩個數(shù)的大小,如64,57交換順序變成57,64,所有的分組比較完后繼續(xù)縮減增量。
增量為3:
每一組有四個數(shù),總共三組,分別為23,12,53,79;57,9,64,87;24,16,71,97;以增量開始(12開始)遍歷數(shù)組,遍歷到12則在第一組中對12進行插入排序,交換23和12的順序;遍歷到9則在第二組對9進行插入排序。。。。遍歷到64對一組中的9,57,64進行插入排序。最后每一組都變得有序。整體有序性變大。
增量為1:
對之前排序過的數(shù)組進行插入排序,通過前面的步驟數(shù)組有序性變大,最后進行插入排序的效率就更高。
2.實現(xiàn)
void shell_sort(int* arr, int len) { int gap = 0; //分組的跨度 int i = 0; int j = 0; for (gap = len / 2; gap >= 1; gap /= 2) //分組增量 { for (i = gap; i < len; i++) { //遍歷每組 for (j = i - gap; j >= 0; j -= gap) //對組內(nèi)進行插入排序 { if (arr[j] > arr[j + gap]) { swap(&arr[j], &arr[j + gap]); } } } } }
3.算法分析
時間復雜度:最好情況為完全有序o(n),最差情況為完全無序o(n^2),平均復雜度為o(n ^1.3)。
空間復雜度:該算法為就地排序空間復雜度為o(1)。
穩(wěn)定性:shell排序在分組中可能將相同數(shù)字劃分成不同的分組,會改變相對順序,屬于不穩(wěn)定性排序算法。
總結
冒泡排序、選擇排序、插入排序、希爾排序的實現(xiàn)都是基于線性表進行實現(xiàn)的(數(shù)組或者鏈表),實現(xiàn)邏輯都是通過比較數(shù)字的大小。算法的時間復雜度都比較大,但是屬于就地排序,不需要額外空間。幾種算法相比之下希爾排序更具有優(yōu)勢。
到此這篇關于C語言實現(xiàn)經(jīng)典排序算法的示例代碼的文章就介紹到這了,更多相關C語言排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
如何利用C++實現(xiàn)mysql數(shù)據(jù)庫的連接池詳解
為了提高MySQL數(shù)據(jù)庫的訪問的瓶頸,除了在服務器端增設緩存服務器緩存常用的數(shù)據(jù)之外(如redis),還可以增加數(shù)據(jù)庫連接池,來提高MySQL Server的訪問效率,這篇文章主要給大家介紹了關于如何利用C++實現(xiàn)mysql數(shù)據(jù)庫的連接池的相關資料,需要的朋友可以參考下2021-07-07