一、排序算法
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中常用的排序算法和排序函数，以及简单的效率对比。在实际开发中，我们应该根据实际情况选择最优的排序算法和排序函数，从而提高程序的效率。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/186654.html
微信扫一扫 
支付宝扫一扫 