fofo

理解快速排序

2017-07-27

在一堆基础算法里面,快排不算难的,虽然平时也基本没用到,但却是经常被考察的玩意,没有理解就很痛苦,理解了之后就觉得很容易。先用PHP写,后面还会附上Java与JavaScript版本的。
首先,来张经典的动图:
fast-sort
慢动作可以看:在线动画演示各种排序算法过程 - aTool在线工具

这慢动作看得是真的爽,这还有什么是不能理解呢?快速排序是一种交换类排序,大一学C语言时候学的冒泡也是交换类排序,还记得怎么写么?

//先生成一个乱序的数组
$arr = range(0, 30);
shuffle($arr);
echo implode(' ', bubbleSort($arr));
function bubbleSort($integerArray) {
$num = sizeof($integerArray);
for ($i=0; $i < $num - 1 ; $i++) {
for ($j=0; $j < $num - $i -1; $j++) {
if ($integerArray[$j] > $integerArray[$j + 1]) {
$Temp = $integerArray[$j + 1];
$integerArray[$j + 1] = $integerArray[$j];
$integerArray[$j] = $Temp;
}
}
}
return $integerArray;
}
//result
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
30

冒泡是挺简单的,就是比较一趟趟比较,最坏的情况下时间复杂度是n的平方。快排则是在冒泡上改进的,将一趟排序的结果分两部分,一边的所有数据比另一边都要小,然后再对两个区域进行快排,其实就是递归

//同样,先生成一个乱序的数组,打印出来
$arr = range(0, 30);
shuffle($arr);
echo implode(" ", $arr);
//result
7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5
27

暂时拿这个当需要排序的数组:

//先生成一个乱序的数组
// $arr = range(0, 30);
// shuffle($arr);
$arr = explode(
" ",
"7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5 27");
function QuickSort($integerArray) {
}
function QuickSortCore($integerArray, $start, $end) {
$Temp = $integerArray[$start];
while ($start < $end){
while ($integerArray[$end] >= $Temp) {
$end--;
}
$integerArray[$start] = $integerArray[$end];
while ($integerArray[$start] <= $Temp && $start < $end) {
$start++;
}
$integerArray[$end] = $integerArray[$start];
}
$integerArray[$start] = $Temp;
return $integerArray;
}
echo
"7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5 27",
"\n";
echo implode(" ", QuickSortCore($arr, 0, sizeof($arr) -1));

这个就是快排的核心,首先要把start拿出来,挖个坑出来,然后拿跟end比较,把数组右侧比较小的数给弄到左边来,把数组左侧比较大的数弄右边去。其实就是个双端操作的冒泡。然后就是递归:

//成一个乱序的数组
$arr = range(0, 30);
shuffle($arr);
function Sorts($integerArray) {
QuickSort($integerArray, 0, sizeof($integerArray) - 1);
return $integerArray;
}
function QuickSort(&$integerArray, $start, $end) {
//递归结束条件
if ($start >= $end) {
return ;
}
//分区域后的返回值
$middleIndex = QuickSortCore($integerArray, $start, $end);
//递归调用
QuickSort($integerArray, 0, $middleIndex -1);
QuickSort($integerArray, $middleIndex + 1, $end);
}
function QuickSortCore(&$integerArray, $start, $end) {
$Temp = $integerArray[$start];
while ($start < $end){
while ($integerArray[$end] >= $Temp && $start < $end) {
$end--;
}
$integerArray[$start] = $integerArray[$end];
while ($integerArray[$start] <= $Temp && $start < $end) {
$start++;
}
$integerArray[$end] = $integerArray[$start];
}
$integerArray[$start] = $Temp;
return $start;
}
echo implode(" ", $arr), "\n";
echo implode(" ", Sorts($arr));

实际上当随机数比较大的时候,PHP会很慢,倒不如用PHP自带的sort()方法,这里只是学习一下快排的思想。Java和Js是一个道理,只是语法不同而已。

public static class QuickSort{
public static int[] subQuickSort(int[] array){
QuickSortCore(array, 0, array.length - 1);
return array;
}
private static void QuickSortCore(int[] array, int start, int end){
if (start >= end) {
return ;
}
int middleIndex = QuickSortCoreDetial(array, start, end);
QuickSortCore(array, start, middleIndex - 1);
QuickSortCore(array, middleIndex + 1, end);
}
private static int QuickSortCoreDetial(int[] array, int start, int end){
int middleValue = array[start];
while (start < end) {
while (array[end] >= middleValue && start < end) {
end--;
}
array[start] = array[end];
while (array[start] <= middleValue && start < end ) {
start++;
}
array[end] = array[start];
}
array[start] = middleValue;
return start;
}
}

function QuickSort(arr) {
function Sorts(arr) {
QuickSort(arr, 0, arr.length - 1);
return arr
}
function QuickSort(arr, start, end) {
if (start >= end) {
return ;
}
var middleIndex = QuickSortCore(arr, start, end);
QuickSort(arr, 0, middleIndex -1);
QuickSort(arr, middleIndex + 1, end);
}
function QuickSortCore(arr, start, end) {
var Temp = arr[start];
while (start < end){
while (arr[end] >= Temp && start < end) {
end--;
}
arr[start] = arr[end];
while (arr[start] <= Temp && start < end) {
start++;
}
arr[end] = arr[start];
}
arr[start] = Temp;
return start;
}
return Sorts(arr);
}
Tags: 算法
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章