《常用算法排序》課件

常用算法排序排序算法概述冒泡排序選擇排序插入排序快速排序歸并排序目錄01排序算法概述排序是指將一組數(shù)據(jù)按照一定的順序排列，以便進(jìn)行查找、檢索等操作。排序的定義排序的順序可以是升序或降序，升序是指從小到大排列，降序是指從大到小排列。排序的順序如果兩個(gè)元素相等，排序后它們的位置不會(huì)改變，則稱該排序算法是穩(wěn)定的。排序的穩(wěn)定性排序的定義按照比較方式01比較排序和非比較排序。比較排序是指通過元素之間的比較來確定位置，而非比較排序是指不通過元素之間的比較來確定位置。按照時(shí)間復(fù)雜度02線性時(shí)間復(fù)雜度排序和非線性時(shí)間復(fù)雜度排序。線性時(shí)間復(fù)雜度排序是指時(shí)間復(fù)雜度為O(n)，非線性時(shí)間復(fù)雜度排序是指時(shí)間復(fù)雜度大于O(n)。按照空間復(fù)雜度03原地排序和需要額外空間的排序。原地排序是指在原有數(shù)組上進(jìn)行排序，不需要額外空間；需要額外空間的排序是指需要開辟額外的存儲(chǔ)空間來存儲(chǔ)臨時(shí)數(shù)據(jù)。排序的分類01020304時(shí)間復(fù)雜度衡量算法執(zhí)行效率的重要指標(biāo)，表示算法執(zhí)行所需的時(shí)間與數(shù)據(jù)量之間的關(guān)系?？臻g復(fù)雜度衡量算法所需額外空間的重要指標(biāo)，表示算法執(zhí)行過程中所需額外空間的大小。穩(wěn)定性衡量算法在處理相等元素時(shí)是否保持原有順序的重要指標(biāo)?？勺x性衡量算法可理解性和可維護(hù)性的重要指標(biāo)，良好的可讀性可以提高代碼的可讀性和可維護(hù)性。排序算法的性能指標(biāo)02冒泡排序冒泡排序的基本思想是通過相鄰元素之間的比較和交換，使得每一輪循環(huán)都能將當(dāng)前未排序部分中最大的元素“冒泡”到未排序部分的末尾。具體來說，從第一個(gè)元素開始，依次比較相鄰的兩個(gè)元素，如果前一個(gè)元素比后一個(gè)元素大，則交換它們的位置。這樣一輪循環(huán)下來，最大的元素就會(huì)被“冒泡”到未排序部分的末尾。冒泡排序的基本思想冒泡排序的算法實(shí)現(xiàn)通常使用一個(gè)循環(huán)結(jié)構(gòu)，循環(huán)遍歷未排序部分的所有元素，依次比較相鄰的兩個(gè)元素并進(jìn)行交換。具體的算法實(shí)現(xiàn)可以描述為：對于未排序部分中的每一個(gè)元素，如果它比它后面的元素大，則交換它們的位置。這樣一輪循環(huán)下來，最大的元素就會(huì)被“冒泡”到未排序部分的末尾。重復(fù)這個(gè)過程，直到整個(gè)數(shù)組都排好序?yàn)橹?。冒泡排序的算法?shí)現(xiàn)冒泡排序的時(shí)間復(fù)雜度與空間復(fù)雜度冒泡排序的時(shí)間復(fù)雜度是O(n^2)，其中n是數(shù)組的長度。這是因?yàn)槊芭菖判蛐枰闅v整個(gè)數(shù)組多次，每次遍歷都需要進(jìn)行n次比較和交換操作。冒泡排序的空間復(fù)雜度是O(1)，因?yàn)槊芭菖判蛑恍枰?shù)級別的額外空間來存儲(chǔ)循環(huán)變量等控制結(jié)構(gòu)，不需要額外的存儲(chǔ)空間來存儲(chǔ)數(shù)據(jù)元素。03選擇排序選擇排序的基本思想是在未排序的序列中找到最?。ɑ蜃畲螅┑脑?，存放到排序序列的起始位置。然后再從剩余未排序的元素中繼續(xù)尋找最小（或最大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。010203選擇排序的基本思想找到未排序部分的最小（或最大）元素，存放到排序序列的起始位置。第一步第二步第三步再從剩余未排序的元素中繼續(xù)尋找最?。ɑ蜃畲螅┰兀缓蠓诺揭雅判蛐蛄械哪┪病Ｖ貜?fù)第二步，直到所有元素均排序完畢。030201選擇排序的算法實(shí)現(xiàn)時(shí)間復(fù)雜度選擇排序的時(shí)間復(fù)雜度為O(n^2)，其中n為待排序元素的數(shù)量。因?yàn)檫x擇排序需要多次遍歷待排序序列，并在每次遍歷中執(zhí)行n次比較操作?？臻g復(fù)雜度選擇排序的空間復(fù)雜度為O(1)，因?yàn)檫x擇排序只需要常數(shù)級別的輔助空間，不需要額外的存儲(chǔ)空間。選擇排序的時(shí)間復(fù)雜度與空間復(fù)雜度04插入排序插入排序的基本思想是將數(shù)組分為已排序和未排序兩部分，初始時(shí)已排序部分包含一個(gè)元素，然后從未排序部分取出元素，并在已排序部分找到合適的插入位置插入，并保持已排序部分一直有序，重復(fù)此過程，直到未排序部分元素為空。插入排序在每一步中都通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。插入排序的基本思想插入排序的算法實(shí)現(xiàn)通常采用迭代的方式進(jìn)行，即通過for循環(huán)從第二個(gè)元素開始遍歷數(shù)組，對于當(dāng)前元素，將其與已排序部分的元素逐個(gè)比較，找到合適的位置后插入。在具體實(shí)現(xiàn)上，可以采用in-place的插入排序算法，即通過交換元素的方式將已排序部分向后移動(dòng)，為新元素騰出空間。插入排序算法的時(shí)間復(fù)雜度為O(n^2)，其中n為數(shù)組的長度。插入排序的算法實(shí)現(xiàn)插入排序的時(shí)間復(fù)雜度與空間復(fù)雜度插入排序的時(shí)間復(fù)雜度為O(n^2)，其中n為數(shù)組的長度。這是因?yàn)樵谧顗那闆r下，需要比較n*(n-1)/2次才能完成排序。插入排序的空間復(fù)雜度為O(1)，因?yàn)橹恍枰玫匠?shù)級別的額外空間。05快速排序快速排序的基本思想將數(shù)組分為兩個(gè)子數(shù)組，分別對子數(shù)組進(jìn)行排序，然后合并已排序的子數(shù)組。遞歸快速排序是一個(gè)遞歸算法，每次遞歸都將數(shù)組分為更小的子數(shù)組，直到子數(shù)組的大小為1或0。隨機(jī)化為了減少最壞情況下的時(shí)間復(fù)雜度，可以使用隨機(jī)化選擇一個(gè)基準(zhǔn)元素。分治法選擇一個(gè)基準(zhǔn)元素，將數(shù)組分為兩個(gè)子數(shù)組，一個(gè)子數(shù)組的所有元素都小于基準(zhǔn)元素，另一個(gè)子數(shù)組的所有元素都大于基準(zhǔn)元素。選擇基準(zhǔn)元素對兩個(gè)子數(shù)組遞歸地執(zhí)行快速排序。遞歸排序子數(shù)組將兩個(gè)已排序的子數(shù)組合并成一個(gè)已排序的數(shù)組。合并已排序的子數(shù)組快速排序的算法實(shí)現(xiàn)時(shí)間復(fù)雜度平均情況下，快速排序的時(shí)間復(fù)雜度為O(nlogn)。在最壞情況下，時(shí)間復(fù)雜度為O(n^2)。空間復(fù)雜度快速排序是一個(gè)原地排序算法，不需要額外的存儲(chǔ)空間，空間復(fù)雜度為O(logn)?？焖倥判虻臅r(shí)間復(fù)雜度與空間復(fù)雜度06歸并排序歸并排序是一種分治算法，它將一個(gè)無序數(shù)組分割成兩個(gè)較小的子數(shù)組，分別對子數(shù)組進(jìn)行排序，然后將有序的子數(shù)組合并成一個(gè)完整的排序數(shù)組?；舅枷胧菍栴}分解為若干個(gè)較小的子問題，遞歸地解決這些子問題，然后將解決子問題的結(jié)果合并為解決原問題的結(jié)果。歸并排序的基本思想123算法步驟1.將數(shù)組分割成兩個(gè)子數(shù)組，直到子數(shù)組的大小為1。2.對每個(gè)子數(shù)組遞歸地應(yīng)用歸并排序。歸并排序的算法實(shí)現(xiàn)將已排序的子數(shù)組合并成一個(gè)完整的排序數(shù)組。歸并排序的算法實(shí)現(xiàn)歸并排序的算法實(shí)現(xiàn)01具體實(shí)現(xiàn)021.定義函數(shù)merge_sort(arr)，輸入一個(gè)無序數(shù)組arr。2.如果arr的大小小于2，直接返回arr。033.將arr分割成兩個(gè)子數(shù)組left和right，大小分別為arr[0,mid]和arr[mid+1,n-1]，其中mid是arr的中間索引。4.遞歸調(diào)用merge_sort(left)和merge_sort(right)，分別對兩個(gè)子數(shù)組進(jìn)行排序。5.定義函數(shù)merge(left,right)，輸入兩個(gè)已排序的子數(shù)組left和right。歸并排序的算法實(shí)現(xiàn)6.合并left和right為一個(gè)完整的排序數(shù)組result。7.在merge_sort函數(shù)中調(diào)用merge(left,right)，將已排序的子數(shù)組合并為一個(gè)完整的排序數(shù)組。歸并排序的算法實(shí)現(xiàn)VS歸并排序的時(shí)間復(fù)雜度為O(nlogn)，其中n是數(shù)組的大小。這是因?yàn)樵谧顗牡那?/p>