冒泡排序的时间复杂度是O(n^2)
,选择排序的时间复杂度也是O(n^2)
,这是因为这两种排序算法的元素比较次数是相同的。但因为冒泡排序是每比较一次,就会交换一次,而选择排序是每一轮循环结束后才进行一次交换。所以,选择排序要相对速度更快一些。
冒泡排序
def bubbleSort(nums):
for i in range(0, len(nums)):
for j in range(0, (len(nums) - 1 - i)):
if nums[j] > nums[j+1]:
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
return nums
选择排序
def selectSort(nums):
for i in range(len(nums) - 1, 0, -1):
maxIndex = 0
for j in range(1, i + 1):
if nums[j] > nums[maxIndex]:
maxIndex = j
temp = nums[i]
nums[i] = nums[maxIndex]
nums[maxIndex] = temp
return nums
快速排序
def quickSort(nums, left, right):
i = left
j = right
base = nums[left]
if i < j:
return nums
while i != j:
while nums[j] >= base and i < j:
j = j - 1
while nums[i] <= base and i < j:
i = i + 1
if i < j:
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
nums[left] = nums[i]
nums[i] = base
quickSort(nums, left, i-1)
quickSort(nums, i+1, right)
return nums
调用
nums = [23, 18, 232, 10, 5, 88, 34, 11, 9]
newNums1 = bubbleSort(nums)
newNums2 = selectSort(nums)
newNums3 = quickSort(nums, 0, len(nums) - 1)
print(newNums1)
print(newNums2)
print(newNums3)
打印结果
[5, 9, 10, 11, 18, 23, 34, 88, 232]
[5, 9, 10, 11, 18, 23, 34, 88, 232]
[5, 9, 10, 11, 18, 23, 34, 88, 232]
Have fun.
网友评论