import java.util.*; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; public class SortMain { public static void main(String[] args) throws Exception{ Integer threadNumber = 4; //线程数量 Integer stopNumber = threadNumber; //闭合器数量 Integer randomCount = 50; //随机数数量 Integer randomNumber = 50; //随机数范围 List workSpeace = new ArrayList<>(); //每个线程需要工作的量 list的长度与线程量一样 if(randomCount % threadNumber == 0){ for(int i=0; i < threadNumber; i ++){ workSpeace.add(randomCount/threadNumber); } }else{ Integer itemValue = randomCount/threadNumber; for(int i = 0 ; i < threadNumber ; i ++){ if(i == threadNumber -1){ workSpeace.add((randomCount-(itemValue*threadNumber)) + itemValue); }else{ workSpeace.add(itemValue); } } } CountDownLatch countDownLatch = new CountDownLatch(stopNumber); //闭合器子线程闭合器 CountDownLatch countDownLatchMain = new CountDownLatch(stopNumber); //主线程闭合器 ExecutorService executors = Executors.newFixedThreadPool(threadNumber); //线程池 Lock lock = new ReentrantLock(); List arrayList = new ArrayList<>(); Random random = new Random(System.currentTimeMillis()); try { for(int i=0; i < randomCount ; i++){ arrayList.add(random.nextInt(randomNumber)); } System.out.println("随机数集合:"+arrayList +" 长度:"+arrayList.size()); Map thradValueMap = Collections.synchronizedMap(new HashMap()); Map > mainValueMap = Collections.synchronizedMap(new HashMap()); List countSizeListValue = new ArrayList(); // for(int i =0; i paramsList = new ArrayList(); //每个线程工作的内容 //思路：每个线程干10个值，10个线程干100个值 int startIndex; //没个线程工作的10个值的尾坐标，也是没个线程管理数值的结束 //startIndex endThreadIndex 因为for循环是反着的，所以这个值也是反着的 int endThreadIndex; //没个线程工作的10个值的头坐标，也是没个线程管理数值的开始 endThreadIndex = ((randomCount/threadNumber)*finalI); if(finalI == threadNumber-1){ startIndex = ((randomCount - ((randomCount/threadNumber)*finalI)) + endThreadIndex) -1; }else{ startIndex = endThreadIndex + ((randomCount/threadNumber)-1); } for(int forStartIndex = startIndex; forStartIndex >= endThreadIndex; forStartIndex--){ paramsList.add(arrayList.get(forStartIndex)); //通过循环拿到每个线程需要工作的内容 } //由于已知随机数最大的值是100,所以可以很容易的规范没个线程所管理的值范围，在这里暂定 1号线程工作范围为0-10.2号线程为11-20,以此类推 //start 此代码块规定此线程管理值的区间 int theManageValueMax; int theManageValueMin; if(finalI == threadNumber-1){//9 theManageValueMax = startIndex+1; theManageValueMin = endThreadIndex; }else{ theManageValueMax = startIndex; theManageValueMin = endThreadIndex; } List discardValue = new ArrayList<>(); //需要剔除的值的集合 for(int chickIndex = 0; chickIndex < workSpeace.get(finalI); chickIndex++){ //循环判断每个线程需要工作内容值 Integer workValue = paramsList.get(chickIndex); //每个线程工作的基本单位（数值） if(theManageValueMin <= workValue&&workValue <= theManageValueMax){ //如果符合工作数值区间，则什么都不做; continue; }else{ //如果不符合工作区间，则剔除到公共区域 Integer thisNumberParent = -1; try { lock.lockInterruptibly(); thisNumberParent = chickNumberParent(threadNumber, randomNumber, workValue); //调用此方法判断此随机数属于哪个线程的工作区间 }catch (Exception e){ for(StackTraceElement itemError : e.getStackTrace()){ System.out.println(itemError); } }finally { lock.unlock(); } String theValueByMap = thradValueMap.get(thisNumberParent); if(theValueByMap == null || "".equals(theValueByMap)){ thradValueMap.put(thisNumberParent,workValue.toString()); }else{ thradValueMap.put(thisNumberParent,theValueByMap + ","+workValue.toString()); } discardValue.add(workValue); } } for(Integer itemDiscardvalue :discardValue){ paramsList.remove(new Integer(itemDiscardvalue.intValue())); } countDownLatch.countDown(); try { countDownLatch.await(); String thisThreadWorkValue = thradValueMap.get(finalI); //当所有子线程工作完之后 从公共区域拿出本应该属于自己的值 if(thisThreadWorkValue == null || "".equals(thisThreadWorkValue)){ //如果公共区域没有属于自己的工作值 }else { String thisThreadWorkValueSz[] = thisThreadWorkValue.split(","); for(int i=0; i < thisThreadWorkValueSz.length; i++){ paramsList.add(Integer.valueOf(thisThreadWorkValueSz[i])); } paramsList = sortInt(paramsList); } mainValueMap.put(finalI,paramsList); }catch (Exception e){ e.fillInStackTrace(); }finally { countDownLatchMain.countDown(); } // System.out.println("分割线---------------------------------"); } }); } countDownLatchMain.await(); List finalList = new ArrayList<>(); for(int i =0; i itemList = mainValueMap.get(i); if(itemList == null || itemList.isEmpty()){ continue; } for(Integer itemValue : itemList){ finalList.add(itemValue); } } System.out.println("排序好的值:"+finalList+" 长度:"+finalList.size()); arrayList.removeAll(finalList); System.out.println("差集为:"+arrayList); }catch (Exception e){ for(StackTraceElement itemError :e.getStackTrace()){ System.out.println(itemError); } }finally { executors.shutdownNow(); } } /** * * @param paramsList 每个线程要干的事情...排序 * @return */ private static List sortInt(List paramsList){ List resutList = new LinkedList<>(); for(int paramsListIndex = 0 ; paramsListIndex = 0 ; resultListIndex--){ if(resultListIndex == 0){ resutList.add(resultListIndex,paramsList.get(paramsListIndex)); break; } int paramsListInt = paramsList.get(paramsListIndex).intValue(); int resultListInt = resutList.get(resultListIndex-1).intValue(); if(paramsListInt <= resultListInt){ continue; }else{ resutList.add(resultListIndex,paramsList.get(paramsListIndex)); break; } } } return resutList; } /** * 判断该数值在map中的key应该是多少 * @param threadNumber 线程量 * @param randomNumber 随机数范围 * @param needChickNumber 需要判断的值 * @return */ private static Integer chickNumberParent(Integer threadNumber,Integer randomNumber,Integer needChickNumber){ Integer onlyThreadNumber = randomNumber/threadNumber; //单个线程负责值得区间， 比如 93个随机数 6个线程， 那么93/6 就是前五个的线程负责量，余数是最后一个线程负责量 Integer valueIndex = needChickNumber / onlyThreadNumber; //还以上一行注释为例子， 如果现在需要判断93这个值属于哪个线程的工作区间，则 93/（随机数数量/线程量） 93/15 = 6, 因为线程量一共为6,在list中长度最大值为5（因为list坐标从0开始），所以93这个值属于最后一个线程的工作区间 if(valueIndex >= threadNumber){ return valueIndex-1; }else{ return valueIndex; } } }