快速排序Java實現

　　About this application:

　　This application implements Quick Sort algorithm which is described like this:

　　Using the Divideandconquer method the Quick Sort first choose a pivot number then divide the numbers which wait for sort into two parts the left part are all smaller than the pivot number while the right part are all bigger than the pivot number Like this then choose a new pivot for the left part and divide it into two parts too Also the left part smaller than the pivot and the right part bigger than the pivot Using this iteration until there is only one number in the divided part At this time your function can return

　　Come to one specific sort there should be two pointers one point to the start while another point to the end If number in the start bigger than pivot then put it in behind or else start pointer move towards afterward If number in the end smaller than pivot then put it in before or else end pointer move towards forward

　　In order to improve the algorithm you can first put the pivot in a temp and after the numbers have been divided then put back the pivot to the position where start and end position are in Also maybe you can use some strategies to use a better pivot

　　Source Code:

　　package quicksort;

　　import javautilArrayList;

　　import javautilScanner;

　　/**

　　* Sort the numbers using quick sort algorithm If there is any suggestion about

　　* this program please email to Author: vivien

　　* Date:

　　*/

　　public class QuickSort {

　　public ArrayList<Double> storeNumbers;

　　public static QuickSort quickSort;

　　public boolean outputEnable;

　　public static void main(String args[]) {

　　Systemoutprintln(Welcome to quick sort!);

　　quickSort = new QuickSort();

　　quickSortoutputEnable = true;

　　quickSortinputNumbers();

　　}

　　/**

　　* Input the numbers you want to sort

　　*/

　　public void inputNumbers() {

　　Scanner in = new Scanner(Systemin);

　　String s;

　　storeNumbers = new ArrayList<Double>();

　　while (true) {

　　Systemout

　　println(Please input the numbers you need to sort(Note: seperate the numbers using comma ):);

　　s = innextLine();

　　// If the input is empty

　　if (strim()isEmpty()) {

　　Systemoutprintln(The numbers you input are not correct);

　　outputEnable = false;

　　continue;

　　} else {

　　String[] a = ssplit();

　　// If the length is

　　if (alength == ) {

　　Systemout

　　println(The numbers you input are not correct);

　　outputEnable = false;

　　continue;

　　}

　　for (int i = ; i < alength; i++) {

　　try {

　　storeNumbersadd(DoublevalueOf(a[i]));

　　outputEnable = true;

　　} catch (NumberFormatException e) {

　　Systemout

　　println(The numbers you input are not correct);

　　outputEnable = false;

　　storeNumbersclear();

　　break;

　　}

　　}

　　}

　　// Sort the numbers

　　sort( storeNumberssize() );

　　// Output the results

　　output();

　　storeNumbersclear();

　　}

　　}

　　/**

　　* Get the pivot of the numbers

　　*

　　* @param start

　　*            The start position of the numbers waiting for sort

　　* @param end

　　*            The end position of the numbers waiting for sort

　　* @return the pivot of the numbers

　　*/

　　public int getPartitionPoint(int start int end) {

　　return (start + end) >> ; // Get the number in the middle

　　}

　　/**

　　* Partition the numbers waiting for sort make the left numbers smaller

　　* than the pivot while the right numbers bigger than the pivot

　　*

　　* @param before

　　*            The start position of the numbers waiting for sort

　　* @param after

　　*            The end position of the numbers waiting for sort

　　* @return the position of the pivot

　　*/

　　public int partition(int before int after) {

　　double temp;

　　int PartitionPoint = getPartitionPoint(before after);

　　temp = storeNumbersget(PartitionPoint);

　　// Put the first number in the position of pivot

　　storeNumbersset(PartitionPoint storeNumbersget(before));

　　// Compare and exchange until before and after are equal

　　while (before != after) {

　　while ((before != after) && (storeNumbersget(after) >= temp)) {

　　after;

　　}

　　if (before < after) {

　　storeNumbersset(before storeNumbersget(after));

　　before++;

　　}

　　while ((before != after) && (storeNumbersget(before) <= temp)) {

　　before++;

　　}

　　if (before < after) {

　　storeNumbersset(after storeNumbersget(before));

　　after;

　　}

　　}

　　storeNumbersset(before temp);

　　return before;

　　}

　　/**

　　* Sort the numbers using iteration

　　*

　　* @param start

　　*            The start position of the numbers waiting for sort

　　* @param end

　　*            The end position of the numbers waiting for sort

　　*/

　　public void sort(int start int end) {

　　if (end start < )

　　return;

　　int positionPoint = partition(start end);

　　sort(start positionPoint );

　　sort(positionPoint + end);

　　}

　　/**

　　* Output the results

　　*/

　　public void output() {

　　if (outputEnable == true) {

　　Systemoutprintln(The numbers after sort are:);

　　for (int i = ; i < storeNumberssize(); i++) {

　　Systemoutprint(storeNumbersget(i) + );

　　}

　　Systemoutprintln();

　　} else

　　return;

　　}

　　}

　　Blackbox Test Case:

　　) All numbers are zero:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　

　　The numbers after sort are:

　　

　　) All numbers are integer:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　+

　　The numbers after sort are:

　　

　　) All number are double:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　++

　　The numbers after sort are:

　　

　　) Numbers with characters which are not digit numbers;

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　we

　　The numbers you input are not correct

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　ert

　　The numbers you input are not correct

　　) Numbers separated by other signs:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　;;;

　　The numbers you input are not correct

　　) Numbers are only commas:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　

　　The numbers you input are not correct

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　

　　The numbers you input are not correct

　　) Input nothing but just a return:

　　Please input the numbers you need to sort(Note: seperate the numbers using comma ):

　　The numbers you input are not correct

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26043.html