美文网首页
使用python3实现冒泡排序、选择排序和快速排序

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

作者: 悟饭哪 | 来源:发表于2019-12-09 23:49 被阅读0次

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

    相关文章

      网友评论

          本文标题:使用python3实现冒泡排序、选择排序和快速排序

          本文链接:https://www.haomeiwen.com/subject/rfcwgctx.html