01. 冒泡排序

[utterances-bot]

01. 冒泡排序 | 算法通关手册

1. 冒泡排序 # 1. 冒泡排序算法思想 # 冒泡排序（Bubble Sort）基本思想：
   第 i (i = 1，2，… ) 趟排序时从序列中前 n - i + 1 个元素的第 1 个元素开始，相邻两个元素进行比较，若前者大于后者，两者交换位置，否则不交换。
   冒泡排序

https://algo.itcharge.cn/01.Array/02.Array-Sort/01.Array-Bubble-Sort/

[Netlessfish]

python中交换两个两个数可以不使用temp暂存

[leixd1994]

然后将第 2 个元素与第 3 个元素比较，也就是将 2 和 3 进行比较。因为 2 < 3，所以不用交换； 这句话有笔误吧？ 此时第二个元素是6 而不是2

[1002637937]

for i in range(len(arr)): 这里需要-1吧

[itcharge]

for i in range(len(arr)): 这里需要-1吧

是的，需要减 1。已更正，感谢指正。

[FFFgrid]

不用减一结果也是对的啊

[shuaibird]

代码实现没有最佳时间复杂度O(n)的优化，需要在第二个循环判断是否进行了位置交换

[itcharge]

感谢指出，目前代码中已实现。
在数组元素已经是升序的状态下，一趟排序后，flag 标志位仍为 False，此时跳出循环，算法结束，这种情况下时间复杂度就是 O(n)。

[hanxiang0227]

打卡

[Paden79555]

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

[Paden79555]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)