算法系列（二）快速排序

相信刚进入到编程学习的同学，在基础部分一定会涉及到排序相关的内容，那么快速排序也是最常接触到的。时间多年，像这些算法在工作中对于我本人来说使用比较少，但是最近在复盘的阶段，所以想起这个事情了，在此做一个记录。

这篇文章我们介绍下快速排序，首先来看一张图：

从上图可以看出快速排序的步骤如下：

1）定基准。随意挑选一个元素为基准值（一般取第一个）。
2）重新排序。将小于基准值的元素放在左边，大于基准值的元素放在右边。此次完成后，基准值换成中间位置。
3）递归的把小于基准值的子序列和大于基准值的子序列排序。

下面使用java版本来演示一下：

package com.demo.Demo;

import java.util.Arrays;

public class BubblingSort {

	private static final int nums[] = { 1, 7, 3, 0, 2, 9, 8, 5, 4, 6 };

	public static void main(String[] args) {
		
		int[] rs_nums = quickSort(nums, 0, nums.length-1);
		System.out.println(Arrays.toString(rs_nums));
	}
	
	private static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }
	
	private static int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }
	
	private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

运行下，看看结果：