返回首页 - Notes - 2014

快速排序


算法描述

一对人有高有矮,随机站队

现在叫队列最右边的人站出来,命名为 A,然后剩下的人中,凡是比 A 矮的人全部站到 A 的左边,凡是比 A 高的人全部站到 A 的右边

然后 A 左边的那些人单独重复上一步骤,A 右边的人也单独重复上一步骤,A 不需要再管

如此反复,直到所有的人都 不需要再管,这样该队列就是按从矮到高排列了


算法实现

PHP

<?php

// 快排
function quick_sort ($arr) {
    if ($item = array_pop($arr)) {
        $leftArray  = array();
        $rightArray = array();

        foreach ($arr as $val) {
            if ($val <= $item) {
                array_push($leftArray, $val);
            } else {
                array_push($rightArray, $val);
            }
        }

        return array_merge(quick_sort($leftArray), array($item), quick_sort($rightArray));
    }

    return array();
}


// 打印数组
function print_arr ($arr) {
    echo '[';
    for ($i = 0; $i < count($arr) - 1; ++$i) {
        echo $arr[$i].' ';
    }
    echo $arr[count($arr) - 1];
    echo ']';
}


// 生成随机数组
$arr = range(1, 10);
shuffle($arr);


// 测试
print_arr($arr);
echo "\n";
print_arr(quick_sort($arr));
echo "\n";

Ruby

# 快排
def quick_sort (arr)
  if item = arr.pop
    quick_sort(arr.select { |i| i <= item }) + [item] + quick_sort(arr.select { |i| i > item })
  else
    []
  end
end


# 生成随机数组
arr = (1..10).to_a.shuffle


# 测试
p arr
p quick_sort arr

CoffeeScript

# 快排
quick_sort = (arr) ->
  if item = arr.pop()
    leftArray  = []
    rightArray = []

    for val in arr
      if val <= item then leftArray.push val else rightArray.push val

    quick_sort(leftArray).concat([item], quick_sort(rightArray))
  else []


# 生成随机数组
rand_array = (arr) ->
  arr.sort ->
    Math.random() - 0.5
  arr

arr = rand_array [1..10]


# 测试
console.log arr
console.log quick_sort arr

JavaScript

// 快排
function quick_sort (arr) {
    var item = arr.pop();
    if (item) {
        var leftArray  = [];
        var rightArray = [];

        for (var i = 0; i < arr.length; ++i) {
            if (arr[i] <= item) {
                leftArray.push(arr[i]);
            } else {
                rightArray.push(arr[i]);
            }
        }

        return quick_sort(leftArray).concat([item], quick_sort(rightArray));
    }

    return [];
}


// 生成随机数组
function rand_array(arr) {
    arr.sort(function () {
        return Math.random() - 0.5;
    });
    return arr;
}

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
arr = rand_array(arr);


// 测试
console.log(arr);
console.log(quick_sort(arr));

date : 2014-04-09、2014-06-24、2014-11-21