算法系列15天速成 第一天 七大经典排序【上】

我会为你详细讲解“算法系列15天速成 第一天 七大经典排序【上】”的完整攻略。

标题

算法系列15天速成 第一天 七大经典排序【上】

内容

本文主要介绍了常用的七大经典排序算法，分别是插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序以及堆排序。对每个算法的特点、实现过程和时间复杂度进行了详细的讲解，同时也对每个算法进行了简单的示例说明。

插入排序

插入排序的基本思想是将待排序的元素插入到已经排好序的序列里面。具体实现过程为：从第一个元素开始，将其插入到已经排好序的序列中，然后再取出下一个元素进行插入，以此类推，直到全部元素有序。时间复杂度为O(n^2)。

以下是一个示例代码：

def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array

希尔排序

希尔排序是插入排序的一种更高效的改进版本，它通过将序列拆分成若干个小的子序列，然后对每个子序列进行插入排序，最后将所有子序列进行合并。希尔排序的时间复杂度是介于O(n)和O(n^2)之间。

以下是一个示例代码：

def shell_sort(array):
    n = len(array)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = array[i]
            j = i
            while j >= gap and array[j-gap] > temp:
                array[j] = array[j-gap]
                j -= gap
            array[j] = temp
        gap //= 2
    return array

选择排序

选择排序的基本思想是将整个序列看作是由两个部分组成，一个是已经排好序的部分，另一个是未排好序的部分，每次从未排好序的部分中选择一个最小的元素然后放到已排好序的序列的末尾。选择排序的时间复杂度为O(n^2)。

以下是一个示例代码：

def selection_sort(array):
    for i in range(len(array)):
        min_index = i
        for j in range(i+1, len(array)):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]
    return array

冒泡排序

冒泡排序的基本思想是两两比较相邻的元素，如果前一个元素比后一个元素大，就交换这两个元素，循环操作直到排序完成。冒泡排序的时间复杂度为O(n^2)。

以下是一个示例代码：

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

快速排序

快速排序是一种典型的分治算法，它通过选择一个关键元素把待排序列分成两个子序列，分别对两个子序列进行递归排序，最后将两个子序列合并成一个有序序列。快速排序的时间复杂度为O(nlogn)。

以下是一个示例代码：

def partition(array, left, right):
    pivot_index = left
    pivot = array[pivot_index]
    left += 1
    while True:
        while left <= right and array[left] < pivot:
            left += 1
        while left <= right and array[right] > pivot:
            right -= 1
        if left > right:
            break
        else:
            array[left], array[right] = array[right], array[left]
    array[pivot_index], array[right] = array[right], array[pivot_index]
    return right

def quick_sort_helper(array, left, right):
    if left >= right:
        return
    pivot_index = partition(array, left, right)
    quick_sort_helper(array, left, pivot_index-1)
    quick_sort_helper(array, pivot_index+1, right)

def quick_sort(array):
    quick_sort_helper(array, 0, len(array)-1)
    return array

归并排序

归并排序的基本思想是将待排元素分成若干个子序列，然后将相邻的两个子序列进行归并操作，重复执行此操作直到整个序列有序为止。归并排序的时间复杂度为O(nlogn)。

以下是一个示例代码：

def merge(array, start, mid, end):
    left = array[start:mid]
    right = array[mid:end]
    l, r = 0, 0
    for i in range(start, end):
        if l >= len(left):
            array[i] = right[r]
            r += 1
        elif r >= len(right):
            array[i] = left[l]
            l += 1
        elif left[l] < right[r]:
            array[i] = left[l]
            l += 1
        else:
            array[i] = right[r]
            r += 1

def merge_sort_helper(array, start, end):
    if start >= end - 1:
        return
    mid = start + (end - start) // 2
    merge_sort_helper(array, start, mid)
    merge_sort_helper(array, mid, end)
    merge(array, start, mid, end)

def merge_sort(array):
    merge_sort_helper(array, 0, len(array))
    return array

堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进，堆排序的时间复杂度为O(nlogn)。

以下是一个示例代码：

def heapify(array, n, i):
    largest = i
    left = 2*i+1
    right = 2*i+2

    if left < n and array[largest] < array[left]:
        largest = left
    if right < n and array[largest] < array[right]:
        largest = right

    if largest != i:
        array[i], array[largest] = array[largest], array[i]
        heapify(array, n, largest)

def heap_sort(array):
    n = len(array)
    for i in range(n//2-1, -1, -1):
        heapify(array, n, i)

    for i in range(n-1, -1, -1):
        array[0], array[i] = array[i], array[0]
        heapify(array, i, 0)
    return array

以上就是本文对于七大经典排序算法的详细讲解，希望能对您有所帮助。