排序算法函数 - 用Python实现十种不同的排序算法

排序算法是计算机科学中一个非常重要的主题之一。它们被用于对元素序列进行排序，可以看作是对数据的重新排列，使其按照一定规则排序，以便更容易查找，处理及使用。在本文中，我们将展示10种不同的排序算法，用Python语言实现，希望能够帮助您更好地理解排序算法的原理与实现。

1. 冒泡排序

冒泡排序是一种简单而直观的排序算法。它的基本思想是，从序列的起始位置开始，依次比较相邻的两个元素，若前者比后者大，则交换它们的位置。这样一次遍历之后，最大的元素就被移动到了序列的末尾。然后，再从序列的起始位置开始，重复上述操作，直到整个序列被排序完成。

下面是Python实现冒泡排序算法的代码：

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

2. 选择排序

选择排序是一种简单的排序算法，其基本思想是，首先在序列中找到最小（或最大）的元素，然后将其放在序列的起始位置。接着，再在除去已排好序的部分的剩余序列中找到最小（或最大）的元素，然后将其放在已排好序的元素的末尾。这样循环下去，直到整个序列被排序完成。

下面是Python实现选择排序算法的代码：

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

3. 插入排序

插入排序是一种简单的排序算法，其基本思想是，将待排序的序列分为两部分，一部分为已排序的部分，另一部分为未排序的部分。刚开始，已排序的部分只包含一个元素，即待排序序列的第一个元素。接着，将未排序的部分中的第一个元素依次与已排序的部分中的元素进行比较，找到其在已排序的部分中应该插入的位置，然后将它插入到已排序的部分中相应位置。

下面是Python实现插入排序算法的代码：

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

4. 希尔排序

希尔排序是一个基于插入排序的快速排序算法。其基本思想是，将待排序的序列分成若干个子序列，对每个子序列分别进行插入排序，然后再将它们合并成一个序列。该算法利用了插入排序在部分有序序列中的效率高的特点。

下面是Python实现希尔排序算法的代码：

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

5. 归并排序

归并排序是一种分治算法，其基本思想是将一个待排序的序列分成两个子序列，对每个子序列进行排序，然后将它们合并成一个有序序列。该算法是基于分治策略的，它将一个大的问题分成若干个小问题，然后将小问题求解，最终合并得到大问题的解。

下面是Python实现归并排序算法的代码：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_arr = arr[:mid]
        right_arr = arr[mid:]
        merge_sort(left_arr)
        merge_sort(right_arr)
        i = j = k = 0
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] < right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1
        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1
        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1
    return arr

6. 快速排序

快速排序是一种基于分治策略的排序算法，其基本思想是选择一个元素作为基准值，将序列分成两部分，一部分比基准值小，另一部分比基准值大。然后对这两个子序列分别进行递归地排序，最终得到有序的序列。

下面是Python实现快速排序算法的代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left_arr = [x for x in arr[1:] if x <= pivot]
        right_arr = [x for x in arr[1:] if x > pivot]
        return quick_sort(left_arr) + [pivot] + quick_sort(right_arr)

7. 堆排序

堆排序是一种常见的排序算法，其基本思想是将待排序的序列构造成一个完全二叉树，并将其调整为一个大顶堆（或小顶堆）。然后将堆顶元素（最大值或最小值）取出，并将其与堆的最后一个元素交换位置。接着再对除了刚才取出的元素以外的其他元素重新构建堆，重复上述操作，直到整个序列被排序完成。

下面是Python实现堆排序算法的代码：

def heap_sort(arr):
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
 
    n = len(arr)
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

8. 计数排序

计数排序是一种非比较排序算法，其基本思想是统计序列中每个元素出现的次数，然后根据元素的大小信息，将元素排列成有序的序列。该算法通常适用于