數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 7.3 交換排序

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)冒泡排序快速排序7.3交換排序在待排序序列中每次選取兩條記錄進(jìn)行比較，若這兩條記錄不滿足排序的要求，則交換位置，直到序列中所有記錄兩兩比較都滿足排序的要求為止。交換排序在每一趟排序中，都比較相鄰兩個(gè)數(shù)的大小。若需要按照由小到大的順序進(jìn)行排序，一旦逆序則交換它們的位置，每趟排序都會(huì)使當(dāng)前“最大”的數(shù)“沉到”序列末尾，小的數(shù)逐步“上升”。冒泡排序冒泡排序示例初始數(shù)據(jù)

45，37，63，91，26，13，58，2第1趟 37，45，63，26，13，58，2，91第2趟 37，45，26，13，58，2，63，91第3趟 37，26，13，45，2，58，63，91第4趟 26，13，37，2，45，58，63，91第5趟 13，26，2，37，45，58，63，91第6趟 13，2，26，37，45，58，63，91第7趟 2，13，26，37，45，58，63，91

冒泡排序算法分析快速排序在每一輪挑選一個(gè)基準(zhǔn)元素，并讓其他比它大的元素移動(dòng)到數(shù)列一邊，比它小的元素移動(dòng)到數(shù)列的另一邊，從而把數(shù)列拆解成了兩個(gè)部分。然后再按照此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列?？焖倥判蚧舅枷耄簭臄?shù)列中挑出一個(gè)元素（默認(rèn)序列第一個(gè)記錄），稱為"基準(zhǔn)"元素進(jìn)行排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。然后遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序?？焖倥判蚩焖倥判蚴纠跏紨?shù)據(jù) 45，37，63，91，26，13，58，2453763912613582第1趟[2，37，13，26]，45，[91，58，63]第2趟

2，[37，13，26]，45，[63，58]，91第3趟2，[26，13]，37，45，[58]，63，91第4趟2，[13]，26，37，45，58，63，91第1趟快速排序算法在分治法的思想下，原數(shù)列在每一輪被拆分成兩部分，每一部分在下一輪又分別被拆分成兩部分，直到不可再分為止，平均情況下需要log2n輪，因此快速排序算法的平均時(shí)間復(fù)雜度是O(nlog2n)在最壞情況下，快速排序算法每一輪只能確定基準(zhǔn)元素一個(gè)位置，時(shí)間復(fù)雜度為O(n