快速排序代码

悠悠 2024-03-23 02:19 76阅读 0赞

import java.util.Arrays;
    
    public class QuickSort {
        
    
        public static void main(String[] args) {
        
            int[] nums = {
        3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
            int[] sortedNums = quickSort(nums);
            System.out.println(Arrays.toString(sortedNums));
        }
    
        public static int[] quickSort(int[] nums) {
        
            // 基本情况：当数组为空或只有一个元素时，无需排序
            if (nums.length <= 1) {
        
                return nums;
            }
    
            int pivot = nums[0]; // 选择第一个元素作为基准值（pivot）
    
            // 初始化三个数组，用于存放小于、等于和大于基准值的元素
            int[] smaller = new int[nums.length];
            int[] equal = new int[nums.length];
            int[] larger = new int[nums.length];
    
            int smallerIndex = 0;
            int equalIndex = 0;
            int largerIndex = 0;
    
            // 遍历数组，将元素分配到相应的数组
            for (int num : nums) {
        
                if (num < pivot) {
        
                    smaller[smallerIndex++] = num;
                } else if (num == pivot) {
        
                    equal[equalIndex++] = num;
                } else {
        
                    larger[largerIndex++] = num;
                }
            }
    
            // 递归地对较小和较大的子数组进行快速排序
            smaller = quickSort(Arrays.copyOf(smaller, smallerIndex));
            larger = quickSort(Arrays.copyOf(larger, largerIndex));
    
            // 将排序后的子数组和相等元素数组合并成一个数组
            System.arraycopy(smaller, 0, nums, 0, smallerIndex);
            System.arraycopy(equal, 0, nums, smallerIndex, equalIndex);
            System.arraycopy(larger, 0, nums, smallerIndex + equalIndex, largerIndex);
    
            return nums;
        }
    }