Python排序

Python中有很多种排序算法，下面介绍其中的几种。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就将它们交换过来。

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]
                
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print("%d" %arr[i])

2. 快速排序

快速排序是一种排序算法，通常被认为是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

def quick_sort(arr, left, right):
    if left < right:
        pivot_index = partition(arr, left, right)
        quick_sort(arr, left, pivot_index-1)
        quick_sort(arr, pivot_index+1, right)

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

arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr)-1)
print("排序后的数组：")
for i in range(len(arr)):
    print("%d" %arr[i])

3. 归并排序

归并排序是一种分治算法，其思想就是将原始数组切分为越来越小的半子数组，直到每个子数组只有一个元素，然后在将子数组合并成较大的有序数组，直到最后只有一个有序数组。

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

arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print("%d" %arr[i])

4. 插入排序

插入排序是一种简单直观的排序算法，其基本思想是将待排序的数组分为已排序和未排序两个部分，每次从未排序的部分中取出一个元素插入到已排序的部分中。

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

arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print("%d" %arr[i])

5. 选择排序

选择排序是一种简单直观的排序算法，其基本思想是每次从待排序的数组中选择最小（或最大）的一个元素，放到已排好序的数组的末尾。

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

arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("排序后的数组：")
for i in range(len(arr)):
    print("%d" %arr[i])

这些排序算法的时间复杂度不尽相同，可以根据具体的应用场景选择合适的算法。