2018-7-25java快排学习

学习笔记,java

快速排列算法学习

数学原理:

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是

　　1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 　　
　　2）以第一个数组元素作为关键数据，赋值给X，即 X=A[0]； 　　
　　3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换； 　　4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换
　　5）重复第3、4步，直到 I=J；

具体例子

49(X) 38 65 97 76 13 27

首先设置关键值X 我是将49看作关键

经过第一次转换
27 38 65 97 76 13 49(X)
27 38 49(X) 97 76 13 65
27 38 13 97 76 49(X) 65
27 38 13 49(X) 76 97 65

因为可以看到此时I=J

所以将49隔离也就成了如下样子
27 38 13 |49| 76 97 65
然后左右分别执行快排
最后就得出了:
13 27 38 |49| 65 76 97
至此快排完成

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
public class QuickSortTest{
    private static void qSort(int[] arr, int head, int tail){
        if(head >= tail || arr == null || arr.length <= 1){
            return;//设置特殊情况
        }
        int i = head,j =tail, pivot = arr[(head + tail) / 2];
        //执行步骤3
        while(head <= j){
            while(arr[i] < pivot){
                ++i;
            }
            while(arr[j] < pivot){
                --j;
            }
            if(i < j){//判断是否满足排序条件
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;

            }else if(i == j){//满足第一次排序算法的结束条件
                ++i;

            }
        }
        qSort(arr, head, j);
        qSort(arr, i, tail);
    }
    public static void main(String[] args){
        int[] array = new int[]{49, 38, 65, 97, 76, 13, 27};
        qSort(array, 0,array.length -1);
        String out = "";
        for(int digit : array) {
            out += (digit + ",");
        }
        System.out.println(out);
    }
}