上一節課我們已經講了算法的基礎知識，這節課我們講一下算法中兩個最為經典的類型：排序算法和查找算法。排序和查找我們之前直接使用列表的内置方法，那實現排序和查找最底層的原理是什麼呢？我們正式開始這節課的内容吧。

　　一、排序算法1.1 冒泡排序 冒泡排序是最簡單的一種排序方法，它的原理是将一列數據中較大（或較小）的數據逐次向右推移的一種排序方法。冒泡排序分為内外兩層循環。外層是總共要跑的遍數，2個數據比較一遍，3個數據比較一遍，以此類推，n個數據就跑了n-1遍。内層循環真正比較數據。以升序為例，每次比較把較大的放到後面。由于每一遍都是将本遍最大的數據移動到最右邊。就像是水中的氣泡一樣，小的氣泡上升，就排到最上面，就像是“冒泡”一樣，所以我們稱它為冒泡排序。

　　下面我們以升序為例，講一下冒泡排序的基本思想：

　　第一遍從第1個元素開始，讓它和第2個元素進行比較，如果大數在前就交換；然後讓2個元素和第3個元素比較，大數在前就交換；依次類推，直到比較完最後一個元素為止。第一遍排序結束時，最後一個元素是所有元素中的最大值。

　　第二遍從第一個元素開始，讓它和第2個元素進行比較，如果大數在前就交換；然後讓2個元素和第3個元素比較，大數在前就交換；依次類推，直到比較到倒數第二個元素為止。第二遍排序結束時，倒數第二個數為第二大的數。

　　……

　　n個數排序共需要n-1遍。

　　我們看一下模拟的實例：

　　3 9 2 1 6 原始數據3 9 2 1 6 将3和9比較，不交換位置3 2 9 1 6 将9和2比較，交換位置3 2 1 9 6 将1和9比較，交換位置3 2 1 6 9 将9和6比較，交換位置。第一輪結束2 3 1 4 9 将3和2比較，交換位置2 1 3 4 9 将3和1比較，交換位置2 1 3 4 9 将3和4比較，不交換位置。第二輪結束……

　　下面我們看一下冒泡排序的Python代碼實現：

　　a = [3, 9, 2, 1, 6] count = len(a) for i in range(0, count - 1): # 外層循環 for j in range(0, count -1 - i): # 内層循環 if a[j] a[j 1]: a[j], a[j 1] = a[j 1], a[j] # 兩個數交換 print(a)

　　1.2 選擇排序 選擇排序對冒泡排序的改進。選擇排序是在參加排序的所有元素中找出數值最小或最大的元素，如果它不是左側第一個元素，就讓它和左側第一個元素交換位置；然後在餘下的元素中找出數值最小或最大的元素，如果它不是左側第二個元素，就與左側第二個元素交換位置；……依次類推，直到所有元素構成有序的序列。

　　比起冒泡排序，選擇排序更符合人們日常的排序習慣。它的比較次數與冒泡排序相通，但是交換的次數比冒泡排序要少，因此具有更高的效率。

　　下面我們以升序為例，講一下選擇排序的基本思想：

　　第一遍從第1個元素到第n個元素中找出一個最小的元素，如果它不是第1個元素，就讓它和第1個元素交換位置。第一遍排序結束時，第1個元素為所有元素中的最小值。

　　第二遍從第2個元素到第n個元素中找出一個最小的元素，如果它不是第2個元素，就讓它和第2個元素交換位置。第二遍排序結束時，第2個元素為所有元素中第二小的值。

　　……

　　下面我們看看如何實現最小元素的交換位置：

　　第i遍排序開始時，先假設第i個位置上的數是最小的數，用k标記。讓k位置上的數(a[k])與i後面的數(a[j])逐個比較，當找到一個比k位置上小的數，用k記錄j的值。當j到達最後一個數時，一遍比較結束，k指向最小的數，即k記錄最小的數的位置。當i≠k時，交換a[i]與a[k]的值。

　　我們看一下選擇排序的Python代碼實現：

　　a = [3, 9, 2, 1, 6] count = len(a) for i in range(0, count - 1): k = i for j in range(i 1, count): if a[k] a[j]: k = j if k != i: a[k], a[i] = a[i], a[k] print(a)

　　1.3 插入排序 插入排序是先将待排序的數列中的第1個元素看成一個有序的子數列，然後從第2個元素開始，将數據逐個插入這個有序的子數列中，以此類推到最後一個數據。整個排序的過程類似于玩撲克牌時一邊抓牌一遍理牌的過程，每抓一張牌就把它插入到應有的位置上。

　　插入排序的整個過程如下圖所示：

　　插入排序

　　第1次插入，将第2個元素與第1個元素比較。先将要插入到數a[1]放入一個空的變量key；将key與前面已經排好序的元素比較，如果keya[0]成立，說明key要插入到a[0]前面，将a[0]向後移動一個位置，放到a[1]中，再将key放到a[0]中；如果keya[0]不成立，說明key要插入到a[0]後面，放key放入到a[1]的位置中。

　　第2次插入，前面兩個元素已經排好序，将第3個元素放入一個空的變量key，将key與前面排好序的元素比較，再将它插入對應的位置中。

　　……

　　依次類推。

　　我們看一下插入排序的Python代碼實現：

　　a = [3, 9, 2, 1, 6] count = len(a) for i in range(1, count): key = a[i] j = i - 1 while j = 0 and a[j] key: a[j 1] = a[j] j -= 1 a[j 1] = key print(a)

　　1.4 其他排序算法 以上三種排序的算法外，還有歸并排序、快速排序、堆排序、計數排序、桶排序、希爾排序等等，快速排序的思想下節課我們會講解，歸并排序這裡就略去不講了，大家可以自己研究。别的排序算法相對較為複雜，目前階段不需要大家掌握。有興趣的同學可查閱相關資料。

　　相對好理解一些的是歸并排序（暫時不需要掌握代碼），大家可以看動畫的圖片做相應的理解：

　　歸并排序

　　二、查找算法2.1 順序查找 順序查找是一種最為常用的查找算法。我們生活中也經常會用到，比如我們要從一堆書裡面找到我們想要的書，我們會從第一本開始一本一本地看，直到找到我們想要的那本書。

　　順序查找的基本思想是從第一個元素開始，按順序逐個将數據與給定的數據進行比較，如果某個數據與給定的數據相等，則查找成功，輸出所查數據；反之則未找到。

　　順序查找的代碼使用Python實現也非常簡單：

　　data = [12, 23, 1, 89, 34, 13, 78, 67, 54] key = 34 # 要查找的元素 x = -1 # 要查找元素的索引 count = len(data) for i in range(0, count): if data[i] == key: x = i break if x == -1: # -1代表元素未找到 print(元素不存在) else: print(x)

　　2.2 對分查找 對分查找又稱二分查找，是一種高效的查找方法。對分查找的前提是被查找的序列是有序的。

　　我們思考一個問題，從1到100中随機一個數字，猜出這個數是多少。如果我們從1開始一個個往後猜，每次隻能排除一個數字，最壞的情況我們可能要猜100次。但是如果第一次猜50，告訴你大了或者小了。下次再猜25，再下次猜12，以此類推，不管是哪個數字，最多7次之内就能猜出來了。這樣比起順序查找要省了很多的時間。這就是對分查找算法。

　　我們看看對分查找的思路：

　　如果key是我們需要查找的值，列表a中存放了n個已經升序排列的元素，m為查找範圍[i, j]的中間位置。我們查找的過程中必然是以下三種情況之一：

　　如果key a[m]，key在前半部分，新的查找範圍在[i, m-1]中如果key = a[m]，找到需要對數據如果key a[m]，key在後半部分，新的查找範圍在[m 1, j]中 我們看一下對分查找的Python代碼實現：

　　data = [2, 34, 36, 47, 51, 53, 59, 62, 75, 79, 82] key = 47 # 需要查找的元素 count = len(data) i, j = 0, count - 1 x = -1 while i = j: m = (i j) // 2 if key == data[m]: x = m break elif key data[m]: i = m 1 else: j = m - 1 if x == -1: print(未找到元素) else: print(x)

　　三、課後思考題 1、選擇題

　　列表l = [9, 2, 8, 6, 3, 4]，采用選擇排序進行升序排序，第二遍排序之後的結果是（）

　　A. [2, 3, 8, 6, 9, 4]

　　B. [2, 8, 6, 3, 4, 9]

　　C. [2, 6, 3, 4, 8, 9]

　　D. [2, 3, 4, 6, 8, 9]

　　2、選擇題

　　列表l = [5, 2, 6, 3, 7]，利用插入排序進行升序排序，第二次插入排序的結果是（）

　　A. [5, 2, 3, 6, 7]

　　B. [2, 5, 3, 6, 7]

　　C. [2, 5, 6, 3, 7]

　　D. [2, 3, 5, 6, 7]

　　3、選擇題

　　某個列表中有7個元素，依次為19、28、30、35、39、42、48。如果采用對分查找法在列表中查找元素48，需要查找的次數是（）

　　A. 1 B. 2 C. 3 D. 4

　　四、上節課思考題答案 1、C

　　2、C

　　3、參考代碼

　　n = 0 # 統計個數 for i in range(100, 1000): a = i // 100 # 百位數 b = i % 100 // 10 # 十位數 c = i % 10 # 個位數 if a ** 3 b ** 3 c ** 3 == i: n = 1 print(i) print(合計個數：, n)

　　,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!