各种排序的python实现

python基础

浏览数:876

2018-2-3

最近师兄师姐都在找工作,看到他们的笔试题中很多都是算法题。突然一个算法题摆在面前也是让人够懵逼的,于是我也复习一下各种排序算法吧,还是用python实现。

O(n^2)

平均时间复杂度均为O(n^2)的排序有三种:插入排序,选择排序和冒泡排序。这是三种比较简单的排序。

冒泡排序

算法思路:每轮将最小(最大)的一个数交换到数组尾部(顶部)。
代码实现:

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

插入排序

算法思路:每次提取一个数出来有序插入到它前面的数组。
将第i个元素提取出来与它前面部分的数组的元素一一比较,如果前面的数更大(更小),那么前面的数的序号+1.
当第i格元素不比它比较的数更大(更小)时,就把i元素放到它比较的元素后面。
当提取第i个数时,前面部分数组是有序的。
代码实现:

def insert_sort(L):
    length = len(L)
    if length < 2:
        return L
    for i in range(1,length):
        key = L[i]
        j = i-1
        while j >= 0 and L[j] < key:
            L[j+1] = L[j]
            j -= 1
        L[j+1] = key
    return L

选择排序

算法思路:每一轮标记出最小(最大)的数,然后把它放在有序位置上。
代码实现:

def select_sort(L):
    length = len(L)
    if length < 2:
        return L
    for i in range(length-1):
        maxindex = i
        for j in range(i,length):
            if L[j] > L[maxindex]:  # 找出最大数的索引
                maxindex = j
        if i != maxindex:   # 把当前最大数放到当前循环队列首位
            L[i], L[maxindex] = L[maxindex], L[i]
    return L

O(nlogn)

平均时间复杂度为O(nlogn)的算法有:归并排序,堆排序和快速排序; 这些排序算法一般都需要进行迭代,可能需要多个函数,所以都写成可调用类的形式。
归并排序:

算法思路:
以单个元素为单位分组,然后两两排序,再将排好的序列递归地进行两两排序。
代码编写分为两个主要部分:先拆,后并。
对于一个子序列,分成两份,比较两份的第一个元素,小者弹出,然后重复这个过程。对于待排序列,以中间值分成左右两个序列,然后对于各子序列再递归调用。
排序效果如图:

代码实现:

class merge_sort(object):
    def _merge(self, alist, p, q, r):
        left = alist[p: q+1]
        right = alist[q+1: r+1]
        
        for i in range(p, r+1):
            if len(left) > 0 and len(right) > 0:
                if left[0] > right[0]:
                    alist[i] = left.pop(0)
                else:
                    alist[i] = right.pop(0)
            elif len(right) == 0:
                alist[i] = left.pop(0)
            elif len(left) == 0:
                alist[i] = right.pop(0)

    def _merge_sort(self, alist, p, r):
        if p < r:
            q = int((p+r)/2)
            self._merge_sort(alist, p, q)               #先拆左边,拆到单个元素为止
            self._merge_sort(alist, q+1, r)           #拆分合并过程类似二叉树结果
            self._merge(alist, p, q, r)

    def __call__(self, sort_list):                      #让merge_sort成为callable类,即可调用
        self._merge_sort(sort_list, 0, len(sort_list)-1)
        return sort_list

堆排序

算法思路:
堆结构类似二叉树,以列表形式存储。i节点的子节点是i2+1和i2+2,二叉树的前n/2个节点是非叶子结点。
堆排序就是迭代创建最大值堆的过程:
建立最大值堆,把最大值与最尾节点交换。
将最尾元素之前的列表进行建堆(之前行为只改变了堆顶节点,所以这时只需要对堆顶节点建堆),并把最大值与此时列表最尾节点交换,迭代这一过程。
代码结构:
针对某一节点的建堆函数:比较某一节点与其子节点的值,交换出最大值,并对这一 节点的子节点迭代调用此函数。确保以某一节点为堆顶的堆是最大值堆。
对所有非叶子结点从下往上迭代建最大值堆,确保整个堆是最大值堆。
将堆顶节点交换到堆尾,并对其余节点迭代此过程。
代码实现:

class heap_sort(object):
    def _left(self, i):
        return 2 * i + 1
    def _right(self, i):
        return 2 * i + 2
        
    def _max_heapify(self, alist, i, heap_size=None):
        """
        从某个节点开始构建最大值堆,并迭代
        """
        length = len(alist)
        
        if heap_size is None:
            heap_size = length
        
        l = self._left(i)
        r = self._right(i)

        if l < heap_size and alist[l] > alist[i]:      # 确保子节点存在
            max_index = l
        else:
            max_index = i
        if r < heap_size and alist[r] > alist[max_index]:
            max_index = r

        if max_index != i:
            alist[i], alist[max_index] = alist[max_index], alist[i]
            self._max_heapify(alist, max_index, heap_size)   #  这里要迭代是为了保证堆是最大值堆,既每个父节点都大于子节点
    
    def _build_max_heap(self, alist):
        rood_end = len(alist) / 2     # 获取到所有非叶子节点
        for i in range(rood_end)[::-1]:    # 从非叶子结点开始构建最大值堆
            self._max_heapify(alist, i)   
            
    def __call__(self, sort_list):
        self._build_max_heap(sort_list)
        heap_size = len(sort_list)
        for i in range(1, heap_size)[::-1]:
            sort_list[0], sort_list[i] = sort_list[i], sort_list[0]
            heap_size -= 1
            self._max_heapify(sort_list, 0, heap_size)   # 最大值堆已建好,这时只需要针对堆顶建堆
        return sort_list

快速排序

算法思路:
选取一个基准值,大于基准值的数放左边,小于基准值的数放右边(类似于二叉查找树)。再对每个子序列迭代这一过程,直到子序列为单个数。
对于一个已知基准值的列表,如何将比基准值大的数放到基准值右边,比基准值小的数放基准值左边?
设置一个指针,使指针右边的数都是比基准值大(也就是说,指针指向的是最后一个比基准值小的数);
循环列表时,如果遇到比基准值大的数,指针位置不变;如果遇到比基准值小的数,指针向后移,并且将这个数与此时指针指向的数(第一个比基准值大的数)交换位置,使指针指向的又是最后一个比基准值小的数;
循环完成之后,将基准值与指针后的第一个数(第一个比基准值大的数)交换位置,这时基准值左边的数都比它小,右边的数都比它大。
代码实现

import random
class quick_sort(object):
    def _partition(self, alist, p, r):
        i = p-1    # 设置指针,首先假设所有数都比基准值大
        flag = random.randint(p, r)     # 随机选取基准值 
        x = alist[flag]            
        alist[r], alist[flag] = alist[flag], alist[r]   # 将基准值放到列表最后放,方便循环处理
        for j in range(p, r):    # 对于基准值之前的数进行循环
            if alist[j]<x:
                i += 1
                alist[i], alist[j] = alist[j], alist[i]
        alist[i+1], alist[r] = alist[r], alist[i+1]
        return i+1  # 返回的是基准值的index
 
    def _quicksort(self, alist, p, r):
        if p<r:
            q = self._partition(alist, p, r)
            self._quicksort(alist, p, q-1)   # 迭代基准值之前的序列
            self._quicksort(alist, q+1, r)   # 迭代基准值之后的序列
 
    def __call__(self, sort_list):
        self._quicksort(sort_list, 0, len(sort_list)-1)
        return sort_list

原文地址:https://jiayi.space/post/ge-chong-pai-xu-de-pythonshi-xian