ios開發中涉及到算法的地方還真不多，除非你的應用程序真的非常大，或者你想你的應用程序性能非常好才會去想到關於算法方面的性能優化，而在ios開發中真的能用得到的也就是關於排序的，當然如果你是做游戲的話那麼你可能會涉及到不少的算法或者優化問題，但是這不是本篇文章討論的范圍。
後面的文章中，我將會給大家詳細介紹八大算法。
2、冒泡排序
2.1 引出
前面的兩篇博客裡講的插入排序是基於“逐個記錄插入”，選擇排序是基於“選擇”，那麼冒泡排序其實是基於“交換”。每次從第一個記錄開始，一、二兩個記錄比較，大的往後放，二三兩個記錄比較...依次類推，這就是一趟冒泡排序。每一趟冒泡排序後，無序序列中值最大的記錄冒到序列末尾，所以稱之為冒泡排序。
2.2 代碼
1 //冒泡排序 2 void bubbleSort(int *a,int n) 3 { 4 int i,j; 5 for(i=1;i<n;i++) 6 for(j=1;j<n-i+1;j++){ 7 if(a[j+1]<a[j]){ 8 a[j]=a[j]+a[j+1]; 9 a[j+1]=a[j]-a[j+1]; 10 a[j]=a[j]-a[j+1]; 11 } 12 } 13 }
冒泡排序算法：
1 冒泡排序代碼 2 3 static void Main(string[] args) 4 { 5 ////五次比較 6 for (int i = 1; i <= 5; i++) 7 { 8 List<int> list = new List<int>(); 9 //插入2k個隨機數到數組中 10 for (int j = 0; j < 2000; j++) 11 { 12 Thread.Sleep(1); 13 list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000)); 14 } 15 Console.WriteLine("\n第" + i + "次比較："); 16 Stopwatch watch = new Stopwatch(); 17 watch.Start(); 18 var result = list.OrderBy(single => single).ToList(); 19 watch.Stop(); 20 Console.WriteLine("\n快速排序耗費時間：" + watch.ElapsedMilliseconds); 21 Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); 22 watch.Start(); 23 result = BubbleSort(list); 24 watch.Stop(); 25 Console.WriteLine("\n冒泡排序耗費時間：" + watch.ElapsedMilliseconds); 26 Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); 27 Console.ReadKey(); 28 } 29 30 } 31 32 //冒泡排序算法 33 private static List<int> BubbleSort(List<int> list) 34 { 35 int temp; 36 //第一層循環： 表明要比較的次數，比如list.count個數，肯定要比較count-1次 37 for (int i = 0; i < list.Count - 1;i++ ) 38 { 39 //list.count-1：取數據最後一個數下標，47 40 //j>i: 從後往前的的下標一定大於從前往後的下標，否則就超越了。 41 for (var j = list.Count-1; j > i;j-- ) 42 { 43 //如果前面一個數大於後面一個數則交換 44 if (list[j - 1] > list[j]) 45 { 46 temp = list[j - 1]; 47 list[j - 1] = list[j]; 48 list[j] = temp; 49 } 50 } 51 52 } 53 return list; 54 }
2.3 效率分析
相對於簡單選擇排序，冒泡排序交換次數明顯更多。它是通過不斷地交換把最大的數冒出來。冒泡排序平均時間和最壞情況下（逆序）時間為o（n^2）。最佳情況下雖然不用交換，但比較的次數沒有減少，時間復雜度仍為o（n^2）。此外冒泡排序是穩定的。
3、快速排序
3.1 引出
快速排序是冒泡排序的一種改進，冒泡排序排完一趟是最大值冒出來了，那麼可不可以先選定一個值，然後掃描待排序序列，把小於該值的記錄和大於該值的記錄分成兩個單獨的序列，然後分別對這兩個序列進行上述操作。這就是快速排序，我們把選定的那個值稱為樞紐值，如果樞紐值為序列中的最大值，那麼一趟快速排序就變成了一趟冒泡排序。
3.2 代碼
兩種版本，第一種是參考《數據結構》，在網上這種寫法很流行。第二種是參考《算法導論》，實現起來較復雜。
1 //快速排序（兩端交替著向中間掃描） 2 void quickSort1(int *a,int low,int high) 3 { 4 int pivotkey=a[low];//以a[low]為樞紐值 5 int i=low,j=high; 6 if(low>=high) 7 return; 8 //一趟快速排序 9 while(i<j){//雙向掃描 10 while(i < j && a[j] >= pivotkey) 11 j--; 12 a[i]=a[j]; 13 while(i < j && a[i] <= pivotkey) 14 i++; 15 a[j]=a[i]; 16 } 17 a[i]=pivotkey;//放置樞紐值 18 //分別對左邊、右邊排序 19 quickSort1(a,low,i-1); 20 quickSort1(a,i+1,high); 21 } 22 23 //快速排序（以最後一個記錄的值為樞紐值，單向掃描數組） 24 void quickSort2(int *a,int low,int high) 25 { 26 int pivotkey=a[high];//以a[high]為樞紐值 27 int i=low-1,temp,j; 28 if(low>=high) 29 return; 30 //一趟快速排序 31 for(j=low;j<high;j++){ 32 if(a[j]<=pivotkey){ 33 i++; 34 temp=a[i]; 35 a[i]=a[j]; 36 a[j]=temp; 37 } 38 } 39 i++; 40 //放置樞紐值 41 temp=a[i]; 42 a[i]=pivotkey; 43 a[high]=temp; 44 //分別對左邊、右邊排序 45 quickSort2(a,low,i-1); 46 quickSort2(a,i+1,high); 47 }快速排序算法：
1 快速排序法 2 3 static void Main(string[] args) 4 { 5 6 //5次比較 7 for (int i = 1; i <= 5; i++) 8 { 9 List<int> list = new List<int>(); 10 //插入200個隨機數到數組中 11 for (int j = 0; j < 200; j++) 12 { 13 Thread.Sleep(1); 14 list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000)); 15 } 16 Console.WriteLine("\n第" + i + "次比較："); 17 Stopwatch watch = new Stopwatch(); 18 watch.Start(); 19 var result = list.OrderBy(single => single).ToList(); 20 watch.Stop(); 21 Console.WriteLine("\n系統定義的快速排序耗費時間：" + watch.ElapsedMilliseconds); 22 Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); 23 watch.Start(); 24 new QuickSortClass().QuickSort(list, 0, list.Count - 1); 25 watch.Stop(); 26 Console.WriteLine("\n俺自己寫的快速排序耗費時間：" + watch.ElapsedMilliseconds); 27 Console.WriteLine("輸出前是十個數:" + string.Join(",", list.Take(10).ToList())); 28 Console.ReadKey(); 29 } 30 } 31 32 public class QuickSortClass 33 { 34 35 ///<summary> 36 ////// 分割函數 37 ///</summary> 38 //////<param name="list">待排序的數組</param> 39 ///<param name="left">數組的左下標</param> 40 //////<param name="right"></param> 41 ///<returns></returns> 42 public int Division(List<int> list, int left, int right) 43 { 44 //首先挑選一個基准元素 45 int baseNum = list[left]; 46 while (left < right) 47 { 48 //從數組的右端開始向前找，一直找到比base小的數字為止(包括base同等數) 49 while (left < right && list[right] >= baseNum) 50 right = right - 1; 51 //最終找到了比baseNum小的元素，要做的事情就是此元素放到base的位置 52 list[left] = list[right]; 53 //從數組的左端開始向後找，一直找到比base大的數字為止（包括base同等數） 54 while (left < right && list[left] <= baseNum) 55 left = left + 1; 56 //最終找到了比baseNum大的元素，要做的事情就是將此元素放到最後的位置 57 list[right] = list[left]; 58 } 59 //最後就是把baseNum放到該left的位置 60 list[left] = baseNum; 61 //最終，我們發現left位置的左側數值部分比left小，left位置右側數值比left大 62 //至此，我們完成了第一篇排序 63 return left; 64 } 65 public void QuickSort(List<int> list, int left, int right) 66 { 67 //左下標一定小於右下標，否則就超越了 68 if (left < right) 69 { 70 //對數組進行分割，取出下次分割的基准標號 71 int i = Division(list, left, right); 72 //對“基准標號“左側的一組數值進行遞歸的切割，以至於將這些數值完整的排序 73 QuickSort(list, left, i - 1); 74 //對“基准標號“右側的一組數值進行遞歸的切割，以至於將這些數值完整的排序 75 QuickSort(list, i + 1, right); 76 } 77 } 78 }
3.3 效率分析
快速排序時間與劃分是否對稱有關。快速排序的平均時間復雜度為o（n*logn），至於為什麼是o（n*logn），請參考《算法導論》第7章，書中用遞歸樹的方法闡述了快速排序平均時間。且常數因子很小，所以就平均時間而言，快速排序是很好的內部排序方法。最佳情況下（每次劃分都對稱）時間復雜度o（n*logn）。最壞情況下（每次劃分都不對稱，如輸入的序列有序或者逆序時）時間復雜度為o(n^2)，所以在待排序序列有序或逆序時不宜選用快速排序。此外，快速排序是不穩定的。
最佳情況下，每次劃分都是對稱的，由於樞紐值不再考慮，所以得到的兩個子問題的大小不可能大於n/2，同時一趟快速排序時間為o（n），所以運行時間遞歸表達式：
T（n）<=2T(n/2)+o(n)。這個遞歸式的解法請參考下一篇博客中歸並排序效率分析。其解為T（n）=o（n*logn）。
最壞情況下，每次劃分都很不對稱，T(n)=T(n-1)+o(n),可以用遞歸樹來解，第i層的代價為n-i+1.總共有n層。把每一層代價加起來有n-1個n相加。所以這個遞歸式的解為T（n）=o（n^2）,此時就是冒泡排序。
