快速排序

分析

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

162002841931

代码

  • 双向划分(最基础版)
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
49
package 算法;

public class 快速排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{-9,78,0,23,-567,70};
        quickSort(arr, 0, arr.length-1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            int l = left;//左下标
            int r = right;//右下标
            int temp = arr[l];//基准数
            //循环进行分组
            while(l<r){
                //从右边找比它小的数
                while(r>l&&arr[r]>=temp){
                    r--;
                }
                //如果找到则将它放在左边
                if(l<r){
                    arr[l]=arr[r];
                    l++;
                }
                //从左边找比它大的数
                while(l<r&&arr[l]<=temp){
                    l++;
                }
                //如果找到则将它放在右边
                if(l<r){
                    arr[r]=arr[l];
                    r--;
                }
            }
            //这里l==r
            //注意需要将temp填回中间
            arr[l]=temp;
            //分别对中间两边再进行分组排序
            //左边
            quickSort(arr,left,l-1);
            //右边
            quickSort(arr, l+1,right);
        }

    }
}

  • 双向划分升级版

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public static void quickSort(int[] arr,int left,int right){
      	if(left >= right) return; //数组只有一个或零个元素肯定有序直接返回
      	//并用i，j记录左右划分起点，但是由于使用的dowhile肯定会先++所以需要再往外取1
      	int x = arr[left + right >> 1],i = left - 1,j = right + 1; //取中点为基准
        while(i < j){ 
          do i++;while(arr[i] < x); //从左向右找找大于等于x的数
          do j--;while(arr[i] > x);	//从右向左找找小于等于x的数
          if(i < j){								//如果i，j没有相遇则交换使左边小于等于x，右边大于等于x
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
          }
        }
      	quickSort(arr,left,j); 			//递归遍历左边
      	quickSort(arr,j+1,right);		//递归遍历右边
    }

  • 单向划分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public static void quickSort(int[] arr,int left,int right){
      	if(left >= right) return; //数组只有一个或零个元素肯定有序直接返回
      	int x = arr[1],i = left; //取最左边为基准 i作为分隔点,左边全为小于x的数据包括i右边大于等于x
        for(int j = left + 1;j <= r;j++){
          if(arr[j] < x){ //用j来从左向右找小于x的值与++i交换 因为i所在的元素已经小于x
            int temp = arr[++i];
            arr[i] = arr[j];
            arr[j] = temp;
          }
        }
        int temp = arr[left]; //最后将基准与i即为基准的最终位置交换
        arr[left] = arr[i];
        arr[i] = temp;
        
      	quickSort(arr,left,i-1); 			//递归遍历左边
      	quickSort(arr,i+1,right);		//递归遍历右边
    }