基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
下面这个图可以描述算法的实现过程：

时间复杂度

快速排序是一种不稳定的排序方法，平均时间复杂度为O (nlogn)，最坏情况和冒泡排序差不多，为O（n²）。

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([10, 5, 2, 3]) # 结果：[2, 3, 5, 10]

# 比较容易理解的实现方法
def quick(list):
    if len(list) < 2:
        return list
    else:
        left = i = 0
        j = len(list) - 1
        
        while i != j:
            while list[j] >= list[left] and i < j:
                j -= 1

            while list[i] <= list[left] and i < j:
                i += 1
            
            if i < j:
                list[i], list[j] = list[j], list[i]
        list[i], list[left] = list[left],  list[i]
        return quick(list[left:i]) + [list[i]] + quick(list[i+1:])

注意理解：上面的第二种方法，挑选了左侧第一个数作为参考，内部循环则从对面，即列表末尾开始查找，因为如果从左侧开始查找，当满足条件i=j退出循环时，list[i]会比list[left]大，交换之后违反了左边小右边大的原则。

该实例中涉及Python的一个称作列表推导表达式的语法糖用法，即在for循环中嵌套使用if和else语句。例如：

oldList = [12, 3, 4, 6, 7, 13, 21]
newList = [x for x in oldList if x%2 == 0]
print newList # 结果：[12, 4, 6]

想了解更多Python语法糖知识，请参考：Python语法糖系列

循环实现：

def sum(arr):
  total = 0
  for x in arr:
    total += x
  return total

print sum([1, 2, 3, 4]) # 结果：10

递归实现：

def sum(arr):
  total = 0
  length = len(arr)
  if length == 0:
    return total
  else:
    return arr.pop(0) + sum(arr)
    
print sum([1,2]) # 结果：3

简单来说，递归就是程序（函数）调用自身（recursion）的编程技巧。下面的例子是经典的递归实现阶乘（factorial）案例：

def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

fact(3)

#输出结果：6

使用递归需要注意：

• 递归指的是调用自己的函数。
• 每个递归函数都有两个条件：基线条件和递归条件。

选择排序（Selection sort）是一种简单直观的排序算法。

原理

是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序的交换操作介于 0 和 (n - 1） 次之间，所以选择排序是不稳定的排序方法。

算法描述

1. 在一个长度为 n 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
2. 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。

3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

   时间复杂度

   需要的总时间为O(n×n)，即O(n²)。

python语言实现

# -*- coding: UTF-8 -*-
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, 2, 10])

# 输出结果 [2, 3, 5, 6, 10]

当然，还有更简洁的实现方法：

# -*- coding:utf-8 -*-
# 选择排序

# 方法一
def select_sort(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        min = list[i]
        for j in range(i + 1, l):
            if list[j] < min:
                min, list[j] = list[j], min
        list[i] = min

    return list


# 方法二，交换次数少，效率更高
def select(list):
    l = len(list)
    if l < 2:
        return list
    
    for i in range(l):
        for j in range(i + 1, l):
            if list[j] < list[i]:
                list[i], list[j] = list[j], list[i]

    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(select(list))
print(select_sort(list))

前提：一个有序的列表
原理：假如我们心里默念一个1-100的数字，让别人猜，那么怎么猜会比较快呢？（1）从1开始往后猜，那么最坏的情况可能要猜100次；（2）每次都猜剩下数字列表的中间那个数，这样每次都可以排除一半，平均情况下，这种方法比第一种要快。
第二种方法也就是下面的二分查找算法（Python实现）。
时间复杂度：O(log2n)。

# -*- coding: UTF-8 -*-
# 二分查找 binary_search.py

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, 9) #结果：4
print binary_search(my_list, -1) #结果：None

以上代码只适用于没有重复数据的列表，如果列表中有重复的数据，我们要查找左边界或右边界，又该如何呢？在参考了 详解二分查找算法 之后，得出了一下代码供大家参考：

#  寻找左侧边界
def left_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            right = mid
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == len(list):
        return -1

    if list[left] == item:
        return left
    else:
        return -1


#  寻找右侧边界
def right_bound(list, item):
    left = 0
    right = len(list)

    while (left < right):
        mid = (left + right) // 2
        if item == list[mid]:
            left = mid + 1
        elif item > list[mid]:
            left = mid + 1
        elif item < list[mid]:
            right = mid
    
    # 考虑越界问题
    if left == 0:
        return -1
    if list[left - 1] == item:
        return left - 1
    else:
        return -1