[数据结构与算法]数组排序 之 快速排序算法

java实现快速排序

利用快速排序对无序数组进行排序

快速排序算法的基本原理：

分治法：比大小：再分区

1. 从数组中取出第一位数作为基准数（一般选择第一位数字）。
2. 比较大小后分区：大于或者等于基准数的数据放在右边；小于基准数的数据放在左边。
3. 再对左右区间重复前面第二步，直到各区间只有一个数。

代码实现：

import java.util.Arrays;

public class test1 {
    public static void main(String[] args) {
        int[] arr={1644,32,4,56,235,90,345,77,56};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void  quickSort(int[] arr, int start, int end) {
        int i=start;
        int j=end;
        if(i>=j){
            return;
        }
        //temp就是基准位
        int temp=arr[start];
        while(i<j){
            //先看右边，依次往左递减
            while(arr[j]>=temp&&i<j){
                j--;
            }
            //再看左边，依次往右递增
            while(arr[i]<=temp&&i<j){
                i++;
            }
            //如果满足条件则交换
            if (i<j){
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[start]=arr[i];
        arr[i]=temp;
        //递归调用左半数组
        quickSort(arr,start,i-1);
        //递归调用右半数组
        quickSort(arr,i+1,end);

    }
}

运行结果：

[4, 32, 56, 56, 77, 90, 235, 345, 1644]

Process finished with exit code 0