java 快速排序法

欢迎进入Java社区论坛，与200万技术人员互动交流 >>进入

　　快速排序是在冒泡排序的基础上进行的改装，它的原理是经过一趟排序将数据分割成两部分，左边的数据小于右边的数据，然后分别对这两部分数据用同样的原理进行排序，整个排序过程是用递归实现的，下面来看一个例子 package com.lamp.sort;

public class QuickSort{public static void main(String[] args) {int[] data = {5,3,9,2,6,1};sort(data,0,data.length);for (int i = 0; i < data.length; i++) {System.out.println(data[i]);}}/*首先我要找到一个位置的数使得其左边的数字比它要小，右边的数字比它要大开始的时候数组为5，3，9，2，6，1首先从左端下标为++i开始扫描发现3小于5满足条件继续，发现下一个9大于5而此时i的下标值为2不满足条件推出左端扫描的while循环，开始从最右端开始扫描，发现最右端第一个数字就小于5，此时j的值为5，而i此时是小于j的，交换两位置数据，即一轮循环后的数据为5，3，1，2，6，9接着从左端开始继续扫描，当扫描到大于5的值的时候，i的值变为4即6所处位置的下标，当从右端开始扫描时，扫描到小于5的数字时，j的值变为3，而此时i的值大于j的值不满足条件推出最外的while循环,此时数组的数据为5，3，1，2，6，9然后将第一个数和j处下标的数进行互换，数组变为2，3，1，5，6，9这样就达到了预期的目标，即下标为3的数据大于其左边的数据且小于其右边的数据然后以5为分割点对两边的数据用同样的原理进行排序*/ private static void sort(int[] data, int left, int right) {int i = left;int j = right;int middle = data[left];//第一次调用时候我选取要排序的数组的第一个数作为关键数据while(true){while(++i<right-1 && data[i]<middle);while(–j>left && data[j]>middle);if(i >= j){break;} swap(data,i,j); }data[left] = data[j];data[j] = middle;if(left < j){sort(data,left,j);}if(i < right){sort(data,i,right);}}

private static void swap(int[] data, int i, int j) {int temp = data[i];data[i] = data[j];data[j] = temp;}}