[数据结构算法](一): 经典排序算法Python实现

作者: ItchyHiker | 来源:发表于2019-02-16 19:58 被阅读0次

一、冒泡排序 Bubble Sort

思想: 持续比较相邻元素，大的挪到后面，一次比较之后最后一个元素便是所有元素中最大的
步骤:

比较相邻的元素，如果第一个比第二个大，交换二者的位置，
对第0到第n-1个数据重复上述步骤，此时最大元素位于n-1处
每次对所有非排序元素(位于后面的元素)重复上述步骤，直到没有数字可以用来比较

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(1, n-i):
            if array[j-1] > array[j]: # if former larger than the latter, swap two elements
                array[j-1], array[j] = array[j], array[j-1] 
    return array

if __name__ == "__main__":
    array = [1,4,5,2,11,2,20,9]
    sorted_array = bubble_sort(array)
    print("after sort:\n", sorted_array)
    print("after sort:\n", array)

二、选择排序 Selection Sort
步骤:

遍历数组选择其中最小的元素放大数组第一个位置
在剩下了的元素中选择最小的元素放在第二个位置，直到没有剩下的元素

import time
import random

def selection_sort(array):

    n = len(array)
    for i in range(n):
        min_index = i # index for min element
        for j in range(i+1, n):
            if array[j] < array[min_index]:
                min_index = j
        array[min_index], array[i] = array[i], array[min_index] # swap the current element with the minium element
    return array

if __name__ == "__main__":

    n = 1000
    array = []
    for i in range(n):
        array.append(random.randint(0, n))
    sorted_array = selection_sort(array)

三、插入排序 Insertion Sort
原理: 对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
步骤:

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

import random
import time

def insertion_sort1(array):
    n = len(array)
    for i in range(n-1):
        temp = array[i+1]
        index = i
        for j in range(i, -1, -1):
            if array[j] > temp:
                array[j+1] = array[j]
                index = j
            else:
                break
            array[index] = temp
    return array

def insertion_sort2(array):
    n = len(array)
    for i in range(n-1):
        if array[i] > array[i+1]:
            temp = array[i+1]
            index = i
            for j in range(i, -1, -1):
                if array[j] > temp:
                    array[j+1] = array[j]
                    index = j
                else:
                    break
                array[index] = temp
    return array

if __name__ == "__main__":
    n = 1000
    array = []
    for i in range(n):
        array.append(random.randint(0, n))
    t0 = time.time()
    sorted_array1 = insertion_sort1(array)
    t1 = time.time()
    print("insertion_sort1 time:", t1 - t0)
    
    t0 = time.time()
    sorted_array2 = insertion_sort2(array)
    t1 = time.time()
    print("insertion_sort2 time:", t1 - t0)
    sorted_array = sorted(array, reverse=False) # ascending sorting
    assert(sorted_array2 == sorted_array1 == sorted_array)

四、归并排序 Merge Sort

思想: 归并排序是采用分治法的典型算法。先递归分解数组，再合并数组。

先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

import time
import random


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    return merge(left, right)

def merge(left, right):
    l = 0
    r = 0
    array = []
    while(l < len(left) and r < len(right)):
        if left[l] < right[r]:
            array.append(left[l])
            l += 1
        else:
            array.append(right[r])
            r += 1
    array += left[l:]
    array += right[r:]
    return array

if __name__ == "__main__":
    n = 10
    array = []
    for i in range(n):
        array.append(random.randint(0, n))
    print("Array to sorted:", array)
    merge_sorted_array = merge_sort(array)
    print("Merge Sorted array:", merge_sorted_array)
    sorted_array = sorted(array, reverse=False) # ascending sorting
    assert(merge_sorted_array == sorted_array)

五、快速排序 Quick Sort
思想:分而治之
步骤:

随机选取一个元素为基准元素
所有比基准元素小的置于基准元素左侧，所有比基准元素大的置于基准元素右侧
对基准元素左右区间递归调用此过程

import time
import random
def quick_sort(array):
    return qsort(array,0,len(array)-1)

def qsort(array,left,right):
    
    if left >= right : return array
    key = array[left]   # left as key for comparaing
    lp = left           # left index
    rp = right          # right index
    while lp < rp :
        while array[rp] >= key and lp < rp :
            rp -= 1
        while array[lp] <= key and lp < rp :
            lp += 1
        print(array[lp])
        array[lp],array[rp] = array[rp],array[lp]
        print("lp:{0}, rp:{1}".format(lp, rp))
        print(array)
    array[left],array[lp] = array[lp],array[left]
    qsort(array,left,lp-1)
    qsort(array,rp+1,right)
    return array


def quick_sort2(array):
    if len(array) <= 1:
        return array
    key = array[0]
    return quick_sort2([x for x in array[1:] if x < key]) + [key] + quick_sort2([x for x in array[1:] if x >= key])


if __name__ == "__main__":
    # n = 10
    # array = []
    # for i in range(n):
    #     array.append(random.randint(0, n))
    array = [6,5,3,1,8,7,2,4]
    print("Array to sorted:", array)
    quick_sorted_array = quick_sort(array)
    quick_sorted_array2 = quick_sort2(array)
    print("Quick Sorted array:", quick_sorted_array)
    sorted_array = sorted(array, reverse=False) # ascending sorting
    assert(quick_sorted_array == sorted_array == quick_sorted_array2)

六、堆排序
思想: 构建最大二叉堆，然后每次去除最大堆的根节点
步骤:

创建最大堆
移除位于根节点，做最大堆调整的运算

最主要在如何实现max_heapify()函数来调整最大堆上。
采取自底向上的方式构建最大堆，数组后半部分想象为堆最下面的节点，由于是单个节点故满足二叉堆定义。因此可以从中间节点向前逐步构建二叉堆。

下面这个图说明的很清楚了:

Screen Shot 2019-02-16 at 7.46.38 PM.png

# -*- coding: utf-8 -*-
import time
import heapq
import random

def heap_sort(array):
    n = len(array)
    first = n // 2 - 1  # the last non leaf node
    for start in range(first, -1, -1):
        print("enter")
        max_heapify(array, start, n-1)
    for end in range(n-1,0,-1):  # 堆排序，将大根堆转换成有序数组
        array[end],array[0] = array[0],array[end]
        max_heapify(array, 0, end-1)
    return array

def max_heapify(ary, start, end):
    """
    最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
    start为当前需要调整最大堆的位置，end为调整边界
    """
    root = start
    while True:
        print(root)
        child = root*2 + 1  # 调整节点的子节点 对于完全二叉树 左子节点为父节点的2*index + 1
        if child > end: break
        if child+1 <= end and ary[child] < ary[child+1] : # 如果右子节点大于左子节点
            child = child+1  # 取较大的子节点
        if ary[root] < ary[child]:  # 较大的子节点成为父节点
            ary[root], ary[child] = ary[child], ary[root]  # 交换
            root = child # 交换之后可能会破坏child子树的结构，child子树需要重新遍历
        else:
            break

def heap_sort2(array):
    h = []
    for i in array:
        heapq.heappush(h, i)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":
    n = 10
    array = []
    for i in range(n):
        array.append(random.randint(0, n))
    # array = [6,5,3,1,8,7,2,4]
    print("Array to sorted:", array)
    start = time.time()
    heap_sorted_array = heap_sort(array)
    end = time.time()
    print("Time for heap_sort:", end - start)
    start = time.time()
    heap_sorted_array2 = heap_sort2(array)
    end = time.time()
    print("Time for heap_sort using heapq:", end - start)
    # print("Heap Sorted array:", heap_sorted_array)
    # print("Heap Sorted array2:", heap_sorted_array2)
    sorted_array = sorted(array, reverse=False) # ascending sorting
    assert(heap_sorted_array == sorted_array)

七、计数排序
思想: 通过对元素进行计数，从而知道元素在已排序元素中应该处于什么位置
步骤:

定义计数数组，数组大小为代排序元素中最大元素
统计待排序数组中值为i元素的次数，每出现一次在计数数组的i处加一
对计数数组进行逐项求和，依次每一项的新值为原始值和它前一项的值之和，这一步是为了确定待排序数组的元素在新数组中的位置
将每个元素i放在新数组的C(i)处，每放一个元素C(i)减去1

如输入是:1, 4, 1, 2, 7, 5, 2
计数数组:

  index: 0, 1, 2, 3, 4, 5, 6, 7
  value: 0, 2, 2, 0, 1, 1, 0, 1

计数数组求和:

  index: 0, 1, 2, 3, 4, 5, 6, 7
  value: 0, 2, 4, 4, 5, 6, 6, 7

对于输入数组:1, 4, 1, 2, 7, 5, 2
1, 的index为1, 在新数组1处存1, 计数数组在1处减1:[0, 1, 4, 4, 5, 6, 6, 7]

[0, 1, 0, 0, 0, 0, 0, 0]

4, 的index为4, 在新数组5处存4, 计数数组在4处减1:[0, 1, 4, 4, 4, 6, 6, 7]

[0, 1, 0, 0, 0, 4, 0, 0]

...
最后得到:
1, 1, 2, 2, 4, 5, 7

def counting_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    output = [0 for _ in range(max_num+1)]
    count = [0 for _ in range(max_num+1)]
    for i in arr:
        count[i] += 1
    for i in range(1, max_num+1):
        count[i] += count[i-1]
    for i in arr:
        output[count[i]] = i
        count[i] -= 1
    return output[min_num:]
if __name__ == "__main__":
    arr = [1, 4, 1, 2, 7, 5, 2]
    print(counting_sort(arr))

八、基数排序
思想: 使用一定的基数把元素的位数按照重要性从小到大排序
步骤:
以常见的10为基数为列:
个位，十位，百位排序...
如:
170, 45, 75, 90, 802, 24, 2, 66
个位排序:
170, 90, 802, 2, 24, 45, 75, 66
十位:
802, 2, 24, 45, 66, 170, 75, 90
百位:
2, 24, 45, 66, 75, 90, 170, 802

"""
implementing counting sort algorithm
@author vincent
2019.2.16
"""

def counting_sort(arr, exp):
    n = len(arr)
    output = [0]*(n)
    count = [0]*(10)
    for i in range(0, n):
        index = arr[i] // exp
        count[index%10] += 1

    for i in range(1, 10):
        count[i] += count[i-1]

    i = n-1
    while i > 0:
        index = arr[i] / exp
        output[ count[ (index)%10 ] - 1] = arr[i]
        count[index%10] -= 1
        i -= 1
    for i in range(0, len(arr)):
        arr[i] = output[i]


def radix_sort(arr):
    max_num = max(arr)

    exp = 1
    while max_num/exp > 0:
        counting_sort(arr, exp)
        exp *= 10

if __name__ == "__main__":
    arr = [ 170, 45, 75, 90, 802, 24, 2, 66] 
    radix_sort(arr) 
    print(arr)

Todo:
九、桶排序

Reference

http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/
常见算法可视化网站，有助于辅助理解: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Data Structures and Algorithms in Python GoodRich

[数据结构算法](一): 经典排序算法Python实现

一、冒泡排序 Bubble Sort

Reference

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读