【 八大排序之快速排序】_8.9.7.11.3.2.4.6快速排序

快速排序：

快速排序，它的时间复杂度为O(nlogn)
它的原理是：将整个递归分为两步，第一步是基本算法，第二步是递归

1.基本算法：首先定义两个索引 i 和 j,分别等于向方法传递的数组的left和right的索引，选定最左边的第一个数为基准数。两个循环分别从左右出发，左边找比基准数大的数，右边找比基准数小的数，同时右索引要大于左索引。当 i =j时，将i索引的数与基准数交换。本方法只执行完毕

2.递归：调用自身两次，第一次传数组，left，和i-1,第二次传数组，i+1，和right
递归出口为left=right。

源码如下：

public class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
 
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }
 
 
    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"  ");
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48