Python排序函数|极客教程

Python排序函数

介绍

排序是计算机编程中常用的操作之一，它可以帮助我们将一组数据按照一定的顺序进行排列，提高数据的查找效率。Python中提供了多种排序算法和函数，本文将详细介绍Python中的排序函数，并给出示例代码和运行结果。

排序算法

在介绍Python中的排序函数之前，我们先来了解一下常用的排序算法。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就交换位置，直到整个列表排序完成。

选择排序

选择排序也是一种简单的排序算法，它的主要思想是从待排序的数据中选择最小（或最大）的元素放到已排序序列的末尾。

插入排序

插入排序是一种简单直观的排序算法，它将数组分为已排序和未排序两部分，每次将未排序的元素插入到已排序部分的正确位置。

快速排序

快速排序是一种常用的排序算法，它使用了分治的思想，通过一趟排序将待排序的数据分割成独立的两部分，然后再分别对这两部分进行排序。

归并排序

归并排序是一种稳定的排序算法，它也使用了分治的思想，将待排序的数据分成两个子序列，分别进行排序，然后再将两个子序列合并成一个有序的序列。

堆排序

堆排序是一种非常高效的排序算法，它利用了堆这种数据结构的性质，通过构造大顶堆或小顶堆来实现排序。

排序函数

Python中的排序函数sort()和sorted()可以直接对列表进行排序。

sort()函数用于原地排序，即直接修改原列表的顺序，不会返回新的列表。

sorted()函数对原列表进行排序，并将排序结果作为返回值，原列表的顺序不变。

使用示例

冒泡排序

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

nums = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(nums)
print("冒泡排序结果：", nums)

运行结果：
冒泡排序结果： [11, 12, 22, 25, 34, 64, 90]

选择排序

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

nums = [64, 34, 25, 12, 22, 11, 90]
select_sort(nums)
print("选择排序结果：", nums)

运行结果：
选择排序结果： [11, 12, 22, 25, 34, 64, 90]

插入排序

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

nums = [64, 34, 25, 12, 22, 11, 90]
insert_sort(nums)
print("插入排序结果：", nums)

运行结果：
插入排序结果： [11, 12, 22, 25, 34, 64, 90]

快速排序

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums)//2]
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

nums = [64, 34, 25, 12, 22, 11, 90]
nums = quick_sort(nums)
print("快速排序结果：", nums)

运行结果：
快速排序结果： [11, 12, 22, 25, 34, 64, 90]

归并排序

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

def merge(left, right):
    result = []
    i = j = 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

nums = [64, 34, 25, 12, 22, 11, 90]
nums = merge_sort(nums)
print("归并排序结果：", nums)

运行结果：
归并排序结果： [11, 12, 22, 25, 34, 64, 90]

堆排序

def heapify(nums, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and nums[i] < nums[left]:
        largest = left
    if right < n and nums[largest] < nums[right]:
        largest = right
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, n, largest)

def heap_sort(nums):
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):
        heapify(nums, n, i)
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)

nums = [64, 34, 25, 12, 22, 11, 90]
heap_sort(nums)
print("堆排序结果：", nums)

运行结果：
堆排序结果： [11, 12, 22, 25, 34, 64, 90]