【数据结构】交换排序

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数

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注