快速排序

快速排序也是nlogn的算法，而且它在面对完全无序时是比归并排序快的，但是它面对完全有序，或者重复数多的数组又显得无力退化到n2.

下面我们来介绍一下快速排序

主要使用递归

选择第一个点作为比较点，小于该点的数放在该点的左边，大于该点的数放在该点的右边

如果第i个元素比v大的话，就i++ 如果第i个元素比v小的话，就会将第i个元素与j+1元素交换 最后将l处的v元素与第j个元素交换位置

算法实现：

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 );

//防止遇到有序队时退化成o（n2），所以随机选择一个数作为标地

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;

    }

}

---