快速排序

 2019-07-190 Comments

思路:

  1. 选取一个标准值t(数组的第一个)
  2. 使用快排的遍历方式把大于t的放到t的右边,小于的放到左边
  3. t的左半部分和右半部分递归重新计算
  4. 重复上一步直到左右边只有一个值

上面第二部的思路:

  1. 设置两个指针,一个头l,一个尾h
  2. 从h开始往前,如果遇到值小于t,让l位置的值变为h的值
  3. 从l开始往后,如果遇到值大于t,让h位置的值变为l的值
  4. 重复2,3步骤直到l等于h
  5. 这样就把所有大于t的数放到后面,小于的放到前面
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=(int)(Math.random()*100)+1;
        }
        for(int i=0;i<n;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
        quicksort(arr,0,arr.length-1);
        for(int i=0;i<n;i++){
            System.out.print(arr[i]+" ");
        }
    }
    public static void quicksort(int[] a, int l, int h){
        if(l<h){
            //这里需要设置临时变量,用于最后的纪录temp的位置和最开始的头和尾的位置
            int low=l;
            int high=h;
            int temp=a[l];
            while(low<high){
                //a[high]>=temp 需要加上=,如果不加上会产生两个相同的值相近,high位置不会+1,陷入死循环
                while(a[high]>=temp&&low!=high){
                    high--;
                }
                a[low]=a[high];
                while(a[low]<=temp&&low!=high){
                    low++;
                }
                a[high]=a[low];
            }
            a[low]=temp;

            quicksort(a,l,low-1);
            quicksort(a,low+1,h);
        }

    }
}