欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java中的快速排序

程序员文章站 2022-03-16 19:14:28
...
import java.lang.reflect.Array;
import java.util.Arrays;

public class KSpx {
    public static int getIndex(int []arr,int low,int high){
        //基准数据
        int temp=arr[low];
        while (low<high){
            //当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low<high && arr[high]>=temp){
                high--;
            }
            //如果队尾元素小于temp了,需要将其赋值给low
            arr[low]=arr[high];
            //当队首元素小于等于temp时,向前挪动low指针
            while (low<high && arr[low]<=temp){
                low++;
            }
            //当队首元素大于temp时,需要将其赋值给high
            arr[high]=arr[low];
        }
        //跳出循环时low和high相等,此时的low或high就是temp的正确索引位置
        //由原理部分可以很清楚的知道low的位置的值并不是temp,所以需要将temp赋值给arr[low]
        arr[low]=temp;
        return low;//返回temp正确位置
    }
    public static void quickSort(int []arr,int low,int high){
        if(low<high){
            //找寻基准数据的正确索引
            int index=getIndex(arr,low,high);
            //进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr,low,index-1);
            quickSort(arr,index+1,high);
        }

    }

    public static void main(String[] args) {
        int []arr={3,5,1,6,8,7};
        quickSort(arr,0,arr.length-1);
        System.out.print(Arrays.toString(arr));
    }
}