Python List Sorting: Improve Your Programming Efficiency

一、排序算法

Python list的排序算法是一个非常基础的知识点，这里我们主要介绍常用的排序算法。

1. Bubble Sort（冒泡排序）

def bubbleSort(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. Insertion Sort（插入排序）

def insertionSort(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
    return arr

插入排序是一种简单而稳定的排序算法。 它的基本思想是将一个元素插入到已排序的序列中，初始状态认为有一个已排序的序列，只包含一个元素。

3. Quick Sort（快速排序）

def quickSort(arr, low, high):
    if low < high:
 
        pi = partition(arr,low,high)
 
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
 
def partition(arr,low,high):
    i = ( low-1 )         
    pivot = arr[high]     
 
    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 )

快速排序是一种非常快速的排序算法。 它的基本思想是分治。 具体步骤为，从数组中选取一个元素作为基准，并将此元素将小于基准的元素移动到基准的左侧，将大于基准的元素移动到右侧。

二、排序函数

Python中内置了多种列表排序函数，它们极大的方便了Python程序员的工作。 接下来我们将介绍一些Python内置的列表排序函数。

1. sorted()

sorted()函数可以接受一个列表或迭代器对象，返回一个新的按从小到大排序的列表。

a = [5, 2, 3, 1, 4]
sorted_a = sorted(a)
print(sorted_a)    # [1, 2, 3, 4, 5]

2. list.sort()

sort()方法就地对列表进行排序，返回None。

a = [5, 2, 3, 1, 4]
a.sort()
print(a)    # [1, 2, 3, 4, 5]

3. heapq.nlargest()

heapq模块提供了许多有用的函数和数据结构，其中包括nlargest()，它可以返回一个列表中最大的n个元素。

import heapq
a = [5, 2, 3, 1, 4]
largest_a = heapq.nlargest(3, a)
print(largest_a)    # [5, 4, 3]

三、排序效率

排序效率是我们考虑排序算法优劣的重要因素。下面我们用实验比较各种算法的效率。

1. 冒泡排序，n=1000

import time
 
def bubbleSort(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
 
a = list(range(1000,0,-1))
start_time = time.time()    # 计时器开始时间
bubbleSort(a)
end_time = time.time()      # 计时器结束时间
print("Time taken: ",end_time-start_time,"s")    # Time taken:  0.4450087547302246 s

2. 快速排序，n=1000

import time
 
def quickSort(arr, low, high):
    if low < high:
 
        pi = partition(arr,low,high)
 
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
 
def partition(arr,low,high):
    i = ( low-1 )         
    pivot = arr[high]     
 
    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 )
 
a = list(range(1000,0,-1))
start_time = time.time()    # 计时器开始时间
quickSort(a, 0, len(a)-1)
end_time = time.time()      # 计时器结束时间
print("Time taken: ",end_time-start_time,"s")     # Time taken:  0.0024089813232421875 s

3. sorted()函数，n=1000

import time
 
a = list(range(1000,0,-1))
start_time = time.time()    # 计时器开始时间
sorted_a = sorted(a)
end_time = time.time()      # 计时器结束时间
print("Time taken: ",end_time-start_time,"s")     # Time taken:  0.0001552104949951172 s

四、总结

本文介绍了Python中常用的排序算法和排序函数，以及简单的效率对比。在实际开发中，我们应该根据实际情况选择最优的排序算法和排序函数，从而提高程序的效率。