排序之快速排序

百度百科上找的

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。也称分治法。

1.算法基本实现思路

1. 先从要排序的数组中选定一个基准数(一般为第一个)
2. 将比基准数大的数全放到基准数的右边，将比基准数小的数全放到基准数的左边
3. 重复1 2 过程，直到各区间只有一个数

2.分析（从小到大排列为准）

• 最坏情况分析：
  例：现有一个数组9，8，7，6，5，4，3，2，1，0，从小到大排序,长度为n,基准数为k

0	1	2	3	4	5	6	7	8	9
9	8	7	6	5	4	3	2	1	0

初始i = 0,j = n-1,k = a[0] = 9

0	1	2	3	4	5	6	7	8	9
0	8	7	6	5	4	3	2	1	9

a[n-1]<k;j = n-1;从左到右寻找比9大的数,无结果 i = = j;交换k与a[j],在[0,8]区间重复，[9,-]重复

依此类推： 一趟排序确定一个，每趟n-1-i,与冒泡排序一致
Cm = n*(n-1)/2

所以最坏时O(n*n)

• 最好情况分析：
  最好下为O(nlogn)

3.案例

例：6 1 2 7 9 3 4 5 10 8

0	1	2	3	4	5	6	7	8	9
6	1	2	7	9	3	4	5	10	8

初始k = a[0] = 6;i = 0;j = n - 1 = 9;重复1，2过程：
a[7]<k,j = 7; a[3] >k,i = 3; i<j;交换a[7]与a[3]的值

0	1	2	3	4	5	6	7	8	9
6	1	2	（第一次交换）5	9	3	4	7（第一次交换）	10	8

从上一次的位置继续重复步骤：
j = 6;i = 4;k = 6
a[j] = 4 < k=6; 从左到右 -> a[i] > k=6; i<j ; a[4] 与a[6]继续交换

0	1	2	3	4	5	6	7	8	9
6	1	2	（第一次交换）5	4（第二次交换）	3	9（第二次交换）	7（第一次交换）	10	8

i = 5;j = 5; 重复 ij5时,交换基准数K与a[i];

0	1	2	3	4	5	6	7	8	9
3	1	2	（第一次交换）5	4（第二次交换）	6	9（第二次交换）	7（第一次交换）	10	8

此时基准数为3；
[left,i-1]和[i+1,right]递归排序,直到每个区间只有一个元素

流程图：

实现：

package com.wdl.kt.java;

import java.util.Scanner;

/**
 * @program: kt1
 * @author: wdl
 * @create: 2018-09-28 22:36
 */

//快速排序
public class QuickSort {
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            if (n <= 0) return;
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = scanner.nextInt();
            quickSort(a, 0, n - 1);
            for (int i : a) {
                System.out.print(i + " ");
            }
            System.out.println("");
        }
    }

    private static void quickSort(int[] a, int left, int right) {
        if (left > right) return;
        int i = left;
        int j = right;
        int k = a[left];  //基准数
        while (i != j) {
            //从右到左 查找小于基准数的，跳过不满足要求的（大于 等于）
            while (i < j && a[j] >= k) j--;
            //从左到右 查找大于基准数的，（大于 等于）
            while (i < j && a[i] <= k) i++;
            //有符合的情况,进行交换，跳过不满足要求的
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        //相遇,调换基准数字 与 相遇位置的数字
        a[left] = a[i];
        a[i] = k;
        //左右两边同时进行递归排序
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }
}