java排序算法（五）：快速排序

2018-06-18 03:09:02来源：未知阅读 ()

java排序算法（五）：快速排序

　　快速排序是一个速度非常快的交换排序算法，它的基本思路很简单，从待排的数据序列中任取一个数据（如第一个数据）作为分界值，所有比它小的元素放到左边。所有比它大的元素放到右边。经过这样一趟下来，该序列形成左右两个子序列，左边序列中的数据元素的值都比分界值小，右边序列中数据元素的值都比分界值大。接下来对左右两个序列进行递归排序。对两个子序列重新选择中心元素并依此规则调整。直到每个元素子表的元素只剩下一个元素则排序成功

　　思路

　　1、定义一个变量 i变量从左边第一个索引开始，找大于分界值的元素的索引，并用i来记录它。

　　2、定义一个j变量，j变量从右边第一个索引开始，找小于分界值的元素的索引，并用j来记录它。

　　3、如果i < j,交换i、j两个索引处的元素

　　重复执行以上1、2、3步骤，直到i>=j,可以判断j左边的数据元素都小于分界值，j右边的数据元素都大于分界值，最后将分界值j索引处的元素交换即可

　　时间复杂度

　　最好情况（每次总是选到中间值枢轴）Tn = o(nlogn)

　　最坏情况：（每次总是选到最小或者最大元素作为枢轴）

　　做n-1趟，每次比较n-i次。总的比较次数最大；[o(n2)]

　　平均时间复杂度是T(n) = o(logn)

　　代码实现

package com.spring.test;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.awt.print.PrinterGraphics;

/**
 * 快速排序
 */
public class QuickSortTest {
    public static void main(String[] args) {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        print(data);
        quickSort(data,0,data.length-1);
        System.out.println("排序后的数组");
        print(data);

    }

    /**
     * 快速排序
     * @param data
     * @param start
     * @param end
     */
    public static void quickSort(int[] data,int start,int end){
        if(start >= end){
            return;
        }
        //以起始索引为临界点
        int point = data[start];
        int i = start + 1;
        int j = end;
        while(true){
            while(i<end && data[i] < point){
                i++;
            }
            while(i> start && data[j] > point){
                j--;
            }
            if(i < j){
                swap(data,i,j);
            }else{
                break;
            }
        }
        //交换j和分界点的值
        swap(data,start,j);
        print(data);
        //递归在子序列
        quickSort(data,start,j-1);
        quickSort(data,j+1,end);
    }

    /**
     * 交换数据
     */
    public static void swap(int[] data,int i,int j){
        if(i==j){
            return;
        }
        data[i] = data[i]+data[j];
        data[j] = data[i]-data[j];
        data[i] = data[i]-data[j];
    }

    /**
     * 打印输出
     */
    public static void print(int[] data){
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+"\t");
        }
        System.out.println();
    }
}