快速排序也是nlogn的算法，而且它在面對(duì)完全無序時(shí)是比歸并排序快的，但是它面對(duì)完全有序，或者重復(fù)數(shù)多的數(shù)組又顯得無力退化到n2.

下面我們來介紹一下快速排序

主要使用遞歸

選擇第一個(gè)點(diǎn)作為比較點(diǎn)，小于該點(diǎn)的數(shù)放在該點(diǎn)的左邊，大于該點(diǎn)的數(shù)放在該點(diǎn)的右邊

如果第i個(gè)元素比v大的話，就i++

如果第i個(gè)元素比v小的話，就會(huì)將第i個(gè)元素與j+1元素交換

最后將l處的v元素與第j個(gè)元素交換位置

算法實(shí)現(xiàn)：

import java.lang.reflect.Array;

import java.util.Arrays;

public class paixu {

public? static? void main(String args[])

{

Integer array[]=new Integer[10000];

? ? ? ? for (int i =0; i <10000; i++)

array[i] =new Integer((int)(Math.random() * (10000+1) ));

? ? ? paixu(array);

? ? ? ? for (int i =0; i <10000; i++)

System.out.println(array[i]);

? ? }

public? static? void paixu(Comparable[] array)

{

sort(array,0,array.length-1);

? ? }

public static void sort(Comparable[] array,int l,int r)

{

if(l>=r)

return;

? ? ? ? int p=part(array,l,r);

? ? ? ? sort(array,l,p-1);

? ? ? ? sort(array,p+1,r);

? ? }

public? static? int part(Comparable[] arr,int l,int r)

{

swap( arr, l, (int)(Math.random()*(r-l+1))+l );

//防止遇到有序隊(duì)時(shí)退化成o（n2），所以隨機(jī)選擇一個(gè)數(shù)作為標(biāo)地

Comparable v = arr[l];

? ? int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v

? ? for(int i = l +1 ; i <= r; i ++ )

if( arr[i].compareTo(v) <0 ){

j ++;

? ? ? ? ? ? swap(arr, j, i);

? ? ? ? }

swap(arr, l, j);

? ? return j;

}

private static void swap(Object[] arr, int i, int j) {

Object t = arr[i];

? ? ? ? arr[i] = arr[j];

? ? ? ? arr[j] = t;

? ? }

}