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

清疚 2022-01-05 07:15 272阅读 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]+" ");
    		}
    	}
    
    }