[JAVA] 快速排序法（Quicksort）

※ 此程式碼並非優化版本，僅供個人學習用途，若有任何問題請告知。



程式碼如下：

	import java.util.*;
	import java.lang.*;
	import java.io.*;
	public class quicksort {
	public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int i;
	int count = scn.nextInt();
	int[] list = new int[count];
	System.out.println("Numbers to be sorted: ");
	for(i = 0; i < count; i++){
	list[i] = scn.nextInt();
	System.out.print(list[i]+" ");
	}
	System.out.println("\n");
	sort(list, 0, list.length-1);
	System.out.println("Numbers Sorted: ");
	for(int u : list) {System.out.print(u+" ");}
	System.out.println("");
	}
	private static void sort(int[] list, int left, int right) {
	if(left < right) {
	int q = partition(list, left, right); //找pivot
	for(int u : list) {System.out.print(u+" ");}
	System.out.println("\n");
	sort(list, left, q-1); //左子串列
	sort(list, q+1, right); //右子串列
	}
	}
	private static int partition(int list[], int left, int right) {
	int i = left - 1; // i 最後的位置是左子串列的最後一個
	for(int j = left; j < right; j++) { //分開左右子列 左小 右大
	if(list[j] <= list[right]) {
	i++;
	swap(list, i, j);
	}
	}
	swap(list, i+1, right); //pivot與右子串列第一個的位置交換
	return i+1; //回傳pivot之位置
	}
	private static void swap(int[] list, int i, int j) {
	int t = list[i];
	list[i] = list[j];
	list[j] = t;
	}
	}

view raw quicksort.java hosted with ❤ by GitHub

結果如下：

10
Numbers to be sorted:
100 90 80 70 60 50 40 30 20 10
100 90 80 70 60 50 40 30 20 10


10 90 80 70 60 50 40 30 20 100


10 90 80 70 60 50 40 30 20 100


10 20 80 70 60 50 40 30 90 100


10 20 80 70 60 50 40 30 90 100


10 20 30 70 60 50 40 80 90 100


10 20 30 70 60 50 40 80 90 100


10 20 30 40 60 50 70 80 90 100


10 20 30 40 60 50 70 80 90 100


10 20 30 40 50 60 70 80 90 100


Numbers Sorted:
10 20 30 40 50 60 70 80 90 100