Python实现简单的算法

四个简单排序 + 图解(冒泡、选择、插入、快速)

1. 冒泡排序

每次循环都将最大的数字放到列表最后

def bubble_sort(arr):
        length = len(arr)
        for i in range(length - 1):
            for j in range(length - i - 1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
        return arr

2. 选择排序

选择最小的那个数字，更换位置

def choice_sort(arr):
        length = len(arr)
        for i in range(length - 1):
            least = i
            for j in range(i + 1, length):
                if arr[j] < arr[least]:
                    least = j
            arr[i], arr[least] = arr[least], arr[i]
        return arr

3. 插入排序

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

def insert_sort(arr):
        length = len(arr)
        for i in range(length):
            index = i
            while index:
                if index and arr[index-1] > arr[index]:
                    arr[index - 1], arr[index] = arr[index], arr[index - 1]
                index -= 1
        return arr

4. 快速排序

个人觉得快排是最好理解的，就是利用递归原理，每次分成两个列表，依次向下排序，看代码就应该可以理解了。

def fast_sort(arr):
        if len(arr) <= 1:
            return arr
        else:
            left, right = [], []
            pivot = arr.pop()
            for i in arr:
                if i > pivot:
                    right.append(i)
                else:
                    left.append(i)
            return fast_sort(left) + [pivot] + fast_sort(right)

查找(二分)

二分查找

def binary_search(arr, target):
        length = len(arr)
        # start， end是索引(index)
        start = 0
        end = length - 1
        while start <= end:
            mid = (start + end) // 2  # 找到中间数的索引(index)
            if arr[mid] > target:      # 如果中间这个数大于目标值，则缩短end的索引
                end = mid - 1
            elif arr[mid] < target:   # 反之，则增加start的索引
                start = mid + 1
            else:                      # 如果相等，则输出
                return mid