【數據結構】交換排序

2019-11-06 07:18:17

字體：大中小

來源：轉載

供稿：網友

交換排序的基本思想是：

兩兩比較待排序記錄的關鍵字，如果發生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。

冒泡排序

基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規則交換。

優點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發生，還可以提前結束排序。

前提：順序存儲結構

例：關鍵字序列 T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實現過程。

冒泡排序的算法分析

代碼示例

<?phpfunction bubble_sort($rand_arr){ $arr_count = count($rand_arr); for($i=0;$i<$arr_count;$i++){ //設置flag變量，用來記錄數據是否交換完成 $flag = true; for($j=0;$j<$arr_count-1;$j++){ if($rand_arr[$j] > $rand_arr[$j+1]){ //進行交換 $temp = $rand_arr[$j]; $rand_arr[$j] = $rand_arr[$j+1]; $rand_arr[$j+1] = $temp; $flag = false; } } if($flag){ break; } } return $rand_arr;}$arr = array(21,25,49,25,16,8);$arr = bubble_sort($arr);PRint_r($arr);

詳情【PHP】冒泡排序以及優化

快速排序

基本思想：從待排序列中任取一個元素 (例如取第一個) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規則調整，直到每個子表的元素只剩一個。此時便為有序序列了。

優點：因為每趟可以確定不止一個元素的位置，而且呈指數增加，所以特別快！

前提：順序存儲結構

例如：關鍵字序列 T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。（設以首元素為樞軸中心）

算法分析

這種不斷劃分子表的過程，計算機如何自動實現？

每一趟的子表的形成是采用從兩頭向中間交替式逼近法；由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。

代碼示例

<?phpfunction quick_sort($array) { if(count($array) <= 1) return $array; $key = $array[0];//選第一個元素為樞軸 $rightArray = array(); $leftArray = array(); for($i = 1; $i < count($array); $i++) { if($array[$i] >= $key) {//大的放右邊 $rightArray[] = $array[$i]; } else { $leftArray[] = $array[$i];//小的放左邊 } } $leftArray = quick_sort($leftArray);//遞歸調用左邊數組 $rightArray = quick_sort($rightArray);//遞歸調用排序右邊數組 return array_merge($leftArray, array($key), $rightArray);//合并}$arr = array(21,25,49,25,16,8);$arr = quick_sort($arr);print_r($arr);

上一篇：設計模式-（單例模式）

下一篇：1026: [SCOI2009]windy數