排序算法之快速排序

基本思想：
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

1.任取一个元素 (如第一个) 为中心

2.所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表

3.对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个

划分过程中的实例：

算法分析：

平均计算时间是O(nlog2n),就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个

时间效率: O(nlog2n) ,每趟确定的元素呈指数增加

空间效率: O(log2n),递归要用到栈空间

稳 定 性: 不稳定 ,可选任一元素为支点

代码实现：

import java.util.Random;

public class Quicksort {
    public static void main(String[] args) {
    int a[]=new int[10];     //声明创建长度为10的一维数组
    Random ran=new Random();
    int i;

    //生成随机数组并输出
    for(i=0;i<a.length;i++)
    {
        a[i]=ran.nextInt(1000)+1;       // 把范围为1-1000的随机整数复制给a[i]
        System.out.print(a[i]+" ");     // 输出a[i]
    } 
    System.out.println();

    quickSort(a,0,a.length-1);
    System.out.println("快速排序后：");

    for(int j:a)   //遍历排序后的数组            
    {
        System.out.print(j+" ");
    }

  }

    public static void quickSort(int a[],int l,int r)
    {
        int i,j,temp;
        if(l>=r) return ;  //只有一个记录或者无记录，则无需排序
        i=l;
        j=r;
        temp=a[i];   //取a[i]为基准数     
        while(i!=j)
        {
            while(i<j&&a[j]>=temp) //找比基准数temp小的数
            {

                j--;
            }

            if(i<j)         
            a[i++]=a[j];        
            while(i<j&&a[i]<=temp)  //找比基准数temp大的数
            {
                 i++;

            }
            if(i<j)
            a[j--]=a[i];
        }
        a[i]=temp;              //i为基准数temp放入的位置
    quickSort(a,l,i-1);       //递归调用
    quickSort(a,i+1,r);

    }
}