排序算法的实现:冒泡排序、选择排序、快速排序、二分查找、快速排序

冒泡排序：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(bubbers):
    """
    冒泡排序，将numbers按从小到大排序
    :param numbers: list类型
    :return: list类型
    """
    for i in range(len(bubbers)-1,0,-1):
        for j in range(0,i):
            if bubbers[j] > bubbers[j+1]:
                bubbers[j],bubbers[j+1] = bubbers[j+1],bubbers[j]
 
    return bubbers

选择排序：

def select_sort(a):
    """
    选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，
    存放在序列的起始位置，直到全部待排序的数据元素排完。
    :param selects:list类型
    :return:
    """
    for i in range(0,len(a)-1,1):
        k = i
        for j in range(i+1,len(a)):
            if a[k] > a[j]:
                k = j
        if k != i:
            a[i], a[k] = a[k], a[i]
 
    return a

快速排序：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

def insert_sort(b):
    for i in range(1,len(b)-1,1):
        for j in range(i,0,-1):
            if b[j-1]> b[j]:
                b[j-1],b[j] = b[j],b[j-1]
    return b

二分查找：

def binary_search(c,key):
    """
    从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
    如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找。
    如果在某一步骤数组为空，则代表找不到。
    :param c:
    :param key:
    :return:
    """
    left = 0
    right = len(c)-1
    while left <= right:
        mid = (left + right) / 2
        if c[mid] < key:
            left = mid +1
        elif c[mid] > key:
            right = mid -1
        else:
            return mid

快速排序：（分治法）

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

def qiuckly_sort(array):
    assert isinstance(array, list)
    if len(array) == 0:
        return array
 
    quick_sort(array, 0, len(array)-1)
    return array
 
def quick_sort(array, left, right):
 
    if left < right:
        pivot = array[left]
        i, j = left, right
        while i < j:
            while i < j and array[j] >= pivot:
                    j -= 1
            if i < j:
                    array[i] = array[j]
                    i += 1
            while i < j and array[i] < pivot:
                    i += 1
            if i < j:
                    array[j] = array[i]
                    j -= 1
            array[i] = pivot
            quick_sort(array, left, i)
            quick_sort(array, i + 1, right)
 
if __name__ == '__main__':
    a = [5, 3, 7, 2, 8, 4]
    qiuckly_sort(a)
    quick_sort(a,0,len(a)-1)
    print a

方法二：

1.取第一个数为基准数

2.遍历list，小于基准数+基准数+大于基准数

def qsort(arr):
 
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + 
               [pivot] + 
               qsort([x for x in arr[1:] if x >= pivot])

=======快排原理（leo）======

！！！原理原理原理！！！

中位数查找 + 分治理

第一次遍历的

首先设置两个变量i，j。

分别指向序列的首尾元素。
该例子是以第一个元素为基准，从小到大进行排列。

让j从后向前进行查询，直到找到第一个小于66的元素。

则将最后一个j指向的数23，和i指向的66交换位置。

然后将i从前向后查询，直到找到第一个大于66的元素76.
将76和66位置互换。

让j从后向前进行查询，直到找到第一个小于66的元素57
将57和66交换位置。
然后将i从前向后查询，直到找到第一个大于66的元素81.
将81和66交换位置。

让j从后向前进行查询，直到找到第一个小于66的元素26
将26和66交换位置。

此时i，j都同时指向了目标元素66.

查找停止。

所得到的序列就是第一趟排序的序列

查找中位数是面试中经常出现的一类题。用快速排序的思想可以解决这种问题，算法如下：

1.抽取数组的第一个元素作为中间值，用快速排序的思想进行一次调整，将比中间值小的放在中间值的左边，比中间值大的放在中间值的右边。

2.如果中间值的索引等于数组长度的一半，那么就找到了。

3.如果中位数的索引比数组长度的一半大的话，那么在中间值的索引到数组的结尾这个期间内找第（数组长度的一半-中位数）大的数。

4.否则在数组的开始到中间值的索引这段期间内找第（数组长度的一半大）大的数。递归的调用上面的几步，就可以解决问题了！