java练习3.快速查找

题目: 数组 arr[6,1,3,7,9,8,5,4,2],用快速排序进行升序排序.

import java.util.Random;

public class recursionDemo {
    public static void main(String[] args) {

        /*快速排序:
        * 第一轮:以0索引为基准数,确定基准数在数组正确的位置,
        * 比基准数小的放到左边,比基准数大的放在右边,
        * 以此类推*/

        int [] arr={6,1,3,7,9,8,5,4,2};

        /*调用方法:
        * 参数:排序数组,起始索引,结束索引*/
        quickSort(arr,0,arr.length-1);
        //输出打印
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k]+" ");
        }
    }

    public static void quickSort(int [] arr,int i,int j){
        //start,end确定查找范围
        int start=i;
        int end =j;

        //作用是结束掉递归
        if(start>end){
            return;
        }

        //基准数赋值
        int baseNumber=arr[i];

        //利用循环找到需要交换的数字
        while(start!=end){
            //利用end,从结束索引开始往前找,找比基准数小的
            while(true){
                if (start>=end||arr[end]<baseNumber){
                    break;
                }
                end--;
            }
            while(true){
                //利用start,从结束索引开始往前找,找比基准数大的
                if (start>=end||arr[start]>baseNumber){
                        break;
                    }
                    start++;
            }

            //把start,与end的元素进行交换
           int temp=arr[start];
           arr[start]=arr[end];
           arr[end]=temp;
        }

        //当start与end同时指向同一个数时,循环结束
        //结束完成后,需要把基准数和star与end同时指向的位置进行交换
        int temp=arr[i];
        arr[i]=arr[start];
        arr[start]=temp;


      /*此时,i为0,end为基准数位置
      * 再把基准数左边和右边分别进行相同的计算
      * 确定左边起始位为数组起始索引0,结束位为end-1
      * 确定右边起始位为start+1,结束位为数组结束索引*/
       quickSort(arr,i,end-1);

       quickSort(arr,start+1,j);

    }

}

1.把第一个数当做基准数,运用2个指针start与end 一个从前往后,一个从后往前.

2.当start遇到比基准数大的数时,当end遇到比基准数小的数时,就交换位置.

(提醒:一定要先写end指针,不能先写start指针,不然会结果错误)

3.最后在用基准数与end,start同时指向的元素换位置

4.后面利用递归把基准数2边,重新看成2个新数组进行相同操作