91精品久久久久久久久久久久,日韩成人免费,www.啪啪,韩国人免费的吊黑,人妻嫩b,一本大道久久久综合精品,国产wwwww,97精品国产手机

點擊上方藍字關(guān)注我們

提到排序算法呀，我想你肯定不陌生。這應(yīng)該是學(xué)習(xí)編程時學(xué)到的第一個算法了吧。

我現(xiàn)在還能記得自己當(dāng)時在 VC++ 6.0 上按照譚浩強老師的 C 語言教材敲出第一個冒泡排序時的激動心情。滿滿的成就感，不得不說，編程愛好者的快樂就是如此簡單。

雖然排序在我們?nèi)粘Ｉ钪泻艹Ｒ姟⒊Ｓ谩５菍τ谀菚r的自己來說還是很難理解的。而且自己也是在對比著書修改了很多遍才正確的編譯運行。

當(dāng)時我就想著要是有一個算法執(zhí)行過程的動態(tài)圖那就好了。我一直也在這樣嘗試著這樣做，今天我就帶你來體驗下冒泡排序算法的動態(tài)執(zhí)行過程。

話不多說，直接上干貨，先帶你看下效果，包你滿意。

不僅是簡單的算法執(zhí)行過程，我還會為你介紹一些改進的技巧，讓你更加游刃有余，顯示出自己的內(nèi)功修養(yǎng)。

有必要手動寫排序算法嗎？

可能有人覺得現(xiàn)在不需要自己手動寫排序算法了，用的時候直接調(diào)用編程語言內(nèi)置的庫函數(shù)就行了。

在日常的工作學(xué)習(xí)中，我覺得大部分人也就是這樣做的，包括我自己在內(nèi)。而且你自己寫排序算法有 Bug 不說，就算沒有 Bug，肯定也沒有編程語言內(nèi)置的庫函數(shù)高效。

但是這并不能說我們不需要掌握排序算法了，我覺得主要原因有兩個吧。

掌握排序算法可以幫助我們更好的理解計算機程序的執(zhí)行過程，訓(xùn)練我們的編程邏輯。而且排序算法有很多變形，這些變形在特定的應(yīng)用場景下會非常高效。
另外一個我覺得就是應(yīng)對職場的面試了。數(shù)據(jù)結(jié)構(gòu)和算法直接對應(yīng)了你能不能通過筆試，進入面試。我之前做過一個互聯(lián)網(wǎng)大廠的筆試，筆試就是 4 道編程題，時間一個半小時。我當(dāng)時一道題都沒 AC,心態(tài)直接爆炸，結(jié)果也就涼涼了。。。

冒泡排序

接下來，我們就來看一看冒泡排序算法，前面的動畫不知道你看懂了嗎？沒看懂的話可以再看一遍。

但是看懂就代表你可以寫出完整的代碼來嗎？答案并不一定哦。

話不多說，先看下代碼：

#!/usr/bin/python
#?-*-?coding:UTF-8?-*-
from?typing?import?List

#?Bubble?Sort
def?bubble_sort(array:?List[int])?->?None:
??for?i?in?range(len(array)?-?1):
????flag?=?False
????#?如果前面的比后面的元素大，就交換
????for?j?in?range(len(array)?-?1?-?i):
??????if?array[j]?>?array[j?+?1]:
????????array[j],?array[j?+?1]?=?array[j?+?1],?array[j]
????????flag?=?True
????#?如果一輪完成，沒有一個元素進行交換，則表明元素有序，退出循環(huán)
????if?not?flag:
??????break

array?=?[3,?44,?38,?5,?47,?15]
print(array)
bubble_sort(array)
print(array)??

冒泡排序的思想就是比較相鄰之間的元素，如果?array[j] < array[j + 1],則就會互換相鄰之間的元素。這樣每輪迭代完后，總有一個元素可以到達此元素應(yīng)該到達的位置。

每次到位的元素也就是第 K 大元素，舉例說，第一次到位的是第一大元素，也就是最大值。第二次到位的是第二大元素，也就是次大值。

如何評價一個排序算法？

通過上面的程序，我們就實現(xiàn)了冒泡排序算法，那么如何評價一個排序算法呢？我想這個你在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的時候一定都學(xué)過。

主要有以下指標：

時間復(fù)雜度
空間復(fù)雜度
穩(wěn)定性

這里我就不再一一敘述了，冒泡排序算法的時間復(fù)雜度是 O(n2)，空間復(fù)雜度是 O（1），是穩(wěn)定的排序算法。

優(yōu)化

時間復(fù)雜度是 O(n2) 的排序算法是比較耗時的，適用于小規(guī)模的數(shù)據(jù)，不適用于大規(guī)模的數(shù)據(jù)排序，那有沒有優(yōu)化的方法呢？

要想從時間復(fù)雜度的量級上優(yōu)化，這個就只能換排序算法了。但是呢？有一些其他的技巧，可以減少算法的運行時間。是什么呢？

就是在第奇數(shù)次迭代的時候，從前往后比較，而偶數(shù)次迭代的時候，從后往前比較。這樣雖然理論上還是 O(n2) 的時間復(fù)雜度，但是運行時間會降低不少。

#!/usr/bin/python
# -*- coding: UTF-8 -*-
import random
import time

# Bubble Sort
def bubble_sort(array):
  for i in range(len(array) - 1):
    flag = False
    for j in range(len(array) - 1 - i):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]
        flag = True
    if not flag:
      break

def optim_bubble_sort(array):
  for i in range(len(array) - 1):
    flag = False
    if i % 2:
      for j in range(len(array) - 1 - (i // 2), (i // 2), -1):
        if array[j] < array[j - 1]:
          array[j], array[j - 1] = array[j - 1], array[j]
          flag = True
    else:
      for j in range((i // 2), len(array) - 1 - (i // 2)):
        if array[j] > array[j + 1]:
          array[j], array[j + 1] = array[j + 1], array[j]
          flag = True
    if not flag:
      break


if __name__ == "__main__":
        num = 10000

        array = [random.randint(0,num) for _ in range (num)]
        array_copy = array[:]
        #print(array)
        start = time.perf_counter()
        bubble_sort(array)

        end = time.perf_counter()
        #print(array)
        print(end - start)
        start = time.perf_counter()
        optim_bubble_sort(array_copy)
        end = time.perf_counter()
        #print(array_copy)
        print(end - start)