資源簡(jiǎn)介

(共27張PPT)
第2課 排序算法
目錄
01
問題背景與挑戰(zhàn)
02
選擇排序基本原理
03
算法步驟拆解
04
編程實(shí)現(xiàn)與優(yōu)化
05
應(yīng)用場(chǎng)景與擴(kuò)展思考
問題背景與挑戰(zhàn)
PART ONE
智力運(yùn)動(dòng)會(huì)排序任務(wù)
目標(biāo)是通過合理的方法，利用天平完成10個(gè)蘋果的質(zhì)量排序，重點(diǎn)在于找到高效的排序方式，以最短時(shí)間達(dá)成排序要求。
任務(wù)目標(biāo)
此任務(wù)看似簡(jiǎn)單，但要高效完成并非易事，這就引出了對(duì)算法設(shè)計(jì)的需求，需要借助合適的算法來減少比較次數(shù)，提高排序效率。
引出算法需求
小睿的學(xué)校舉行智力運(yùn)動(dòng)會(huì)，其中一項(xiàng)挑戰(zhàn)是對(duì)10個(gè)大小相似但質(zhì)量不同的蘋果排序。參賽者借助天平，要將它們按質(zhì)量由小到大排列，用時(shí)最少且方法最佳者獲勝。
任務(wù)背景
01、
02、
03、
排序的本質(zhì)與核心問題
排序的本質(zhì)
排序的本質(zhì)是一個(gè)不斷比較每?jī)蓚€(gè)蘋果質(zhì)量的過程。在這個(gè)過程中，通過比較確定元素之間的大小關(guān)系，進(jìn)而對(duì)元素的位置進(jìn)行調(diào)整。
01
02
元素比較
在對(duì)蘋果排序時(shí)，需要將每個(gè)蘋果與其他蘋果進(jìn)行比較，判斷其質(zhì)量大小，這是確定蘋果最終順序的基礎(chǔ)操作。
03
位置交換
當(dāng)比較出兩個(gè)蘋果質(zhì)量的大小關(guān)系后，如果順序不符合要求，就需要交換它們的位置，以此逐步構(gòu)建出有序序列。
手動(dòng)排序的局限性
在對(duì)10個(gè)蘋果進(jìn)行手動(dòng)排序時(shí)，隨著蘋果數(shù)量的增加，比較和交換的次數(shù)會(huì)急劇上升。例如，每增加一個(gè)蘋果，比較次數(shù)就會(huì)大幅增加，導(dǎo)致排序效率低下。
效率瓶頸體現(xiàn)
01
若蘋果數(shù)量從10個(gè)擴(kuò)展到100個(gè)甚至更多，人工操作的難度和時(shí)間成本將難以承受。人工排序不僅容易出錯(cuò)，而且效率極低，無法滿足大規(guī)模數(shù)據(jù)的排序需求。
規(guī)模擴(kuò)展挑戰(zhàn)
02
面對(duì)大規(guī)模數(shù)據(jù)的排序任務(wù)，手動(dòng)排序的局限性凸顯，這就迫切需要自動(dòng)化的排序算法來提高效率和準(zhǔn)確性，以應(yīng)對(duì)不斷增長(zhǎng)的數(shù)據(jù)規(guī)模挑戰(zhàn)。
對(duì)自動(dòng)化的需求
03
選擇排序基本原理
PART TWO
算法核心思想
每一輪排序都是在前一輪的基礎(chǔ)上進(jìn)行，不斷縮小未排序數(shù)據(jù)的范圍。隨著輪次的推進(jìn)，已排序序列逐漸增長(zhǎng)，未排序序列逐漸縮短，最終實(shí)現(xiàn)整個(gè)序列的有序排列。例如在對(duì)10個(gè)蘋果排序時(shí)，第一輪找出最輕的蘋果放在首位，第二輪在剩余9個(gè)蘋果中找出第二輕的放在第二位，依此類推。
遞進(jìn)式排序邏輯
選擇排序采用分層構(gòu)建的方式來生成有序序列。從序列的起始位置開始，逐步將未排序數(shù)據(jù)中的最小元素挑選出來，放置到已排序序列的末尾，一層一層地構(gòu)建出完整的有序序列。
分層構(gòu)建有序序列
雙循環(huán)結(jié)構(gòu)解析
選擇排序中的外層循環(huán)用于控制排序的輪次。以對(duì)n個(gè)元素進(jìn)行排序?yàn)槔鈱友h(huán)會(huì)執(zhí)行n - 1次。每一輪循環(huán)都對(duì)應(yīng)著確定一個(gè)位置的元素，使其成為有序序列的一部分。比如對(duì)10個(gè)蘋果排序，外層循環(huán)就會(huì)執(zhí)行9次，依次確定從最輕到第九輕的蘋果位置。
外層循環(huán)控制輪次
1
內(nèi)層循環(huán)的主要作用是在每一輪中查找未排序數(shù)據(jù)中的最小元素。在內(nèi)層循環(huán)中，會(huì)將當(dāng)前輪次起始位置的元素與未排序部分的其他元素逐個(gè)進(jìn)行比較。如果發(fā)現(xiàn)有比當(dāng)前元素更小的元素，就記錄下該元素的位置，循環(huán)結(jié)束后，就能確定這一輪中的最小元素。
內(nèi)層循環(huán)執(zhí)行極值查找
2
算法特征總結(jié)
選擇排序是一種原地排序算法，這意味著在排序過程中，除了輸入的數(shù)組本身，不需要額外的大量存儲(chǔ)空間來完成排序操作。它只需要幾個(gè)額外的變量來輔助記錄數(shù)據(jù)的位置和進(jìn)行比較交換等操作，在空間復(fù)雜度上具有一定優(yōu)勢(shì)。
選擇排序是不穩(wěn)定的排序算法。在排序過程中，相等元素的相對(duì)順序可能會(huì)被改變。例如，假設(shè)有序列 [5a, 3, 5b]，在選擇排序時(shí)，可能會(huì)將5a與3交換位置，導(dǎo)致原本在5a后面的5b跑到了5a前面，改變了相等元素5a和5b的相對(duì)順序。
原地排序特征
不穩(wěn)定性特征說明
算法步驟拆解
PART THREE
首輪極值定位
首輪要找出10個(gè)蘋果中質(zhì)量最輕的，在第一步比較出質(zhì)量輕的蘋果后，需用這個(gè)蘋果分別與2 - 9號(hào)蘋果進(jìn)行比較。如果該蘋果比其他蘋果重就交換，輕則不交換，通過這n - 1（這里n = 10，即9次）次比較，就能找出質(zhì)量最輕的蘋果，并把它放到首位。
全面比較找最小
在選擇排序中，首輪極值定位從序列頭部開始。例如對(duì)10個(gè)蘋果排序，首先使用天平比較0號(hào)和1號(hào)位置的蘋果。若0號(hào)位置的蘋果重，則交換兩個(gè)蘋果的位置，否則不交換。
比較的起始步驟
次優(yōu)元素遞進(jìn)選擇
在找出最輕的蘋果并放置到首位后，次優(yōu)元素的選擇范圍縮小到剩余的蘋果。比如第二輪，用1號(hào)位置的蘋果，重復(fù)第一輪的步驟，在剩余9個(gè)蘋果中選出第二輕的蘋果。
縮小范圍選次優(yōu)
01
每一輪都在不斷縮小的未排序序列中選擇當(dāng)前輪次的最小元素。隨著輪次推進(jìn)，已排序序列逐漸增長(zhǎng)，未排序序列逐漸縮短，通過這種遞進(jìn)方式完成所有元素的篩選。
遞進(jìn)選擇的過程
02
每輪選出的次優(yōu)元素，會(huì)放置到已排序序列的末尾，也就是當(dāng)前輪次對(duì)應(yīng)的位置。如第二輪選出的第二輕的蘋果放置在1號(hào)位置。
確定位置放置元素
03
比較次數(shù)數(shù)學(xué)建模
根據(jù)等差數(shù)列求和公式 (S_n = frac{n(a_1 + a_n)}{2})（其中n為項(xiàng)數(shù)，(a_1)為首項(xiàng)，(a_n)為末項(xiàng)），這里項(xiàng)數(shù)為n - 1，首項(xiàng)為n - 1，末項(xiàng)為1。將其代入公式可得總比較次數(shù) (S = frac{(n - 1)(n - 1 + 1)}{2} = frac{n(n - 1)}{2})。
在選擇排序中，每一輪比較的次數(shù)構(gòu)成一個(gè)等差數(shù)列。第一輪比較n - 1次（n為元素總數(shù)），第二輪比較n - 2次，以此類推，最后一輪比較1次。例如對(duì)10個(gè)蘋果排序，第一輪比較9次，第二輪比較8次……第九輪比較1次。
求和公式推導(dǎo)
等差數(shù)列的形成
比較次數(shù)數(shù)學(xué)建模
以10個(gè)蘋果為例，將n = 10代入公式，總比較次數(shù)為 (frac{10times(10 - 1)}{2} = 45) 次，這就是通過數(shù)學(xué)建模得出的選擇排序?qū)?0個(gè)元素進(jìn)行排序的總操作量。
總操作量計(jì)算示例
時(shí)間復(fù)雜度分析
選擇排序的時(shí)間復(fù)雜度為O(n )，這意味著算法執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模n的平方成正比。當(dāng)數(shù)據(jù)規(guī)模n增大時(shí)，算法執(zhí)行時(shí)間會(huì)急劇增長(zhǎng)。
O(n )的含義
01
通過繪制算法效率曲線可以直觀看到，隨著數(shù)據(jù)規(guī)模n的增加，O(n )曲線上升趨勢(shì)明顯。與其他更高效的排序算法（如O(n log n)的快速排序）相比，選擇排序在處理大規(guī)模數(shù)據(jù)時(shí)效率較低。
效率曲線圖示說明
02
由于時(shí)間復(fù)雜度為O(n )，選擇排序適用于小數(shù)據(jù)量的排序任務(wù)。在數(shù)據(jù)量較小的情況下，其簡(jiǎn)單直觀的特點(diǎn)使其易于實(shí)現(xiàn)和調(diào)試，但對(duì)于大規(guī)模數(shù)據(jù)排序則不太適用。
對(duì)算法應(yīng)用的影響
03
編程實(shí)現(xiàn)與優(yōu)化
PART FOUR
數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)
在數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)中，數(shù)組是常用的選擇。例如在對(duì)蘋果質(zhì)量排序任務(wù)里，可使用數(shù)組來存儲(chǔ)每個(gè)蘋果的質(zhì)量數(shù)據(jù)。數(shù)組具有連續(xù)存儲(chǔ)的特點(diǎn)，能方便地通過索引訪問元素，為后續(xù)的排序操作提供基礎(chǔ)。
數(shù)組的選擇
索引操作在整個(gè)排序過程中至關(guān)重要。通過索引，我們可以準(zhǔn)確地定位數(shù)組中的元素，進(jìn)而進(jìn)行比較和交換等操作。比如在選擇排序中，利用索引可以快速找到未排序部分的元素，并與已排序部分進(jìn)行關(guān)聯(lián)操作。
索引操作的意義
數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)
實(shí)現(xiàn)數(shù)組與索引操作的方案需要綜合考量。要根據(jù)數(shù)據(jù)量大小、操作的復(fù)雜度等因素來設(shè)計(jì)。對(duì)于小數(shù)據(jù)量的蘋果質(zhì)量排序，簡(jiǎn)單的一維數(shù)組和基本的索引操作就能滿足需求，但對(duì)于大數(shù)據(jù)量，可能需要更復(fù)雜的結(jié)構(gòu)和算法。
實(shí)現(xiàn)方案的考量
極值索引追蹤策略
在每一輪排序中，從數(shù)組的特定位置開始遍歷，將第一個(gè)元素的索引設(shè)為臨時(shí)變量初始值。然后依次與后續(xù)元素比較，若遇到更小的元素，就更新臨時(shí)變量為該元素的索引，以此準(zhǔn)確記錄最小元素位置。
在極值索引追蹤策略里，臨時(shí)變量發(fā)揮著關(guān)鍵作用。以選擇排序找最小元素為例，通過設(shè)置臨時(shí)變量，可以在遍歷數(shù)組時(shí)記錄當(dāng)前找到的最小元素的索引位置，方便后續(xù)操作。
記錄最小元素位置的過程
臨時(shí)變量的作用
極值索引追蹤策略
這種通過臨時(shí)變量記錄最小元素位置的策略，使得排序過程更加有序和高效。它避免了每次比較都進(jìn)行復(fù)雜的操作，只需在遍歷結(jié)束后，根據(jù)臨時(shí)變量記錄的索引進(jìn)行相應(yīng)處理，提高了排序效率。
策略的優(yōu)勢(shì)
交換操作優(yōu)化技巧
采用這些減少冗余交換操作的實(shí)現(xiàn)方法，能顯著提升排序算法的性能。特別是在數(shù)據(jù)量較大時(shí)，減少的冗余操作能大幅降低計(jì)算時(shí)間，提高程序運(yùn)行效率。
實(shí)現(xiàn)方法的效果
為減少冗余交換操作，可在比較時(shí)增加判斷條件。比如在確定最小元素索引后，先判斷該索引是否就是當(dāng)前需要交換的位置，如果是則無需交換，直接進(jìn)入下一輪排序，從而節(jié)省計(jì)算資源。
減少冗余的方法
在排序過程中，需要識(shí)別冗余交換操作。例如在選擇排序時(shí)，如果當(dāng)前比較的元素已經(jīng)是最小的，卻仍然進(jìn)行不必要的交換，這就是冗余操作。通過分析比較條件，可以發(fā)現(xiàn)這類無意義的交換。
冗余交換操作的識(shí)別
應(yīng)用場(chǎng)景與擴(kuò)展思考
PART FIVE
小數(shù)據(jù)量場(chǎng)景優(yōu)勢(shì)
對(duì)于小數(shù)據(jù)量排序需求，選擇排序簡(jiǎn)單直觀的特點(diǎn)使其易于實(shí)現(xiàn)和調(diào)試。像一些簡(jiǎn)單的小型系統(tǒng)，只需少量代碼就能完成排序功能，降低開發(fā)成本。
簡(jiǎn)單易實(shí)現(xiàn)
在某些智能家居設(shè)備中，如傳感器數(shù)據(jù)量較小且對(duì)排序要求不高時(shí)，選擇排序算法可快速對(duì)數(shù)據(jù)進(jìn)行排序處理，保障設(shè)備正常運(yùn)行。
典型應(yīng)用示例
在小數(shù)據(jù)量場(chǎng)景下，選擇排序算法占用計(jì)算機(jī)資源較少。例如在嵌入式設(shè)備中，其硬件資源相對(duì)有限，選擇排序算法不會(huì)給設(shè)備帶來過多負(fù)擔(dān)，能高效完成小數(shù)據(jù)量的排序任務(wù)。
資源占用少
01、
02、
03、
與其他算法的對(duì)比
時(shí)間復(fù)雜度方面，選擇排序和冒泡排序平均和最壞時(shí)間復(fù)雜度均為 (O(n^2))，但選擇排序交換次數(shù)更少。空間復(fù)雜度上，二者都為 (O(1))。
與冒泡排序?qū)Ρ?br/>插入排序在數(shù)據(jù)基本有序時(shí)時(shí)間復(fù)雜度為 (O(n))，而選擇排序始終為 (O(n^2))。空間復(fù)雜度上，插入排序同樣為 (O(1))，二者在空間占用上表現(xiàn)相當(dāng)。
與插入排序?qū)Ρ?br/>選擇排序在小數(shù)據(jù)量時(shí)優(yōu)勢(shì)明顯，但面對(duì)大數(shù)據(jù)量，冒泡排序和插入排序在特定情況下可能更具效率，開發(fā)者需根據(jù)實(shí)際情況選擇合適算法。
綜合對(duì)比結(jié)論
排序穩(wěn)定性改進(jìn)
在一些特定應(yīng)用場(chǎng)景中，排序穩(wěn)定性至關(guān)重要。例如在成績(jī)排名系統(tǒng)中，相同成績(jī)的學(xué)生順序應(yīng)保持不變，穩(wěn)定排序算法能滿足此類需求。
穩(wěn)定性的重要性
01
為改進(jìn)選擇排序的穩(wěn)定性，可通過記錄每個(gè)元素的原始位置。在排序過程中，當(dāng)遇到相等元素時(shí)，按照原始位置順序處理，從而實(shí)現(xiàn)穩(wěn)定排序。
記錄原始位置實(shí)現(xiàn)穩(wěn)定版本
02
改進(jìn)后的穩(wěn)定版本選擇排序，在需要保持相等元素相對(duì)順序的場(chǎng)景中能更好地發(fā)揮作用，拓寬了選擇排序算法的應(yīng)用范圍。
改進(jìn)后的效果與應(yīng)用
03
謝謝

展開更多......

收起↑