本帖最后由 李连闯 于 2012-11-1 17:17 编辑
- import java.util.concurrent.CountDownLatch;
- import java.util.concurrent.ExecutorService;
- import java.util.concurrent.Executors;
- /**
- 今天的题目:模拟运动员赛跑计时器。
- 定义一个数组
- {58,56,3,8,22,59,10,60,4,40,52,14,37,26,53,15,43,38,18,49,33,21,5,23,41,45,13,27,55,
- 29,30,7,50,32,20,47,35,48,12,17,39,9,24,42,16,44,25,46,34,36,19,31,51,6,11,54,28,2,57,1} .
- 以三名运动员对这个数组排序为例,
- 三名运动员分别代表的是选择排序,冒泡排序,快速排序。设计计时器,记录他们所用的时间。
- 为了达到三名运动员同时跑,可以设定前一个要等后一个1纳秒
- 注:该加注释的地方要加注释 请附带结果图
- * @author Lian
- *
- */
- public class MyTimerCounter {
- public static void main(String[] args) {
- int[] data = {58,56,3,8,22,59,10,60,4,40,52,14,37,26,53,15,43,38,18,49,33,21,5,23,
- 41,45,13,27,55,29,30,7,50,32,20,47,35,48,12,17,39,9,24,42,16,44,25,
- 46,34,36,19,31,51,6,11,54,28,2,57,1};
- System.out.println("原始排序: ");
- SortUtil.printArray(data);//打印一开始的数据
- Runnable command = null;
- ExecutorService pool = Executors.newCachedThreadPool();
- final CountDownLatch order = new CountDownLatch(1);
- int counter = 3;//要创建的运动员数目
- for(int i=0; i<counter; i++){//这里分配了3个线程,0-冒泡,1-选择,2-快速
- final int count = i;
- command = new Runnable(){
- @Override
- public void run(){
- int[] data = {58,56,3,8,22,59,10,60,4,40,52,14,37,26,53,15,43,38,18,49,33,21,5,23,
- 41,45,13,27,55,29,30,7,50,32,20,47,35,48,12,17,39,9,24,42,16,44,25,
- 46,34,36,19,31,51,6,11,54,28,2,57,1};
- //比赛过程 排序 打印时间等
- MyTimerCounter.race(order, count, data);
- }
- };
- //执行
- pool.execute(command);
- }
- try {
- Thread.sleep(0,1);
- order.countDown();//计数器归零 等待的线程开始执行
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- pool.shutdown();
- }
- //主要执行部分
- public static void race(final CountDownLatch order, final int count, int[] data) {
- String name = null;
- switch(count){
- case 0:name="运动员-冒泡";
- break;
- case 1:name="运动员-选择";
- break;
- case 2:name="运动员-快速";
- break;
- }
- System.out.println(name+",准备开跑...");
- try {
- order.await();//等待执行
- }
- catch (InterruptedException e) {
- e.printStackTrace();
- }
- long begin = System.nanoTime();
- switch(count){
- case 0:data = SortUtil.bubbleSort(data);
- break;
- case 1:data = SortUtil.selectionSort(data);
- break;
- case 2:data = SortUtil.quickSort(data,0,data.length);
- break;
- }
- long end = System.nanoTime();
- //打印排序后的结果
- SortUtil.printArray(data,name,begin,end);
- }
- }
- class SortUtil{
- //冒泡排序
- public static int[] bubbleSort(int[] data){
- for(int i=0; i<data.length; i++){
- for(int j=i ; j<data.length; j++){
- if(data[j]<data[i]) swap(data, i, j);
- }
- }
- return data;
- }
- //选择排序
- public static int[] selectionSort(int[] data){
- int minIndex;
- for (int i=0; i<data.length; i++) {
- minIndex = i;//假设每轮第一个元素为最小元素
- //从每轮比较的开始元素的下一元素开始循环,因为自己没必要和自己比
- for (int j=i+1;j<data.length; j++) {
- //如果有比当前data[minIndex]更小的元素,则将该元素索引的值j替换minIndex,
- //保证 minIndex存放的是本轮数组最小值的索引值
- if (data[j]<data[minIndex]) {
- minIndex = j;
- }
- }
- //当最小元素索引确定后,则把该索引位置与本轮比较开始位置的数组数字相交换
- swap(data, i, minIndex);
- }
- return data;
- }
- //快速排序
- public static int[] quickSort(int[] data,int left,int right){
- int i = left;
- int j = right;
- int flag = data[left]; //选一个数作为比较的基准数字 小的放左边,大的放右边(先分然后把基准数字挪到中间) 通常选择的是第一个
- while(true)
- {
- //从第二个数开始找大于基准数字的数 ,从前面开始找大于flag(即data[left])的数,
- //如果data[i]>flag(即data[left]),循环结束,得到的i即为第一个大于基准数字flag的数字的数组索引;
- while((++i)<right-1 && data[i]<flag);
- //从最后一个数开始找第一个小于基准数字flag(即data[left])的数
- //如果data[i]<flag,循环结束,得到的i即为第一个小于基准数字flag的数字的数组索引;
- while((--j)>left && data[j]>flag);
- //如果从左右两边寻找的数组索引位置出现了交叉的话,就说明根据基准数字分开的大小两份已经分好了(可以根据打印结果来看)
- //于是一次排序的循环过程结束,跳出循环后,将基准数字挪到分好的两组数字的中间
- if(i>=j) break;
- //交换两边找到的数
- SortUtil.swap(data, i, j);
- //可以自定义个方法用来打印每次排序后的即时排序状况
- //printArray(data);
- }
- //把基准数据放到相对于该基准数字而分的大小两组数字的中间
- swap(data, left, j);
- //递归快排基准数字左边的数据 这时候的基准数据取得是基准数字左边所有数字左起的第一个
- if(left<j)
- quickSort(data,left,j);
- //递归快排基准数字右边的数据 这时候的基准数据取得是基准数字右边所有数字左起的第一个
- if(right>i)
- quickSort(data,i,right);
- return data;
- }
- //数组两位置数字交换方法
- public static void swap(int[] data, int i, int j) {
- int temp = data[i];
- data[i] = data[j];
- data[j] = temp;
- data[i] - data[j];
- }
- //数组值打印方法 有时间
- public synchronized static void printArray(int[] data,String name, long begin,long end){
- System.out.println();
- System.out.println(name+" 到终点的结果:");
- for(int i : data){
- System.out.print(i+",");
- }
- System.out.println();
- System.out.println(name+" 跑完全程 耗时:"+(end-begin)+" 纳秒...");
- }
- //打印数组数字 无时间
- public synchronized static void printArray(int[] data){
- for(int i : data){
- System.out.print(i+",");
- }
- System.out.println();
- }
- }
复制代码 一次运行的打印结果主要截图:
|