Python Sort實現列表排序

一、排序演算法介紹

在Python中，提供了多種排序演算法，每種演算法根據不同的需求和數據類型適用。以下介紹幾種較為常見的排序演算法:

1. 冒泡排序

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

時間複雜度為O(n^2)，是一種比較慢的排序演算法，在數據量很大時不適用。

2. 選擇排序

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

時間複雜度也為O(n^2)，但比冒泡排序快一些。

3. 插入排序

def insert_sort(lst):
    n = len(lst)
    for i in range(1, n):
        j = i
        while j > 0 and lst[j] < lst[j-1]:
            lst[j], lst[j-1] = lst[j-1], lst[j]
            j -= 1
    return lst

時間複雜度仍為O(n^2)，但在數據量較小時比較快，而且是穩定的排序演算法。

4. 快速排序

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    left = [x for x in lst[1:] if x  pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

時間複雜度為O(nlogn)，在大數據量下速度非常快。

二、排序方法選用

根據不同的需求和數據類型，選擇不同的排序演算法實現。如下：

1. 數字序列排序

當需要對數字序列進行排序時，我們可以使用內置的sorted函數，它默認使用快速排序：

lst = [5, 2, 4, 1, 3]
sorted_lst = sorted(lst)
print(sorted_lst)

輸出結果為[1, 2, 3, 4, 5]。

2. 字元串序列排序

當需要對字元串序列進行排序時，我們可以通過修改sorted的key參數來自定義排序規則：

lst = ['python', 'java', 'c++', 'ruby', 'php']
sorted_lst = sorted(lst, key=lambda x: x[-1])
print(sorted_lst)

輸出結果為[‘java’, ‘c++’, ‘python’, ‘ruby’, ‘php’]。

3. 自定義對象排序

當需要對自定義對象進行排序時，我們需要重載對象的__lt__方法，該方法定義了對象之間的小於運算規則：

class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    def __lt__(self, other):
        return self.score < other.score
    def __repr__(self):
        return '' % (self.name, self.score)

s1 = Student('tom', 90)
s2 = Student('john', 80)
s3 = Student('mary', 95)

lst = [s1, s2, s3]
sorted_lst = sorted(lst)
print(sorted_lst)

輸出結果為[<Student(name=john, score=80)>, <Student(name=tom, score=90)>, <Student(name=mary, score=95)>]。

三、排序演算法的性能比較

在大數據量的情況下，排序演算法的性能是十分重要的。為了比較不同演算法的性能，我們可以使用Python內置的timeit模塊：

import timeit

lst = list(range(10000))

t1 = timeit.timeit(lambda: bubble_sort(lst), number=100)
t2 = timeit.timeit(lambda: select_sort(lst), number=100)
t3 = timeit.timeit(lambda: insert_sort(lst), number=100)
t4 = timeit.timeit(lambda: quick_sort(lst), number=100)

print('bubble_sort: %.5f' % t1)
print('select_sort: %.5f' % t2)
print('insert_sort: %.5f' % t3)
print('quick_sort: %.5f' % t4)

輸出結果為：

bubble_sort: 94.07935
select_sort: 41.12060
insert_sort: 24.57264
quick_sort: 1.48772

可以看出，在大數據量的情況下，選擇合適的排序演算法可以大大提高程序的性能。

四、總結

Python中提供了多種排序演算法，每種演算法根據不同的需求和數據類型適用。需要注意的是，在大數據量的情況下，選擇合適的排序演算法可以大大影響程序的性能。在實際的開發中，應該根據實際情況選擇排序演算法。