172.16.0.151_20200911-陈政平

问题

快速排序:

public class QuickSort {
    public void quickSort(int[] A, int left, int right) {
        if (left > right) {
            return;
        }
        int base = A[left];
        int x = left;
        int y = right;
        while (x != y) {
            while (A[y] >= base && x < y) {
                y--;
            }
            while (A[x] <= base && x < y) {
                x++;
            }
            int temp = A[x];
            A[x] = A[y];
            A[y] = temp;
        }
        A[left] = A[x];
        A[x] = base;
        quickSort(A, left, x - 1);
        quickSort(A, y + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 45, 62, 25, 123, 44, 98, 75, -10, 0 };
        QuickSort cd = new QuickSort();
        cd.quickSort(arr, 0, 8);
        System.out.println(java.util.Arrays.toString(arr));

    }
}

解决:

先把数组中的一个数当基准元素,一般会把数组中最左边的数当做基准数,然后从两边进行检索;

先从右边检索比基准数小的,再从左边检索比基准数大的,如果检索到了就停下来,然后交换这两个元素,然后再继续检索。

把基准元素和相遇位置的元素交换,基准数和相遇位置的数交换完成,表示第一轮排序结束。

这时,基准数左边的数都比它小,右边的数都比它大。

第二轮比较和第一轮比较方式一样;先排基准数左边的数,再排基准数右边的数。

标签

© 2021 成都云创动力科技有限公司 蜀ICP备20006351号-1