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

快速排序（java实现及过程解析） 1.概念

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

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

2.java实现

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;
    }
}

 3.过程

        待排序数组：

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

基准lr第1次划分原数组进入partition01234567891068790613245交换5和8，l++,r--01234567891065790613248交换4和7，l++,r--01234567891065490613278交换2和9，l++,r--01234567891065420613978l++01234567891065420613978l++01234567891065420613978l++01234567891065420613978l++01234567891065420613978l>r，结束while交换target和nums[r]01234567891035420616978第2次划分进入partition01234567891035420616978交换5和1，l++,r--01234567891031420656978r--01234567891031420656978交换4和0，l++,r--01234567891031024656978l++01234567891031024656978l>r，结束while交换target和nums[r]01234567891021034656978第3次划分进入partition01234567891021034656978l++01234567891021034656978l++01234567891021034656978l>r，结束while交换target和nums[r]01234567891001234656978第4次划分进入partition01234567891001234656978r--，l>r，结束whiler=left，不做交换01234567891001234656978第5次划分进入partition01234567891001234656978r--01234567891001234656978r--，l>r，结束whiler=left，不做交换01234567891001234656978第6次划分进入partition01234567891001234656978l++01234567891001234656978l>r，结束while交换target和nums[r]01234567891001234566978第7次划分进入partition01234567891001234566978l++01234567891001234566978l++　01234567891001234566978　l>r，结束while交换target和nums[r]01234567891001234566879第8次划分进入partition01234567891001234566879l++01234567891001234566879l>r，结束while交换target和nums[r]01234567891001234566789最终结果01234566789