常用的比较高效的排序算法之快速排序

排序算法在数据结构那门课上了解过之后，就一直抛在脑后了。印象中比较深刻的就是冒泡算法了，因为名称比较形象。之前应用过冒泡算法，大概过程就是两层循环，前后两两比较，大的往后排，复杂度应该是 O（n*(n-1)）。

每次需要进行排序的时候，都是临时去找一下算法结构，然后套用一下。这次搜索突然找到了一篇介绍比较详细的文章 总结5种比较高效常用的排序算法 - cnblog，里面介绍的 5 种算法听着都很耳熟，但肯定没有实现过。这次尝试了最后一种冒泡算法的进阶算法 —— 快速排序算法，里面用到了二分法和递归。

以下是作者的 Java 版实现的快速排序：

public class QuickSort {
    public int partition(int[] sortArray, int low, int height) {
        int key = sortArray[low];// 刚开始以第一个数为标志数据
        while (low < height) {
            while (low < height && sortArray[height] >= key)
                height--;// 从后面开始找，找到比key值小的数为止
            sortArray[low] = sortArray[height];// 将该数放到key值的左边
            while (low < height && sortArray[low] <= key)
                low++;// 从前面开始找，找到比key值大的数为止
            sortArray[height] = sortArray[low];// 将该数放到key值的右边
        }
        sortArray[low] = key;// 把key值填充到low位置，下次重新找key值
        // 打印每次排序结果
        for (int i = 0; i <= sortArray.length - 1; i++) {
            System.out.print(sortArray[i] + "\t");
        }
        System.out.println();
        return low;
    }
  
    public void sort(int[] sortArray, int low, int height) {
        if (low < height) {
            int result = partition(sortArray, low, height);
            sort(sortArray, low, result - 1);
            sort(sortArray, result + 1, height);
        }
    }
  
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] array = { 5, 69, 12, 3, 56, 789, 2, 5648, 23 };
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        quickSort.sort(array, 0, 8);
        for (int i = 0; i <= array.length - 1; i++) {
            System.out.print(array[i] + "\t");
        }
    }
}

晚上试一下看看效果，因为不确定 array 值传递到方法中做排序，对于 sortArray 的修改能否反映到原始数组 array 上。原谅我这个半吊子 Java 程序员，对于形参、实参的概念还停留在 C 语言上，在 C 和 PHP 中形参的修改是不会影响到实参的。为了使实参变化，C 中用了引用赋值或者指针，PHP 中没有指针，只有引用赋值。

解释一下，实参是主调函数在调用被调函数时，传递的变量；形参是被调用函数接受传递变量而定义的变量。

PHP 版的快速算法实现：

private function summary2_partition(&$arr, $low, $high)
{
    $key = $arr[$low];

    while ($low < $high) {
        while ($low < $high && $arr[$high]['cat_id'] >= $key['cat_id']) {
            $high--;
        }
        $arr[$low] = $arr[$high];
        while ($low < $high && $arr[$low]['cat_id'] <= $key['cat_id']) {
            $low++;
        }
        $arr[$high] = $arr[$low];
    }
    $arr[$low] = $key;
    return $low;
}

private function summary2_quickSort(&$data, $low, $high)
{
    if ($low < $high) {
        $middle = $this->summary2_partition($data, $low, $high);
        $this->summary2_quickSort($data, $low, $middle - 1);
        $this->summary2_quickSort($data, $middle + 1, $high);
    }
}

/**
 * @param $data array 按照商品汇总数据
 */
private function data_summary2(&$data)
{
    ...
    // 按照商品分类对商品列表进行排序（订单详情结果已汇总到第一个订单中） 快速排序
    $cnt = count($newList[0]['orderDetail']);
    $this->summary2_quickSort($newList[0]['orderDetail'], 0, $cnt - 1);
    return $newList;
}

此次应用场景为对导出的订单商品列表按照商品分类进行排序。在被调函数形参前面加的 & 符号表示引用赋值，这样，在形参上的变动会反应在实参上。

有机会可以再用 C 实现一遍。