快速排序法java代码实现 快速排序Java实现

快速排序Java实现  

　　About this application:

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

　　Using the Divide and conquer method the Quick Sort first choose a pivot number then divide the numbers which wait for sort into o 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 o 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 o 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 quick sort;

　　import java util ArrayList;

　　import java util Scanner;

　　/**

　　* 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[]) {

　　System out println( Wele to quick sort! );

　　quickSort = new QuickSort();

　　quickSort outputEnable = true;

　　quickSort inputNumbers();

　　}

　　/**

　　* Input the numbers you want to sort

　　*/

　　public void inputNumbers() {

　　Scanner in = new Scanner(System in);

　　String s;

　　storeNumbers = new ArrayList<Double>();

　　while (true) {

　　System out

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

　　s = in nextLine();

　　// If the input is empty

　　if (s trim() isEmpty()) {

　　System out println( The numbers you input are not correct );

　　outputEnable = false;

　　continue;

　　} else {

　　String[] a = s split( );

　　// If the length is

　　if (a length == ) {

　　System out

　　 println( The numbers you input are not correct );

　　outputEnable = false;

　　continue;

　　}

　　for (int i = ; i < a length; i++) {

　　try {

　　storeNumbers add(Double valueOf(a[i]));

　　outputEnable = true;

　　} catch (NumberFormatException e) {

　　System out

　　 println( The numbers you input are not correct );

　　outputEnable = false;

　　storeNumbers clear();

　　break;

　　}

　　}

　　}

　　// Sort the numbers

　　sort( storeNumbers size() );

　　// Output the results

　　output();

　　storeNumbers clear();

　　}

　　}

　　/**

　　* 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 = storeNumbers get(PartitionPoint);

　　// Put the first number in the position of pivot

　　storeNumbers set(PartitionPoint storeNumbers get(before));

　　// Compare and exchange until before and after are equal

　　while (before != after) {

　　while ((before != after) && (storeNumbers get(after) >= temp)) {

　　after ;

　　}

　　if (before < after) {

　　storeNumbers set(before storeNumbers get(after));

　　before++;

　　}

　　while ((before != after) && (storeNumbers get(before) <= temp)) {

　　before++;

　　}

　　if (before < after) {

　　storeNumbers set(after storeNumbers get(before));

　　after ;

　　}

　　}

　　storeNumbers set(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) {

　　System out println( The numbers after sort are: );

　　for (int i = ; i < storeNumbers size(); i++) {

　　System out print(storeNumbers get(i) + );

　　}

　　System out println();

　　} else

　　return;

　　}

　　}

　　Black box Test Case:

　　 ) All numbers are zero:

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

　　The numbers after sort are:

　　 ) All numbers are integer:

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

　　 +

　　The numbers after sort are:

　　 ) All number are double:

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

　　 + +

　　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 ma ):

　　we

　　The numbers you input are not correct

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

　　 er t

　　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 ma ):

　　 ; ; ;

　　The numbers you input are not correct

　　 ) Numbers are only mas:

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

　　The numbers you input are not correct

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

　　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 ma ):