Python实现常见的算法排序

本文将从多个方面对Python实现常见的算法排序进行详细阐述。

一、冒泡排序

冒泡排序是一种简单直观的排序算法，它重复比较相邻的两个元素，如果顺序错误就交换位置，直到整个数组排序完成。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        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

arr = [5, 9, 3, 1, 2]
sorted_arr = bubble_sort(arr)
print(sorted_arr)

上述代码实现了冒泡排序的功能。首先，声明了一个bubble_sort函数，它接受一个待排序的数组作为参数。然后，利用两个嵌套的循环遍历数组，并通过比较相邻元素的大小，交换位置以实现排序。最后，返回排序后的数组。

冒泡排序的时间复杂度是O(n^2)，在最坏情况下需要进行n*(n-1)/2次比较和交换操作。

二、插入排序

插入排序是一种简单且高效的排序算法，它将待排序的元素按照顺序一个一个地插入到已经排序好的部分中。

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

arr = [5, 9, 3, 1, 2]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

上述代码实现了插入排序的功能。首先，声明了一个insertion_sort函数，它接受一个待排序的数组作为参数。然后，通过一个外层循环遍历整个数组，将每个元素插入到已经排序好的部分中。内层循环用来找到正确的插入位置，并移动较大的元素以腾出空间。最后，返回排序后的数组。

插入排序的时间复杂度是O(n^2)，在最坏情况下需要进行n*(n-1)/2次比较和移动操作。

三、选择排序

选择排序是一种简单直观的排序算法，它每次从待排序的数组中选择最小（或最大）的元素，然后将其放到已经排序好的部分的末尾。

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

arr = [5, 9, 3, 1, 2]
sorted_arr = selection_sort(arr)
print(sorted_arr)

上述代码实现了选择排序的功能。首先，声明了一个selection_sort函数，它接受一个待排序的数组作为参数。然后，通过两个嵌套的循环遍历整个数组，每次找到当前未排序部分的最小元素，并将其与当前位置元素进行交换。最后，返回排序后的数组。

选择排序的时间复杂度是O(n^2)，在最坏情况下需要进行n*(n-1)/2次比较和交换操作。

四、快速排序

快速排序是一种高效的排序算法，它采用分治的思想，通过选取一个基准元素，将数组分成两个子数组，然后对子数组进行递归排序。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left, right, equal = [], [], []
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            equal.append(num)
    return quick_sort(left) + equal + quick_sort(right)

arr = [5, 9, 3, 1, 2]
sorted_arr = quick_sort(arr)
print(sorted_arr)

上述代码实现了快速排序的功能。首先，声明了一个quick_sort函数，它接受一个待排序的数组作为参数。然后，选择一个基准元素（本例中选择中间位置元素），将数组按照基准元素分成三个部分：小于基准元素的部分、等于基准元素的部分和大于基准元素的部分。接着，对左右两个子数组进行递归排序，并将排序后的子数组与等于基准元素的部分合并。最后，返回排序后的数组。

快速排序的平均时间复杂度是O(nlogn)，最坏情况下可以达到O(n^2)，但概率很小。

五、归并排序

归并排序是一种高效的排序算法，它采用分治的思想，将数组不断划分成更小的部分进行排序，然后将排序好的部分合并。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [5, 9, 3, 1, 2]
sorted_arr = merge_sort(arr)
print(sorted_arr)

上述代码实现了归并排序的功能。首先，声明了一个merge_sort函数，它接受一个待排序的数组作为参数。然后，通过递归将数组不断划分成更小的部分，直到只剩下一个元素。接着，将排序好的子数组进行合并，这里使用了一个名为merge的辅助函数来实现。最后，返回排序后的数组。

归并排序的时间复杂度是O(nlogn)，它是一种稳定的排序算法。

六、总结

本文详细介绍了Python实现常见的算法排序。冒泡排序通过相邻元素的比较和交换来实现排序；插入排序通过将元素逐个插入到已排序部分的适当位置来实现排序；选择排序通过选择最小（或最大）元素并将其放到已排序部分的末尾来实现排序；快速排序通过选取基准元素，并将数组分成两个子数组递归排序来实现排序；归并排序通过不断划分和合并数组来实现排序。

每种排序算法都有其特点和适用场景，选择合适的算法可以提高排序效率。在实际开发中，要根据具体需求选择适当的排序算法。