使用python3实现冒泡排序、选择排序和快速排序

冒泡排序的时间复杂度是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.