快速排序法QuickSort

/**

 *

 * @author Administrator

 * 功能：交换式排序之快速排序

 */

package com.test1;

import java.util.Calendar;

public class QuickSort {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        //int[] arr = { 1, 6, 0, -1, 9, -100, -90 };

        int[] arr = new int[10000];

        for (int i = 0; i < arr.length; i++) {

            //让程序随机产生一个1 - 10000个数

            //Math.random会产生一个0到1的数

            arr[i] = (int)(Math.random()*10000);

        }

        Quick quick = new Quick();

        //在排序前打印系统时间

        //Calendar是单开模式，在系统里面只有一个，且只需要一个实例，不是new 出来的

        //Java共有23中模式

        Calendar cal = Calendar.getInstance();

        System.out.println("排序前："+cal.getTime());

        quick.sort(0, arr.length-1, arr);

        //在排序后打印系统时间

        //因为是单开的，所有首先重新得到实例

        cal = Calendar.getInstance();

        System.out.println("排序后："+cal.getTime());

//        System.out.println("排序后的结果是：");

//        for (int i = 0; i < arr.length; i++) {

//            System.out.print(arr[i]+" ");

//        }

    }

}

//快速排序法

class Quick

{

    public void sort(int left, int right, int[] array){

        int l = left;

        int r= right;

        int pivot = array[(left+right)/2];

        int temp = 0;

        while(l < r)

        {

            while(array[l] < pivot) l++;

            while(array[r] > pivot) r--;

            if(l >= r)

                break;

            temp = array[l];

            array[l] = array[r];

            array[r] = temp;

        }

//        System.out.println("the current array is");

//        for(int i = 0; i< 5; i++)

//        {

//            System.out.println(" "+array[i]);

//        }

        if(l == r)

        {

            l++;

            r--;

        }

        if(left < r)

            sort(left,r,array);

        if(right> l)

            sort(l,right,array);

    }

}