快速排序

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

给定一串数字选择一个数作为这串数字的基准值。

每次排序将小于基准值的数放在基准值的左边，将大于基准值的数放在基准值的右边，这样便完成了一次排序。

然后分别对左边子序列和右边子序列进行上一步的操作，知道比较数组的长度为1时完成排序。

根据对快速排序的定义我们可以用数组保存这串数。令数组的第一个数做为基准值进行比较。定义两个指针，一个放在数组的首地址，另一个放在位地址。定义左指针叫left，右指针叫right。

右值8小于基准值19，交换。

L右移

97大于右值19，交换

R左移

1小于19

L右移

 9比19小不交换

L右移

17也比19小L右移

此时重叠，基准值的位置在L=R的时候再次移动R<L，至此一轮比较结束。

依次选择递归，改变递归的左边界和右边界直到递归结束完成排序。

代码

public class QuickSort {
    public void Qs(int[] arr, int L, int R) {
        if (L > R) {
            return;
        }
        int left = L;
        int right = R;
        int value = arr[left];//最左边是比较值
        while (left < right) {
            if (arr[right] < value) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
            } else {
                right--;
            }
            if (arr[left] > value) {
                int temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
                right--;
            } else {
                left++;
            }
        }
//        System.out.println("left:" + left);
//        System.out.println("right:" + right);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        //左
            Qs(arr, L, left - 1);
        //右
            Qs(arr, R + 1, R);
    }

    public static void main(String[] args) {
        QuickSort num = new QuickSort();
        int[] arr = new int[]{19, 97, 9, 17, 1, 8};
        num.Qs(arr, 0, arr.length - 1);
    }
}

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