面试刷题必看!Python中的5大排序算法及其实现代码

hang0 2020-08-16

排序是每个 IT 工程师和开发人员必备的知识技能。不仅要通过编程面试,而且要了解算法本身。不同的排序算法很好地展示了算法设计如何对程序的复杂性、速度和效率产生如此大的影响。

让我们来看看排名前5,也是最常见,面试中经常被问到的排序算法,看看如何用Python实现它们!

面试刷题必看!Python中的5大排序算法及其实现代码

1.冒泡排序

冒泡排序是 CS 入门课程中最常讲授的一种,因为它清楚地说明了排序的工作原理,同时又简单又易于理解。冒泡排序将逐步遍历列表并比较相邻的元素对。如果元素的顺序错误,则会交换这些元素。重复对列表中未排序部分的遍历,直到对列表进行排序。因为冒泡排序重复地通过列表中未排序的部分,所以它的最坏情况复杂性为O(n²)。

面试刷题必看!Python中的5大排序算法及其实现代码
def bubble_sort(arr): 
    def swap(i, j): 
        arr[i], arr[j] = arr[j], arr[i] 
 
    n = len(arr) 
    swapped = True 
     
    x = -1 
    while swapped: 
        swapped = False 
        x = x + 1 
        for i in range(1, n-x): 
            if arr[i - 1] > arr[i]: 
                swap(i - 1, i) 
                swapped = True 
                     
    return arr 

2.选择排序

选择排序也相当简单,优于冒泡排序。如果你要在这两者之间进行选择,那么最好使用默认的“右选择排序”。使用选择排序,我们将输入列表/数组分为两部分:已排序项的子列表和构成列表其余部分的剩余项的子列表。

我们首先在未排序的子列表中找到最小的元素,并将其放在已排序子列表的末尾。因此,我们不断地获取最小的未排序元素,并将其按排序顺序放入已排序的子列表中。此过程将重复进行,直到列表完全排序。

面试刷题必看!Python中的5大排序算法及其实现代码
def selection_sort(arr):         
    for i in range(len(arr)): 
        minimum = i 
         
        for j in range(i + 1, len(arr)): 
            # 选择最小值 
            if arr[j] < arr[minimum]: 
                minimum = j 
 
        # 把它放在已排序的数组结尾 
        arr[minimum], arr[i] = arr[i], arr[minimum] 
             
    return arr 

3.插入排序

插入排序比冒泡排序和选择排序都要快,而且可以说更加简单。就像在玩纸牌游戏时,洗牌的过程就是反复进行插入排序!在每次循环迭代中,插入排序从数组中删除一个元素。然后在另一个排序数组中查找该元素所属的位置,并将其插入其中。它重复这个过程,直到没有输入元素保留。

面试刷题必看!Python中的5大排序算法及其实现代码
def insertion_sort(arr): 
         
    for i in range(len(arr)): 
        cursor = arr[i] 
        pos = i 
         
        while pos > 0 and arr[pos - 1] > cursor: 
            # 交换列表中的数字 
            arr[pos] = arr[pos - 1] 
            pos = pos - 1 
        # 中断并进行最终交换 
        arr[pos] = cursor 
 
    return arr 

4.合并排序

合并排序是一个完美的分而治之的算法例子。使用这种算法只需要通过以下两个主要步骤:

(1) 连续分割未排序的列表,直到有N个子列表,其中每个子列表都有1个“未排序”的元素,N是原始数组中的元素数。

(2) 反复合并,即一次将两个子列表合并在一起,生成新的已排序子列表,直到所有元素都完全合并到一个已排序的数组中。

面试刷题必看!Python中的5大排序算法及其实现代码
def merge_sort(arr): 
    # 对最后一个数组进行拆分 
    if len(arr) <= 1: 
        return arr 
    mid = len(arr) // 2 
    # 在两个部分上递归执行merge_sort 
    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:]) 
 
    # 合并在一起 
    return merge(left, right, arr.copy()) 
 
 
def merge(left, right, merged): 
 
    left_cursor, right_cursor = 0, 0 
    while left_cursor < len(left) and right_cursor < len(right): 
       
        # 将每一个排序并放入结果 
        if left[left_cursor] <= right[right_cursor]: 
            merged[left_cursor+right_cursor]=left[left_cursor] 
            left_cursor += 1 
        else: 
            merged[left_cursor + right_cursor] = right[right_cursor] 
            right_cursor += 1 
             
    for left_cursor in range(left_cursor, len(left)): 
        merged[left_cursor + right_cursor] = left[left_cursor] 
         
    for right_cursor in range(right_cursor, len(right)): 
        merged[left_cursor + right_cursor] = right[right_cursor] 
 
    return merged 

5.快速排序

快速排序也是一种分而治之的算法,与合并排序一样。尽管它有点复杂,但在大多数标准实现中,它的执行速度比合并排序快得多,而且很少达到O(n²)的最坏情况复杂度。它有三个主要步骤:

(1) 我们首先从数组中选择一个元素,称之为pivot。

(2) 将小于轴的所有元素移到轴的左侧;将大于轴的所有元素移到轴的右侧。这称为分区操作。

(3) 递归地将上述2个步骤分别应用于元素的每个子数组,这些元素的值比上一个轴的值小或大。

面试刷题必看!Python中的5大排序算法及其实现代码
def partition(array, begin, end): 
    pivot_idx = begin 
    for i in xrange(begin+1, end+1): 
        if array[i] <= array[begin]: 
            pivot_idx += 1 
            array[i], array[pivot_idx] = array[pivot_idx], array[i] 
    array[pivot_idx], array[begin] = array[begin], array[pivot_idx] 
    return pivot_idx 
 
def quick_sort_recursion(array, begin, end): 
    if begin >= end: 
        return 
    pivot_idx = partition(array, begin, end) 
    quick_sort_recursion(array, begin, pivot_idx-1) 
    quick_sort_recursion(array, pivot_idx+1, end) 
 
def quick_sort(array, begin=0, end=None): 
    if end is None: 
        end = len(array) - 1 
     
    return quick_sort_recursion(array, begin, end) 

--END--

相关推荐