排序算法之快速排序（Java实现）-蒲公英云

排序算法之快速排序（Java实现）

清疚 2022-01-05 07:15 354阅读 0赞

快速排序是一种交换排序，这种排序的思想是把数组通过不断的递归，把数组中的数据分成两部分，前半部分小于某一个数，后半部分大于这个数，接着再对这两部分分别使用这种思想进行交换排序。这种排序的重点在于理解：局部排好序，那么整体就排好序了。

那么，如何把数据分成两部分，这里有个简单的办法，每次取数组中的第一个下标为low=0的元素，作为基准temp，然后通过从数组末端下标为high开始找比他小的元素，如果找到，那么nums[low]=nums[high]，这一步只是把高位上的元素移到低位，高位空出来，接着从低位开始找比temp大的元素，如果找到，则将刚才空出的高位填上这个低位的数据，nums[high]=nums[low]，当low=high的时候，再将这个位置填上temp，nums[low]=temp，这时候数组中已经分成了两部分，下一次从这个位置两边开始递归。

package com.xxx.algorithm.sort;
public class QuickSort {
    public static void quickSort(int[] nums,int low,int high){
        if(low<high){
            int middle = getMiddle(nums, low, high);
            quickSort(nums, low, middle-1);
            quickSort(nums, middle+1, high);
        }
    }
    public static int getMiddle(int[] nums,int low,int high){
        int temp = nums[low];
        while(low<high){
            while(low<high && nums[high] > temp){
                high--;
            }
            nums[low] = nums[high];
            while(low<high && nums[low]<temp){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = temp;
        return low;
    }
    public static void main(String[] args) {
        int data[] = {5,2,3,4,1,7,9,8,6,0,120,100};
        quickSort(data, 0, 11);
        System.out.println();
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+" ");
        }
    }
}