上篇文章介绍了大O表示方法和5种常见算法的大O表示时间，本篇文章主要对二分法查找、选择排序、快速排序算法进行了实现。
1 二分法查找
二分法查找是一种速度非常快的算法，但是它有固定的应用范围。仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按照顺序排列的，因此可以使用二分查找来找名字。二分法查找需要执行log n 次操作，大O表示法为 O(log n)。
算法问题描述：
函数binary_search接受一个有序数组和元素。如果指定的元素包含在数组中，如何编写函数binary_search返回元素的位置。
算法实现：
二分查找每次都检查中间元素，比较中间元素与查询元素的大小，不断缩小查询区域
#二分法查找（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 选择排序
有很多算法只有经过排序后的数据才能使用，例如上部分介绍的二分法查找。排序是最基础、最重要的算法之一，很多编程语言都内置了排序算法，基本上不需要你从头开始编写自己的版本。但是，对基础排序算法的学习是掌握其他重要算法的基础。本部分介绍的选择排序算法就是一种最简单的排序算法。选择性排序需要执行n+(n-1)+(n-2)+...+2+1次操作，大O表示法为O(n2).
算法问题描述：
如下图所示，假设计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。你需要写一个选择排序算法按照乐队播放的次数进行排序，从而选择出你最喜欢的乐队。
算法实现：
选择排序算法会重复的遍历列表，找出作品播放次数最终的乐队，将其加入到一个新列表中，并将其从原始的列表中删除。
#选择排序（python代码）
#选择列表中最小元素的函数
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倍。快速排序主要是应用了分而治之（divide and conquer, D&C）——一种著名的递归式的问题解决方法。
使用 D&C 解决问题主要包括两个步骤：
（1）找出基线条件，这种基线条件必须尽可能的简单。（注意：递归函数的基线条件通常是数组为空或者只包含一个元素）
（2）不断将问题分解（或者说缩小规模），直到符合基线条件。
算法问题描述：
函数 quicksort 接受一个无序列表。如何编写函数 quicksort 对列表中的元素进行快速排序。
算法实现：
快速排序 D&C 策略（如下图所示）：
1 、快速排序的基线——列表为空或者只有一个元素的列表是天然“有序”的列表
2、快速排序问题分解：（1）选择基准值（2）将数组分成两个子列表：小于基准值的列表和大于基准值的列表（3）对两个子列表再进行快速排序
快速排序的代码还是比较优雅的！
#快速排序（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、对每一对儿相邻的元素做同样的工作，执行完毕后，找到第一个最大值
3、重复以上的步骤，每次比较次数 - 1，直到不需要比较
//冒泡排序 C++代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
int arr[] = { 4,2,8,0,5,7,3,9 };
//总共排序的轮数为：元素个数 - 1
for (int i = 0; i < 9 - 1; i++) {
//内层循环次数：元素个数 - 当前轮数 -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、《算法图解》
