快速排序法是一種高效的排序算法,也是Python語言中常用的排序算法之一。它的核心思想是分治法,將一個大問題分解成幾個小問題,然后遞歸解決這些小問題。在快速排序算法中,我們需要選取一個基準元素,將序列分成兩個部分,一部分小于基準元素,另一部分大于基準元素,然后對這兩個部分分別進行遞歸排序,直到整個序列有序。
def quick_sort(arr): """ 快速排序函數 :param arr: 待排序序列 :return: 排序后的序列 """ if len(arr)<= 1: return arr else: pivot = arr[0] # 選擇第一個元素作為基準元素 less = [x for x in arr[1:] if x<= pivot] # 將小于等于基準元素的元素放入less中 greater = [x for x in arr[1:] if x >pivot] # 將大于基準元素的元素放入greater中 return quick_sort(less) + [pivot] + quick_sort(greater) # 遞歸排序左右兩部分 arr = [3, 7, 1, 4, 9, 2, 6, 8, 5] sorted_arr = quick_sort(arr) print(sorted_arr) # 輸出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
上述代碼實現了快速排序的核心算法,即將序列分成兩個部分,并且遞歸對這兩個部分進行排序。具體來講,我們首先選擇第一個元素作為基準元素,并將小于等于它的元素放在一個數組less中,大于它的元素放在另一個數組greater中。然后我們分別對這兩個數組進行遞歸排序,最后將排序后的數組less、基準元素和數組greater依次連接起來即可。
快速排序的時間復雜度為O(nlogn),它是一種高效率的排序算法,被廣泛應用于各種場合之中。Python語言提供了簡單、直觀的語法,使得快速排序的實現變得非常容易。
上一篇python 降序排序數
下一篇python 怎么寫字典