数据结构快速排序算法
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
現
是相當不錯的。
快速排序法的基本精神是在數列中找出適當的軸心，然後將數列一分為二，分別對
左邊與右邊數列進行排序，而影響快速排序法效率的正是軸心的選擇。
【第一种快速排序算法】--- 值固定...每次以最左边的元素为轴心
1. 令索引 i 從數列左方往右方找，直到找到大於 s 的數
2. 令索引 j 從數列右方往左方找，直到找到小於 s 的數
3. 如果 i >= j，則離開迴圈
4. 如果 i < j，則交換索引i與j兩處的值
5. 將左側的軸與 j 進行交換
6. 對軸左邊進行遞迴
7. 對軸右邊進行遞迴
透過以下演算法，則軸左邊的值都會小於s，軸右邊的值都會大於s，如此再對軸
左右兩邊進行遞迴，就可以對完成排序的目的，
例如下面的實例，*表示要交換的數，[]表示軸:
[41] 24 76* 11 45 64 21 69 19 36*
[41] 24 36 11 45* 64 21 69 19* 76
[41] 24 36 11 19 64* 21* 69 45 76
[41] 24 36 11 19 21 64 69 45 76
21 24 36 11 19 [41] 64 69 45 76
*/
function swap(&$array,$i,$j)
{
global $n;
$temp=$array[$i];
$array[$i]=$array[$j];
$array[$j]=$temp;
$n++;
}
/**
*
* 第一种快速排序算法--- 值固定...每次以最左边的元素为轴心
* @param Array $array
* @param int $left
* @param int $right
*/
function quickSort1(&$array,$left,$right)
{
if($left<$right)
{
$i=$left;
$j=$right+1;
while(true)
{
while($i+1
-1 && $array[--$j] > $array[$left]);
if($i>=$j) break;
swap($array,$i,$j);
}
print_r($array);
echo '
';
swap($array,$left,$j);//定位比较完的轴心值 交换后重新选择一个轴心值
//echo "
{$i}->{$j}
";//查看 每次结束时候的 $i $j
quickSort1($array,$left,$j-1);//重点->交换点 $left--($j-1)
quickSort1($array,$j+1,$right);//重点-> 交换点 $left--($j+1)
}
}
$n=0;
$array = array(41,24,76,11,45,64,21,69,19,36);
//print_r($array);
quickSort1($array,0,count($array)-1);
//echo '
移动了'.$n.'次
';
//print_r($array);
?>
浙公网安备 33021202002483