快速排序JAVA实现

2022/1/8 14:33:42

本文主要是介绍快速排序JAVA实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快排的原理是:

选择一个关键值作为基准值,(可以选择第一个,也可以选择最后一个,或者随便选一个,我习惯选第一个)。

将比基准值大的都放在右边的序列中,将比基准值小的都放在左边的序列中。

具体循环过程:从后向前比较,用基准值和最后一个值进行比较。如果比基准值小,则换位,如果比基准值大,则继续比较下一个值,知道找到第一个比基准值小的值才交换位置。

 

再从前向后比较,如果有比基准值大的,交换位置,如果没有,则继续比较下一个,直到找到第一个比基准值大的值才交换位置,

 

重复执行上述过程。直到左边都是小于基准值的数,右边都是大于基准值的数。

继续重复循环上述过程。

package sort;

/**
 * @author leon
 * @描述 快速排序算法实现
 */
public class quickSort {
    public static int[] quickSort(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        int pivot = arr[low];
        while (end > start) {
            while (end > start && arr[end] >= pivot) {
                end--;
            }
            if (arr[end] <= pivot) {
                swap(arr,end,start);
            }
            while (end > start && arr[start] <= pivot) {
                start++;
            }
            if (arr[start] >= pivot) {
                swap(arr,start,end);
            }
        }
        if (start >low) quickSort(arr, low, start-1);
        if (end < high) quickSort(arr,end + 1, high);
        return arr;
    }

    public static void swap(int[] arr,int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {1,3,5,8,7,4,6};
         quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length ; i++) {
            System.out.println(arr[i]);
        }

    }

}

 



这篇关于快速排序JAVA实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程