【算法】快速排序

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;


public class QuickSortUtils {
    public static void main(String[] args) {
        Integer[] i = new Integer[]{5,3,2,1,4,7,6,9,0,8};
        List testArray = Arrays.asList(i);
        System.out.println(qSort(testArray));
    }

   
    private static List qSort(List subList){
        if(subList == null || subList.size() == 0){
            return Collections.emptyList();
        }
        if(subList.size() < 2){
            return subList;
        }
        // 选择一个基准值
        int pivot = 0;
        Integer pivotValue = subList.get(pivot);
        //获取所有比基准值对应的值小的集合放到 【左边集合】
        List less = subList.stream().filter(item -> item < pivotValue).collect(Collectors.toList());
        //获取所有比基准值对应的值大的集合放到 【右边集合】
        List greater = subList.stream().filter(item -> item > pivotValue).collect(Collectors.toList());
        //最终排序完成的集合为 【左边集合】 + pivotValue + 【右边集合】
        List lessResult = qSort(less);
        List greaterResult = qSort(greater);
        List result = new ArrayList<>();
        result.addAll(lessResult);
        result.add(pivotValue);
        result.addAll(greaterResult);
        return result;
    }
}

结果：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

存在重复元素怎么处理呢，思路是一致的，中间值代表的元素拼接时，无需排序，直接拼接到结果数组就可以了。

DEMO

package org.example.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;


public class QuickSortUtils {
    public static void main(String[] args) {
        Integer[] i = new Integer[]{3,5,1,1,4,2,3};
        List testArray = Arrays.asList(i);
        System.out.println(qSortWithEqualsValue(testArray));

    }

  

    
    private static List qSortWithEqualsValue(List subList){
        if(subList == null || subList.size() == 0){
            return Collections.emptyList();
        }
        if(subList.size() < 2){
            return subList;
        }
        // 选择一个基准值
        int pivot = 0;
        Integer pivotValue = subList.get(pivot);
        // 获取所有比基准值对应的值小的集合放到 【左边集合】
        List less = subList.stream().filter(item -> item < pivotValue).collect(Collectors.toList());
        // 中位数相等的值，不需要参与排序，直接拼接 【中间集合】
        List equals = subList.stream().filter(item -> Objects.equals(item, pivotValue)).collect(Collectors.toList());
        // 获取所有比基准值对应的值大的集合放到 【右边集合】
        List greater = subList.stream().filter(item -> item > pivotValue).collect(Collectors.toList());
        // 最终排序完成的集合为 【左边集合】 + pivotValue + 【右边集合】
        List lessResult = qSortWithEqualsValue(less);
        List greaterResult = qSortWithEqualsValue(greater);
        List result = new ArrayList<>();
        result.addAll(lessResult);
        result.addAll(equals);
        result.addAll(greaterResult);
        return result;
    }
}

结果:

[1, 1, 2, 3, 3, 4, 5]