一、算法的基本概念

算法是指對解題方案準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。

算法中的指令描述的是一個計算過程，在它的作用下，系統從初始狀態和初始輸入（也可能沒有）開始，經歷一系列有限且被明確定義的中間狀態，最終產生所要求的輸出，并停止于終止狀態。

同一個問題，不同的算法，可能會在時間、空間等方面表現出明顯的差異，一個算法的優劣可以用時間復雜度和空間復雜度來衡量。

二、算法的基本特征

（1）有窮性 算法必須能在執行有限個步驟后終止 （2）確切性 算法的每一個步驟必須有確切的定義 （3）輸入項 算法有規范化的輸入，以表示運算對象的初始狀態 （4）輸出項 算法至少有一個輸出，以反映處理的最終結果 （5）可行性 算法中的每個執行步驟都必須能在有限時間內完成

三、算法的基本要素

（1）運算和操作 計算機可以執行的基本操作是以指令的形式描述的，包括如下四類： 算數運算：加、減、乘、除、模等 關系運算：大于、小于、等于、不等于等 邏輯運算：與、或、非等運算 數據傳輸：輸入、輸出、賦值等 （2）流程和控制 算法的功能不僅取決于所選用的操作，還與各操作之間的執行順序有關

四、算法的評定標準

（1）時間復雜度 算法的時間消耗與問題規模之間的函數關系：T(N) = O(F(N)) （2）空間復雜度 算法的空間消耗與問題規模之間的函數關系：S(N) = O(F(N)) （3）正確性 執行算法的結果是否滿足要求 （4）可讀性 算法本身可供人們閱讀的難易程度 （5）健壯性 算法對非正常輸入的反應和處理能力，亦稱容錯性

五、算法的思想

（1）遞推法 通過計算前面的一些項來得出序列中指定項的值，其思想是把一個復雜而龐大的計算過程轉化為簡單過程的多次重復，充分發揮計算機速度快且不知疲倦的特點 （2）遞歸法 把大問題轉化為與原問題相似的小問題來求解，遞歸的神奇之處在于用有限的語句來定義無線的對象集合。遞歸需要有終止條件，遞歸前進段和遞歸返回段，若終止條件不滿足則遞歸前進，否則遞歸返回。 （3）窮舉法 對于要解決的問題，列舉出它所有的可能性，逐個判斷其中哪些符合問題所要求滿足的條件，從而得到問題的解。 （4）貪心算法 自頂向下，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇，就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到相應子問題的一個最優解，雖然每一步都能保證局部解最優，但最終得到的全局解未必最優。 （5）分治法 把一個復雜問題分成兩個或更多仙童或相似的子問題，再把子問題分成更小的子問題。。。直到最后的子問題可以簡單地直接求解，原問題的解即子問題解的分并。 （6）動態規劃法 將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。 （7）迭代法 按照一定的規則，不斷地用舊值推算出新值，直到滿足某種特定條件為止。利用計算機速度快、擅長簡單重復的特點，讓計算機重復執行若干步驟，并在每次執行這些步驟時，都從舊值算出新值。 （8）分支界限法 把全部可行的解孔家不斷分割為越來越小的子集，謂之分支，并為每個子集計算一個下界或上界，謂之定界。在每次分支后，對界限超出已知可行解的子集不再做進一步分支，搜索范圍迅速收斂。這一過程一直進行到找出可行解為止，該可行解的值不大于任何子集的界限，因此這種算法一般可以求得全局最優解。 （9）回朔法 在包含問題所有解的解空間樹中，從根節點出發，按深度優先搜索解空間樹，當搜索到某一節點時，先判斷該節點是否包含問題的解，若包含則從節點出發繼續搜索，否則逐層向其父節點回溯。若希望求得問題的所有解，則必須回溯到根，且根節點的所有可行子樹都必須被搜索到才能結束，否則只要搜索到問題的一個解即可終止。

六、算法的分類

算法按其執行期限可被分為： （1）有限算法 算法過程無論長短，總能在有限的時間內終止 （2）無限算法 算法過程因無終止條件或終止條件無法得到滿足，而永不停息 算法按其解的確定性可被分為： （1）確定性算法 對于確定的輸入，算法總能得到確定的結果 （2）非確定算法 對于確定的輸入，算法得到的結果并不唯一確定

七、常見的查找算法

1、線性查找（順序查找）

（1）算法描述 從頭開始，依次將每一個元素與查找目標進行比較，直到找到目標元素，或者與所有元素比較完畢，表示查找失敗。 （2）算法評價 平均時間復雜度：O(N) 對數據的有序性沒有要求 （3）線性查找實現 //線性查找算法的實現 #include <stdio.h>int find (int arr[], int data, int num) {int i = 0;for (i = 0; i < data; i++){if (arr[i] == num){return i;}} }int main (void) {int arr[9] = {1, 5, 4, 3, 6, 8, 9, 2, 7};printf ("元素3所在的下標是：%d\n", find (arr, 9, 2));return 0; } 輸出結果： 元素2所在的下標是：7

2、二分查找

（1）算法描述 首先假設所有的元素按照升序排列，使用中間元素和目標元素進行比較，如果相等則查找成功，如果中間元素小于目標元素，則去中間元素的右側查找，否則去中間元素的左側查找，重復以上過程直到查找成功，或者查找失敗。
（2）算法評價 平均時間復雜度：O(logN) 要求樣本元素必須有序 （3）基于遞歸的二分查找實現 //基于遞歸的二分查找算法實現 #include <stdio.h> int find (int arr[], int left, int right, int data) {//表示向右縮進if (left <= right){//1.計算中間元素的下標int p = (left + right) / 2;//2.使用中間元素和目標元素進行比較，如果相等，則直接返回下標if (arr[p] == data)return p;//3.如果中間元素小于目標元素，則去中間元素的右側繼續查找 else if (arr[p] < data)return find (arr, p+1, right, data);//4.如果中間元素大于目標元素,則去中間元素的左側繼續查找 elsereturn find (arr, left, p - 1, data);}//5.比較完畢，查找失敗else{printf ("查找失敗\n");return -1;} }int main (void) {int arr[9] = {11, 22, 33, 44, 55, 66, 77, 88, 99};//調用查找函數查找元素33,返回下標printf("元素33所在的下標是：%d\n",find(arr,0,8,33)); // 2printf("元素60所在的下標是：%d\n",find(arr,8,0,60)); // -1return 0; } 輸出結果： 元素33所在的下標是：2 查找失敗 元素60所在的下標是：-1（4）基于循環的二分查找實現 //基于循環的二分查找實現 #include <stdio.h> int find (int arr[], int left, int right, int data) {while (left <= right){int p = (left + right) / 2;if (arr[p] == data)return p;else if (arr[p] > data)right = p - 1;elseleft = p + 1;}if (left > right){printf ("查找失敗\n");return -1;} }int main (void) {int arr[9] = {11, 22, 33, 44, 55, 66, 77, 88, 99};//調用查找函數查找元素33,返回下標printf("元素33所在的下標是：%d\n",find(arr,0,8,33)); // 2printf("元素44所在的下標是：%d\n",find(arr,8,0,44)); // -1return 0; } 輸出結果： 元素33所在的下標是：2 查找失敗 元素44所在的下標是：-1（5）二分查找說明

八、常見的排序算法

1、冒泡排序算法

（1）算法描述 相鄰元素兩兩比較，前者大于后者，彼此交換。 從第一對到最后一對，最大的元素沉降到最后。 針對未排序部分，重復以上步驟，沉降次大值。 每次掃描越來越少的元素，直至不再發生交換。 （2）算法評價 平均時間復雜度 O(N^2) 穩定排序，對數據的有序性非常敏感
（3）冒泡排序算法實現 //冒泡排序函數 #include <stdio.h> void bubble (int arr[], int len) {int i = 0, j = 0;//外層循環控制比較的輪數for (i = 1; i < len; i++){// 內層循環控制對當前輪數的下標訪問 for (j = 0; j < len - i; j++){//如果左邊元素大于等于右邊交換if (arr[j] >= arr[j + 1]){//防止數據丟失，找個替身int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}} }int main (void) {int arr[9] = {20, 8, 25, 3, 15, 9, 30, 5, 22};bubble (arr, 9);//調用排尋算法進行排序//冒泡排序int i = 0;for (i = 0; i < 9; i++)printf ("%d ", arr[i]);printf ("\n");return 0; } 輸出結果： 3 5 8 9 15 20 22 25 30 （4）冒泡排序說明

2、插入排序算法

（1）算法描述 首元素自然有序 取出下一個元素，對已排序序列，從后向前掃描 大于被取出元素者后移 小于等于被取出元素者，將被取出元素插入其后 重復步驟2，直至處理完所有元素 （2）算法評價 平均時間復雜度 O(N^2) 穩定排序， 對數據的有序性份額長敏感，但是賦值的次數比冒泡排序少，因此略優于冒泡排序算法。 （3）插入排序算法實現 //插入排序算法的實現 #include <stdio.h> //將第一元素看作有序 //假定已經有序，依次比較 void insert (int arr[], int len) {int i = 0, j = 0;//1.從第二個元素起，一次取出每一個元素//外層循環控制比較的輪數for (i = 1; i < len; i++){//保存取出的元素 第二個元素int temp = arr[i];//2.使用取出的元素和左邊有序元素比較，如果左邊元素大于取出元素，則右邊元素右移for (j = i; j > 0; j--){if (arr[j - 1] > temp)arr[j] = arr[j - 1];elsebreak;}if (i != j)arr[j] = temp;} }int main (void) {int arr[9] = {20, 8, 25, 3, 15, 9, 30, 5, 22};//調用排尋算法進行排序//插入排序insert (arr, 9);int i = 0;for (i = 0; i < 9; i++)printf ("%d ", arr[i]);printf ("\n");return 0; } 輸出結果： 3 5 8 9 15 20 22 25 30 （4）插入排序說明

3、選擇排序算法

（1）算法描述 在整個序列中尋找最小元素，與首元素交換 在剩余序列中尋找最小元素，與次元素交換 依次類推，知道剩余序列中僅包含一個元素 （2）算法評價 平均時間復雜度：O(N^2) 非穩定排序 對數據的有序性不敏感 交換次數少，優于冒泡排序 （3）選擇排序算法實現 //選擇排序算法的實現 #include <stdio.h> //假定最小值與實際最小值 void choose (int arr[], int len) {//1.從第一個元素起依次取出，記錄下標int i = 0, j = 0;for (i = 0; i < len; i++){int min = i;//最小值下標為0//2.使用記錄的最小值與后續元素比較，如果后續元素小于記錄的最小值，則重新記錄下標for (j = i + 1; j < len; j++){if (arr[j] < arr[min])//下標1 < 下標0min=j;//最小值下標變為 下標 1}//3.直到記錄的最小值和后續元素比較完畢，則交換記錄的最小值和最開始假定的最小值//一開是假定的最小值是這組數中最小的if (i != min){int temp = arr[i];arr[i] = arr[min];arr[min] = temp;}} }int main (void) {int arr[9] = {20, 8, 25, 3, 15, 9, 30, 5, 22};//調用排尋算法進行排序//選擇排序算法choose (arr, 9);int i = 0;for (i = 0; i < 9; i++)printf ("%d ", arr[i]);printf ("\n");return 0; } 輸出結果： 3 5 8 9 15 20 22 25 30 （4）選擇排序說明

4、快速排序算法

（1）算法描述 從待排序序列中任意挑選一個元素，作為基準 將所有小于基準的元素放在基準之前，大于基準的元素放在基準之后，等于基準的元素放在基準之前或之后，這個過程稱為分組 以遞歸的方式，分別對基準之前和基準之后的分組繼續進行分組，知道每個分組內的元素個數不多于 1 個為止 （2）算法評價 平均時間復雜度：O(NlogN) 非穩定排序 若每次都能均勻分組，則排序速度最快 （3）快速排序算法實現 //快速排序算法的實現 #include <stdio.h> //選好基準 void quick (int arr[], int left, int right) {//1.根據左邊元素和右邊元素下標計算出中間元素的下標int p = (left + right) / 2;//2.選擇中間元素作為基準值，保存int pivot = arr[p];//3.分別使用左右來年改變的元素與基準值進行比較int i = 0, j = 0;for(i = left, j = right; i < j;)//找一個替身{//首先使用左邊元素與基準值比較，如果左邊元素小于基準值則比較下一個元素while (arr[i] < pivot && i < p)i++;//如果左邊元素大于基準值，則將左邊元素賦值給p指向的位置，p指向數據來源的位置if (i < p){arr[p] = arr[i];p = i;//基準值不可賦值}//右邊元素方法同上while(arr[j] >= pivot && j > p)j--;if (j > p){arr[p] = arr[j];p = j;}//當i和j相等時，將基準值放到重合的位置上arr[p] = pivot;//分別對左邊元素和右邊元素進行遞歸排序if(p - left > 1)quick (arr, left, p - 1);if (right - p > 1)quick (arr, p + 1, right);} } int main() {int arr[9] = {20, 8, 25, 3, 15, 9, 30, 5, 22};//調用排尋算法進行排序//快速排序算法quick (arr, 0, 8);int i = 0;for(i = 0; i < 9; i++)printf ("%d ", arr[i]);printf ("\n");return 0; } 輸出結果： 3 5 8 9 15 20 22 25 30 （4）快速排序說明

5、歸并排序算法

（1）算法描述 將待排序序列從中間劃分為兩個相等的子序列 以遞歸的方式分別對兩個子序列進行排序 將兩個有序的子序列合并成完整的序列
有序合并： 分配合并序列，其大小為兩個有序序列大小之和 設定兩個指針，分別指向兩個有序序列的首元素 比較指針目標，嬌笑著進入合并序列，指針后移 重復步驟3，直到某一指針到達序列末尾 將另一序列的剩余元素直接復制到合并序列末尾 （2）算法評價 平均時間復雜度：O(2NlogN) 穩定排序 對數據的有序性不敏感 非就地排序，需要輔助空間，不適合處理海量數據 （3）歸并排序算法實現 #include<stdlib.h> #include<stdio.h>#define SIZE 8void Merge (int sourceArr[], int startIndex, int midIndex, int endIndex) {int start = startIndex;int i, j, k;int tempArr[SIZE];for (i = midIndex + 1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)if (sourceArr[startIndex] <= sourceArr[i])tempArr[j] = sourceArr[startIndex++];elsetempArr[j] = sourceArr[i++];if (startIndex <= midIndex)for (k = 0; k <= midIndex - startIndex; k++)tempArr[j + k] = sourceArr[startIndex + k];if (i <= endIndex)for (k = 0; k <= endIndex - i; k++)tempArr[j + k] = sourceArr[i + k];for (i = start; i <= endIndex; i++)sourceArr[i] = tempArr[i]; }//內部使用遞歸 void MergeSort (int sourceArr[], int startIndex, int endIndex) {int midIndex;if (startIndex < endIndex){midIndex = (startIndex + endIndex) / 2;MergeSort (sourceArr, startIndex, midIndex);MergeSort (sourceArr, midIndex+1, endIndex);Merge (sourceArr, startIndex, midIndex, endIndex);} }//調用 int main (void) {int a[SIZE] = {8, 4, 6, 3, 1, 7, 5, 2};MergeSort (a, 0, SIZE-1);int i = 0;for (i = 0; i < SIZE; i++)printf ("%d ", a[i]);printf ("\n");return 0; } 輸出結果： 1 2 3 4 5 6 7 8 （4）歸并排序說明

總結

以上是生活随笔為你收集整理的数据结构与算法 -- 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。