並べ替えアルゴリズムjava 2-基数並べ替え、並べ替え

1、基数の並べ替え――基本的な実現思想：まず、配列中のデータの最大の桁数を判断し、その後、ビット上の数字を比較し、並べ替えを行い、他のビット上の数字を比較して、順番に並べ替えを行う。

/**
	 *     
	 */
	public static void radixSort(int []array){
		
		int max = array[0];//    
		for (int i = 0; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
			}
		}
		
		int time = 0;//      
		while (max > 0) {
			max /= 10;
			time++;
		}
		
		List<ArrayList<Integer>> list = new ArrayList<>();//          0-9      
		for (int i = 0; i < 10; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		//          
		for (int i = 0; i < time; i++) {//          
			for (int j = 0; j < array.length; j++) {
				//               
				int a = array[j] / pow(i);
				int b = a % 10;//        
				list.get(b).add(array[j]);
			}
			//          
			int n = 0;
			for( ArrayList<Integer> arrayList : list){
				
				if (arrayList.size() != 0) {
					
					for(Integer inner : arrayList){
						
						array[n] = inner.intValue();//    
						n++;
					}
					arrayList.clear();
				}
			}
		}
		System.out.println("------" + Arrays.toString(array));
	}
	private static int pow(int n){//   10 n  ，    Math.pow(10，n);
		int value = 1;
		for (int i = 0; i < n; i++) {
			value *= 10;
		}
		return value;
	}
	

 
2、規格と並べ替え、コードの長さを見ないでください。比較的簡単です。gapは1、2、4、8…の変化です。2つの配列の結合後の配列要素の個数の変化に合います。並べ替えは、最初の2つのグループが並べ替えられ、次いで隣接する最初のグループ要素と第2のグループ要素の比較が並べ替えられて1つの配列になり、順次行われます。

/**
	 *     
	 */
	public static void mergeSort(int []array){
		
		//       
		ArrayList<Integer> listLeft = new ArrayList<>();
		//       
		ArrayList<Integer> listRight = new ArrayList<>();
		//           
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int gap = 1; gap < array.length; gap = gap * 2) {
			
			for (int i = 0; i < array.length; i++) {
				
				if (listLeft.size() < gap) {
					
					listLeft.add(array[i]);
				}else {
					if (listRight.size() < gap) {
						
						listRight.add(array[i]);
					}
				}
				if (listLeft.size() == gap && listRight.size() == gap || 									(listLeft.size() == gap && listRight.size() < gap && i == array.length - 1)) {
					
					switchArray(listLeft, listRight, list);
					
					listLeft.clear();
					listRight.clear();
				}
			}
			for (int j = 0; j <list.size(); j++) {
				
				array[j] = list.get(j);
				
			}
			listLeft.clear();
			listRight.clear();
			list.clear();
			System.out.println(Arrays.toString(array));
		}
		
		
	}
	private static void switchArray(ArrayList<Integer> listLeft,ArrayList<Integer> listRight,ArrayList<Integer> list ){
		
		int m = 0;
		int n = 0;
		while (m < listLeft.size() && n < listRight.size()) {
			
			while(m < listLeft.size() && n < listRight.size() && listLeft.get(m) < listRight.get(n)){
				
				list.add(listLeft.get(m));
				m++;
			}
			
			while (n < listRight.size() && m < listLeft.size() && listLeft.get(m) >= listRight.get(n)) {
				
				list.add(listRight.get(n));
				n++;
			}
		}
		
		while (m < listLeft.size()) {//                      ，       
			
			list.add(listLeft.get(m));
			m++;
		}
		
		while (n < listRight.size()) {
			
			list.add(listRight.get(n));
			n++;
		}
	}