快速排序算法

快速排序算法的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

我们来看看一趟排序中如何将数据划分为两部分，使得左边部分比给定元素小，而右边部分比给定元素大。
首先，我们选定一个数字作为中轴元素用于划分数据，我们选择数据的第一个元素。
然后，我们定义两个指针，分别指向数据的首（i）和尾（j）。从后面（j）元素开始进行比较，如果j指向的元素大于等于中轴元素，则j–，向前移动一位；否则，交换i和j位置的元素。然后，从前面（i）元素比较，如果i指向的元素小于等于中轴，则i++，向后移动一位；否则，交换i和j位置的元素。这样一直循环，知道i==j为止。这样就完成了一次划分，我们选择的中轴元素刚好位于i（此时，i等于j）位置上。

下面是一个示意图：

下面给出Java的实现：

package cn.tzy;

import java.util.Arrays;

public class SortAlg {
    public static void main(String[] args) {
        int[] numbers = {5, 1, 6, 7, 0, 4, 2, 3};
        quickSort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.toString(numbers));
    }

    public static void swap(int[] numbers, int i, int j) {
        if (numbers[i] == numbers[j]) return;
        numbers[i] = numbers[i] ^ numbers[j];
        numbers[j] = numbers[i] ^ numbers[j];
        numbers[i] = numbers[i] ^ numbers[j];
    }

    public static void quickSort(int[] numbers, int low, int high) {
        if (numbers.length < 2) return;
        if (low >= high) return;

        int left = low;
        int right = high;
        int pivot = numbers[low];
        while (left < right) {
            while (left < right && numbers[right] >= pivot) right--;
            swap(numbers, left, right);
            while (left < right && numbers[left] <= pivot) left++;
            swap(numbers, left, right);
        }

        quickSort(numbers, low, right - 1);
        quickSort(numbers, left + 1, high);
    }
}

我们再来看看用Scala的函数式编程思想如何实现：

package cn.tzy

object SortAlg {
  def quickSort(numbers: List[Int]): List[Int] = {
    if (numbers.length < 2) numbers
    else {
      quickSort(numbers.filter(_ < numbers.head)) ++
        numbers.filter(_ == numbers.head) ++
        quickSort(numbers.filter(_ > numbers.head))
    }
  }

  def main(args: Array[String]): Unit = {
    val numbers = List(5, 1, 6, 7, 0, 4, 2, 3)
    println(numbers)
    val sortedNumbers = quickSort(numbers)
    println(sortedNumbers)
  }
}

有没有感受到函数式编程的简介，我们使用filter函数找出比中轴元素小的，然后是中轴元素，再接着是比中轴元素小。短短几行代码就完成了Java很多行代码的功能！