博客

1.三路快速排序算法的基本思想

之前的快速排序算法都是将序列分成<=v和>v或者是<v和>=v的两个部分，而三路快速排序是

将序列分成三个部分:<v、=v、>v，如下图所示:首先v元素还是作为”基准”元素，e表示当前遍历索引值指向的元素，也就是待考虑的元素整个序列被分成3个部分，也就是说当我们遍历完成之后整个序列就已经被分成了<v、=v、>v三个部分了，而我们只需要对<v和>v的两个部分再次递归调用三路排序函数进行排序即可。

2.代码

package p5.排序算法;

import java.util.Arrays;

public class QuickSort03 extends Sort{
    public QuickSort03(int[] arr) {
        super(arr);
    }
    @Override
    public void sort() {
        quickSort(0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private void quickSort(int L, int R) {
        if (L >= R) {
            return;
        }
        swap(L, (int) (Math.random() * (R - L + 1) + L));
        int v=arr[L];
        int lt=L;
        int gt=R+1;
        int i=L+1;
        while (i<gt) {
            if (arr[i] < v) {
                swap(i, lt + 1);
                lt++;
                i++;

            } else if (arr[i] > v) {
                swap(i, gt - 1);
                gt--;
            } else {
                i++;
            }
        }swap(L,lt);
        quickSort(L,lt-1);
        quickSort(gt,R);

    }


}