|
总结常用的三种排序方法：
一、选择排序
选择排序是每个元素与其后面的元素逐一进行比较和交换，时间复杂度是：O(n*n)。
def selectionSort(nums):
n = len(nums)
if n<2:
return nums
for i in range(n-1):
for j in range(i+1, n):
if nums[i]>nums[j]:
nums[i], nums[j] = nums[j], nums[i]
return nums
二、冒泡法
冒泡法是对相邻的两个元素进行交换，时间复杂度是：O(n*n)。
def bubbleSort(nums):
n = len(nums)
if n < 2:
return nums
for i in range(n-1):
for j in range(n-1-i):
if nums[j]>nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
三、快速排序
快速排序是采用分治处理，选取列表的其中一个元素作为分界项，把剩余的元素逐一与分界项进行比较，创建两个列表分别保存比分界项小的元素和大的元素，然后对这两个列表进行递归，直到列表的元素只剩一个为止。其时间复杂度为：O(n*logn)。
def quickSort(nums):
n = len(nums)
if n < 2:
return nums
small = []
big = []
for i in range(1, n):
if nums[i]<nums[0]:
small.append(nums[i])
else:
big.append(nums[i])
return quickSort(small)+[nums[0]]+quickSort(big)
|