快速排序（java实现及过程解析）

        快速排序是由冒泡排序改进而得的，基本思想是在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入适当的位置后，数据序列被此元素划分为两个部分。所有关键字比该元素关键字小的元素放在前一部分，所有比他大的元素放置在后一部分，并把该元素排在这两个部分的中间（称为该元素归位），这个过程成为一趟快速排序，即一趟划分。

        之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或者空为止。

import java.util.Arrays;

public class QuickSort {
    public void quickSort(int nums[], int left, int right) {
        //如果左边>=右边，没有意义
        if (left >= right) {
            return;
        }
        //快速排序一次后，基准元素所在的位置
        int position = partition(nums, left, right);

        //此时基准元素左侧的元素都比他小，右侧的都比他大
        //对基准元素左、右两侧的元素再进行快速排序
        quickSort(nums, left, position - 1);
        quickSort(nums, position + 1, right);
    }

    public int partition(int nums[], int left, int right) {
        //总是以最左边的元素作为基准元素
        int target = nums[left];
        int l = left + 1;
        int r = right;
        while (l <= r) {
            if (nums[l] > target && nums[r] < target) {
                swap(nums, l++, r--);
            }
            if (nums[l] <= target) {
                l++;
            }
            if (nums[r] >= target) {
                r--;
            }
        }
        //把基准元素放在对应的位置
        if(left != r){
            swap(nums, left, r);
        }
        //返回基准元素所在的位置
        return r;
    }

    
    public void swap(int nums[], int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

        待排序数组：

        [6, 8, 7, 9, 0, 6, 1, 3, 2, 4, 5]