快速排序Java实现

王朝学院·作者佚名  2009-11-12
窄屏简体版  字體: |||超大  

package quickSort;

import java.util.Random;

import java.util.Scanner;

public class QuickSort {

public static int n = 0;

public static int[] array = null;

public static void main(String[] args) {

System.out.println("请输入比较的数的个数n: ");

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

array = new int[n];

Random r = new Random();

for(int i=0; i<n;) {

array[i] = r.nextInt(6000);

//System.out.print(array[i] + " ");

i++;

/*if(i%10 == 0) {

System.out.println();

}*/

}

long t = System.currentTimeMillis();

qSort(0, n-1);

System.out.println("排序所用时间为: " + (System.currentTimeMillis() - t) + "ms");

/*System.out.println("排序后的数如下:");

for(int i=0; i<n;) {

System.out.print(array[i] + " ");

i++;

if(i%10 == 0) {

System.out.println();

}

}*/

}

public static void qSort(int p, int r) {

if(p < r) {

int pt = partition(p, r);

qSort(p, pt-1);

qSort(pt+1, r);

}

}

public static int partition(int p, int r) {

int pt = (int) (p + Math.random()*(r-p));//产生处于p和r之间的随机数

int flag = array[pt];

int i=p-1;

int j=r+1;

while(true) {

while(array[++i] > flag);

while(array[--j] < flag);

if(i>=j) break;

int swap = array[i];

array[i] = array[j];

array[j] = swap;

}

array[i] = flag;

return i;

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航