上篇文章介紹了大O表示方法和5種常見算法的大O表示時間睡扬，本篇文章主要對二分法查找、選擇排序黍析、快速排序算法進行了實現(xiàn)卖怜。
1 二分法查找
二分法查找是一種速度非常快的算法阐枣，但是它有固定的應(yīng)用范圍马靠。僅當(dāng)列表是有序的時候，二分查找才管用蔼两。例如甩鳄，電話簿中的名字是按照順序排列的，因此可以使用二分查找來找名字额划。二分法查找需要執(zhí)行l(wèi)og n 次操作妙啃，大O表示法為 O(log n)。
算法問題描述：
函數(shù)binary_search接受一個有序數(shù)組和元素俊戳。如果指定的元素包含在數(shù)組中揖赴，如何編寫函數(shù)binary_search返回元素的位置。
算法實現(xiàn)：
二分查找每次都檢查中間元素抑胎，比較中間元素與查詢元素的大小燥滑，不斷縮小查詢區(qū)域
#二分法查找（python代碼）
def binary_search(list,item):
low = 0
high = len(list) -1
while low <= high:
mid = (low + high)/2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1,3,5,7,9]
print binary_search(my_list,3)
1 #返回值
print binary_search(my_list,-1)
None #返回值
2 選擇排序
有很多算法只有經(jīng)過排序后的數(shù)據(jù)才能使用，例如上部分介紹的二分法查找阿逃。排序是最基礎(chǔ)铭拧、最重要的算法之一，很多編程語言都內(nèi)置了排序算法恃锉，基本上不需要你從頭開始編寫自己的版本搀菩。但是，對基礎(chǔ)排序算法的學(xué)習(xí)是掌握其他重要算法的基礎(chǔ)破托。本部分介紹的選擇排序算法就是一種最簡單的排序算法秕磷。選擇性排序需要執(zhí)行n+(n-1)+(n-2)+...+2+1次操作，大O表示法為O(n2).
算法問題描述：
如下圖所示炼团，假設(shè)計算機存儲了很多樂曲。對于每個樂隊疏尿，你都記錄了其作品被播放的次數(shù)瘟芝。你需要寫一個選擇排序算法按照樂隊播放的次數(shù)進行排序，從而選擇出你最喜歡的樂隊褥琐。
算法實現(xiàn)：
選擇排序算法會重復(fù)的遍歷列表锌俱，找出作品播放次數(shù)最終的樂隊，將其加入到一個新列表中敌呈，并將其從原始的列表中刪除贸宏。
#選擇排序（python代碼）
#選擇列表中最小元素的函數(shù)
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
#對輸入列表進行排序
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5,3,6,3,6,2,1])
[1, 2, 3, 3, 5, 6, 6] #返回值
3 快速排序
選擇排序的大O表示法為O(n2)造寝，快速排序排序的大O表示法為O(n log n)】粤罚快速排序的速度是選擇排序的n/logn倍诫龙。快速排序主要是應(yīng)用了分而治之（divide and conquer, D&C）——一種著名的遞歸式的問題解決方法鲫咽。
使用 D&C 解決問題主要包括兩個步驟：
（1）找出基線條件签赃，這種基線條件必須盡可能的簡單。（注意：遞歸函數(shù)的基線條件通常是數(shù)組為空或者只包含一個元素）
（2）不斷將問題分解（或者說縮小規(guī)模）分尸，直到符合基線條件锦聊。
算法問題描述：
函數(shù) quicksort 接受一個無序列表。如何編寫函數(shù) quicksort 對列表中的元素進行快速排序箩绍。
算法實現(xiàn)：
快速排序 D&C 策略（如下圖所示）：
1 孔庭、快速排序的基線——列表為空或者只有一個元素的列表是天然“有序”的列表
2、快速排序問題分解：（1）選擇基準值（2）將數(shù)組分成兩個子列表：小于基準值的列表和大于基準值的列表（3）對兩個子列表再進行快速排序
快速排序的代碼還是比較優(yōu)雅的材蛛！
#快速排序（python代碼）
def quicksort(array):
if len(array) < 2:
return array #基線條件
else:
#遞歸條件
pivot = array[0] #選取基準值
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([2,3,6,8,1,2])
[1, 2, 2, 3, 6, 8] #返回值
4 冒泡排序
冒泡排序和選擇排序的思路比較類似圆到，大O表示法為O(n2)。它的思路為：
1仰税、比較相鄰的元素构资，如果第一個比第二個大，就交換他們兩個
2陨簇、對每一對兒相鄰的元素做同樣的工作吐绵，執(zhí)行完畢后，找到第一個最大值
3河绽、重復(fù)以上的步驟己单，每次比較次數(shù) - 1，直到不需要比較
//冒泡排序 C++代碼
#include <iostream>
#include <string>
using namespace std;
int main()
{
int arr[] = { 4,2,8,0,5,7,3,9 };
//總共排序的輪數(shù)為：元素個數(shù) - 1
for (int i = 0; i < 9 - 1; i++) {
//內(nèi)層循環(huán)次數(shù)：元素個數(shù) - 當(dāng)前輪數(shù) -1
for (int j = 0; j < 9 - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 0; i < 9; i++) {
cout << arr[i] << endl;
}
}
參考資料
1耙饰、《算法圖解》
