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中常用的排序算法和排序函數，以及簡單的效率對比。在實際開發中，我們應該根據實際情況選擇最優的排序算法和排序函數，從而提高程序的效率。