施坤的博客
0%

冒泡排序

发表于 分类于 阅读次数： Valine：

说明

  • 冒泡排序法是通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面，就像水底的气泡一样向上冒，故称这种排序方法为冒泡排序法。

冒泡算法步骤

  • 先将序列中第 1 个元素与第 2 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换；
  • 然后将第 2 个元素与第 3 个元素比较，若前者大于后者，则两者交换位置，否则不交换；
  • 依次类推，直到第 n - 1 个元素与第 n 个元素比较（或交换）为止。经过如此一趟排序，使得 n 个元素中值最大元素被安置在序列的第 n 个位置上。

冒泡排序动画演示

bubbleSort

冒泡排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def bubbleSort(self, arr):
        for i in range(len(arr)):
            for j in range(len(arr) - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

        return arr

    def sortArray(self, nums):
        return self.bubbleSort(nums)

if __name__ == "__main__":
   st = Solution().sortArray([10,4,2,11,8])
   print(st)
    
 [2, 4, 8, 10, 11]

移动零

  • 原题来自于这里
  • 这是对冒泡算法的运用

题目大意

给你一个数组，将所有 0 移动到末尾，并保持原有的非 0 数字的相对顺序。要求只能在原数组上进行操作。

解题思路

  • 使用两个指针 left，right。left 指向处理好的非 0 数字数组的尾部，right 指针指向当前待处理元素。

  • 不断向右移动 right 指针，每次移动到非零数，则将左右指针对应的数交换，交换同时将 left 右移。

  • 此时，left 指针左边均为处理好的非零数，而从 left 指针指向的位置开始， right 指针左边都为 0。

  • 遍历结束之后，则所有 0 都移动到了右侧，且保持了非零数的相对位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def moveZeroes(self, nums):
        left = 0
        right = 0
        while right < len(nums):
        # 不断向右移动 right 指针
            if nums[right] != 0:
            # 每次移动到非零数，则将左右指针对应的数交换，
                nums[left], nums[right] = nums[right], nums[left]
                # 交换同时将 left 右移
                left += 1
            # 不断向右移动 right 指针
            right += 1
        print(nums)
if __name__ == "__main__":
   st = Solution().moveZeroes([1,1,0,1,0,1])

   [1, 1, 1, 1, 0, 0]