『壹』 蠻力法是什麼樣的演算法
《演算法設計與分析基礎》學習 --- 蠻力法 要重溫演算法思想，並以《演算法設計與分析基礎》這本書作為教材。該書每一章介紹一種演算法設計思想。今天從最簡單的開始寫起，打好基礎。以後再逐步深入，學習更深入的演算法。 蠻力法就是一種解決問題的最簡單最直觀的最容易理解方法，雖然它簡單，而且在實際應用中因為效率的原因可能不能派上用場，但是還是不能忽略它。正如書中作者所說，在解決小規模問題的時候也不失為一個方法，而且也是更復雜演算法的基礎。 一、選擇排序
以最簡單的思路解決排序問題，對於N個元素的數組，通過N次掃描數組，每次選擇出最小的元素放置到正確的位置，N趟掃描後即完成排序。 show sourceview source print? 01/* 02 蠻力法-選擇排序 03 將輸入數組排成非遞減數組 04 05 array:待排數組 06 n:數組大小，即[0,n-1] 07*/08void SelectionSort(int array[],unsigned int n) 09{ 10 int min; 11 for(int i=0;i<n-1;i++) 12 { 13 min=i; 14 for(int j=i+1;j<n;j++) 15 { 16 if(array[j]<array[min]) 17 min = j; 18 } 19 if(i!=min) 20 { 21 int temp = array[i]; 22 array[i] = array[min]; 23 array[min] = temp; 24 } 25 } 26}//SelectionSort
這是一個最差的排序方法，對於任何輸入都是 O(n*n)的時間復雜度。但是它的最大優點就是交換次數最少。 二、冒泡排序
又是一個經典的蠻力排序演算法。這里我僅僅對原始的冒泡做了點點改進，如果演算法已經排好序的話該演算法掃描一遍便完成排序。
show sourceview source print? 01/* 02 蠻力法-冒泡排序(稍微改進版) 03 將輸入數組排成非遞減數組 04 05 array:待排數組 06 n:數組大小，即[0,n-1] 07*/08void BubbleSort(int array[],unsigned int n) 09{ 10 int i=n-1; 11 int last; 12 while(i>0) 13 { 14 last = 0; 15 for(int j=0;j<i;j++) 16 { 17 if(array[j]>array[j+1]) 18 { 19 int temp = array[j]; 20 array[j] = array[j+1]; 21 array[j+1] = temp; 22 23 last = j; //記錄最近一次交換值的位置 24 } 25 } 26 i = last; 27 } 28}//BubbleSort
但是在最差的情況下，它還是O(n*n)的時間復雜度。 三、順序查找和字元串的蠻力匹配
順序查找，再簡單不過的查找演算法了，算是對蠻力思想的一種應用。以及字元串的蠻力匹配也是這樣的。