python排序算法,冒泡排序和快排

2023-12-19 00:03:18

对于排序算法中比较知名的两个算法,分别就是冒泡排序和快速排序,在日常学习和使用中都会听到这两种排序算法的名称,这里主要介绍如何使用python来实现这两种排序算法。

冒泡排序的实现:一是从集合第一个元素开始,每两个相邻的元素进行比较大小的行为,然后令数值较大的元素向后移动,交换这两个元素的位置,依次对比,直到数组的末尾为结束。经过这一次完整的对比之后,即可找到整个集合中最大的那个元素,并且这个元素已经经过移动后,到达了最后的一个位置。

二是进行第二次排序,第二次排序同样是从元素集合的第一个元素开始,往后进行对比,相邻两个元素较大者往后移位置,一直往后对比大小直到倒数的第二个位置结束。这次得到的结果是第二大的元素到了倒数第二个位置。

三就是根据以上步骤进行对比,每一趟都会得到一个元素自己所在的最终的位置,直到所有元素都完成了排序,就得到了最终的排序好的结果。

添加图片注释,不超过 140 字(可选)

B = [20, 30, 90, 10, 28, 49, 20, 41, 42, 78],对B集合进行了冒泡排序后的输出结果

def bubbleSort(nums):
    for i in range(len(nums) - 1):
        flag = 0
        for j in range(len(nums) - 1 - i):
            if nums[j] > nums[j + 1]:
                temp = nums[j + 1]
                nums[j + 1] = nums[j]
                nums[j] = temp
                flag = 1
        if flag == 0:
            break
    return nums

以上是冒泡排序的python实现。

对于冒泡排序的时间复杂度较高的问题,对冒泡排序进行优化之后得出的快排。

快排的核心思想就是经过一趟比较即可得到某个元素在排序后的最终位置。

其实现过程是在一个集合中{a1,...,an},如果选取a1作为基准的元素,设置i,j指针,初始值为i=0,j=n-1,然后将a1保存为关键key=a1。从后往前进行搜索,过程中从如果j元素的值大于key,则j--,一直直到找到第一个比key小的值,然后就将i的值和j的值交换位置。然后就是从前往后搜索了,从头开始查找,如果i元素的值比key的值大的话,则i++,一直到找到比key的值大的元素,又将i和j的值进行位置交换。一直返回执行以上操作,直到i和j下标一样,就是完成了一趟排序了。这个时候key所在的位置就是其在最终排序中的位置,而对于这个key左右的子集合,是可以套用以上的排序过程。直到最后就是分的每个子集合都只有一个元素为止。即完成了排序。

添加图片注释,不超过 140 字(可选)

快速排序的实现如下:

def quickSort(nums, low, high):
    i = low
    j = high
    key = nums[i]
    while i < j:
        while i < j and key <= nums[j]:
            j -= 1
        nums[i] = nums[j]
        while i < j and key >= nums[i]:
            i += 1
        nums[j] = nums[i]
    nums[i] = key
    quickSort(nums, low, i - 1)
    quickSort(nums, i + 1, high)

文章来源:https://blog.csdn.net/Mrsawyer/article/details/135072032
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。