大厂面试常考:快速排序冒泡排序算法

在大厂面试中，经常会出现排序算法的相关问题。快速排序和冒泡排序是最常见的排序算法之一，本文将详细讲解这两种常见的排序算法。

快速排序

概念

快速排序采用“分治法”的思想。首先选取一个基准点，将数组分为左右两部分。左侧部分小于基准点，右侧部分大于基准点。接下来，递归地对左、右两个子数组执行快速排序。

代码实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0] # 选取第一个元素为基准点
        left = [i for i in arr[1:] if i < pivot]
        right = [i for i in arr[1:] if i >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

示例

假设我们有一个数组 [3, 7, 4, 1, 9, 2, 6, 5, 8]，根据快速排序算法，我们选取第一个元素 3 为基准点。经过一次排序，数组变成了：

[2, 1, 3, 4, 9, 7, 6, 5, 8]

接下来，我们递归地对左右两个子数组进行排序，最终得到排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

冒泡排序

概念

冒泡排序是一种简单的排序算法。它从第一个元素开始，将相邻的两个元素进行比较，如果前一个元素比后一个元素大，则交换位置。重复这个过程，直到整个数组排序完成。

代码实现

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

示例

假设我们有一个数组 [3, 7, 4, 1, 9, 2, 6, 5, 8]，根据冒泡排序算法，经过一次排序，数组变成了：

[3, 4, 1, 7, 2, 6, 5, 8, 9]

接下来，我们重复这个过程，进行多次排序，直到得到排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

总结

快速排序和冒泡排序算法都是常见的排序算法，在大厂面试中经常被问及。本文对快速排序和冒泡排序算法的概念、代码实现以及示例进行了详细讲解。熟练掌握这两种排序算法，对于大厂面试及日常开发都会有帮助。