快排

  • 2021 年 12 月 4 日
  • 筆記

 最近在做題的時候，遇到這要一道題，大致意思是給定幾個數，讓排序，從小到大輸出，我很快就想到了，冒泡排序，和選擇排序，但在我寫完代碼提交的時候系統卻顯示，超時，所以我又想到了一種方法，所用的時間比較少，就是一種和二分法差不多的一種方法，主體思想就是，先選定一個數當作基點，然後讓他與其他各各數相比，然後把比他小的數放在他的左邊，把比他大的數放在他的右邊，然後用遞歸，讓這組數一直循環，一直到完成排序。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int[] num = new int[h];
        for (int i = 0; i < num.length; i++) {
            num[i] = sc.nextInt();
        }
        quickSort(num,0,num.length - 1);
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
    }
    public static void quickSort(int[] x,int n ,int m){
        if(n >= m){ //當 n>= m 時所有的數都已經進行過排序了，循環結束
            return;
        }
        int val = x[n];
        int a = n;
        int b = m;
        while(a < b){
            while(a < b && x[b] > val){
                b--;
            }
            if(a < b){
                x[a++] = x[b];
            }
            while(a < b && x[a] < val){
                a++;
            }
            if(a < b){
                x[b--] = x[a];
            }
        }
        x[a] = val;
        quickSort(x,n,a - 1); //對左邊進行快排
        quickSort(x,a + 1,m); //對右邊進行快排
    }
}

快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。每次排序的時候設置一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了。因此總的比較和交換次數就少了，速度自然就提高了。

VirMach 便宜 VPS

QNews

QNews