没有比这个姿势更简单了! Python 十种排序算法详细介绍

排序是计算机程序设计中的重要概念，是任何搜索或数据处理的基础，因此排序算法也成为了计算机科学中一个重要的研究领域。Python 作为一门高级编程语言，提供了许多简单易用的排序算法，本文将详细介绍 Python 中的十种排序算法。

1. 冒泡排序(Bubble Sort)

冒泡排序是最简单的排序算法之一，它的实现方式是通过比较相邻的两个元素，如果第一个元素比第二个元素大，则交换这两个元素的位置，重复这个过程，直至列表中所有元素均排序完成。

以下是 Python 中的冒泡排序的实现代码：

```
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
```

2. 选择排序(Selection Sort)

选择排序是另一种简单的排序算法，它的实现方式是每次从列表中选择一个最小的元素，并将其放到列表的第一个位置，然后再在剩余的元素中选择一个最小的元素，将其放到列表的第二个位置，重复这个过程，直至列表中所有元素均排序完成。

以下是 Python 中的选择排序的实现代码：

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

3. 插入排序(Insertion Sort)

插入排序是将一个元素插入到已排序列表中的正确位置的排序算法。它的实现方式是从列表的第二个元素开始，将其与已排序的元素逐一比较，直至找到正确位置并插入该元素，重复这个过程，直至列表中所有元素均排序完成。

以下是 Python 中的插入排序的实现代码：

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

4. 希尔排序(Shell Sort)

希尔排序是插入排序的一种改进版本，它将要排序的列表拆分为若干子列表，对每个子列表进行排序，然后将所有子列表合并为一个，重复这个过程，直至所有元素均排序完成。

以下是 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. 归并排序(Merge Sort)

归并排序是一种分治算法，它将要排序的列表拆分为若干子列表，对每个子列表进行排序，然后将所有子列表合并为一个，重复这个过程，直至所有元素均排序完成。

以下是 Python 中的归并排序的实现代码：

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

6. 快速排序(Quick Sort)

快速排序是一种分治算法，它将要排序的列表拆分为若干子列表，对每个子列表进行排序，然后将所有子列表合并为一个，重复这个过程，直至所有元素均排序完成。

以下是 Python 中的快速排序的实现代码：

```
def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1
```

7. 堆排序(Heap Sort)

堆排序是一种基于堆的排序算法，它将要排序的列表构建为一个堆，然后重复执行从堆中删除最大元素并将其放入已排序的列表中的过程，直至所有元素均排序完成。

以下是 Python 中的堆排序的实现代码：

```
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n, -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. 计数排序(Counting Sort)

计数排序是一种非比较排序算法，它通过确定每个元素在列表中出现的次数来排序，然后重复执行统计并重新排序的过程，直至所有元素均排序完成。

以下是 Python 中的计数排序的实现代码：

```
def counting_sort(arr):
    max_element = int(max(arr))
    min_element = int(min(arr))
    range_of_elements = max_element - min_element + 1
    count_elements = [0] * range_of_elements
    output_arr = [0] * len(arr)
    for i in range(0, len(arr)):
        count_elements[arr[i]-min_element] += 1
    for i in range(1, len(count_elements)):
        count_elements[i] += count_elements[i-1]
    for i in range(len(arr)-1, -1, -1):
        output_arr[count_elements[arr[i]-min_element] - 1] = arr[i]
        count_elements[arr[i]-min_element] -= 1
    for i in range(0, len(arr)):
        arr[i] = output_arr[i]
    return arr
```

9. 桶排序(Bucket Sort)

桶排序是另一种非比较排序算法，它通过将要排序的元素分配到不同的桶中，然后对每个桶中的元素进行排序，并将所有桶合并为一个排序完成的列表。

以下是 Python 中的桶排序的实现代码：

```
def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr
    min_element = int(min(arr))
    max_element = int(max(arr))
    bucket_count = (max_element - min_element) // bucket_size + 1
    buckets = []
    for i in range(0, bucket_count):
        buckets.append([])
    for i in range(0, len(arr)):
        buckets[(arr[i] - min_element) // bucket_size].append(arr[i])
    arr = []
    for i in range(0, len(buckets)):
        buckets[i].sort()
        for j in range(0, len(buckets[i])):
            arr.append(buckets[i][j])
    return arr
```

10. 基数排序(Radix Sort)

基数排序是另一种非比较排序算法，它通过将要排序的元素按照位数进行排序，先按照个位排序，再按照十位排序，以此类推，重复这个过程，直至所有元素均排序完成。

以下是 Python 中的基数排序的实现代码：

```
def radix_sort(arr):
    radix = 10
    max_len = False
    tmp, placement = -1, 1
    while not max_len:
        max_len = True
        buckets = [list() for _ in range(radix)]
        for i in arr:
            tmp = i // placement
            buckets[tmp % radix].append(i)
            if max_len and tmp > 0:
                max_len = False
        x = 0
        for bucket in buckets:
            for i in bucket:
                arr[x] = i
                x += 1
        placement *= radix
    return arr
```

总结

本文详细介绍了 Python 中的十种排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。这些算法涵盖了各种不同的排序场景，开发人员可以根据实际需求选择最适合的算法。