十大排序算法详解（三）排序算法的比较与性能分析_不同算法的差异

一、时间复杂度与空间复杂度

  算法是指令的集合，是为解决特定问题而规定的一系列操作。它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。一个算法通
常来说具有以下五个特性：

• 输入：一个算法应以待解决的问题的信息作为输入。
• 输出：输入对应指令集处理后得到的信息。
• 可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。
• 有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。
• 确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定
  输入开始，多次执行同一指令集结果总是相同的。

  在解决某一具体问题时，常常会涉及到不同的算法。此时，就需要用一些指标来评估不同算法的好坏，常用的指标有两个：时间复杂度和空间复杂度，相比之下，时间复杂度更为常用一些。

1.1 时间复杂度

  时间复杂度主要用来衡量一个算法运行所需要的时间，理论上这个时间受限于硬件、数据输入、数据输出因素等影响，必须要实际运行才能知道这个时间。所以此时就需要用一种估算的方式，来衡量真正的算法运行所需要的时间。
  一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。为了表示输入规模n和时间频度T(n)的关系，引入了时间复杂度的概念。
  若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

• 大O表示法
    时间复杂度有不同的表示方式，常用的是大O表示法，大O表示方法的计算步骤：

1>用常数1取代运行时间中的所有加法常数。
2>只保留最高阶项。
3>去除最高阶的常数。

  常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。 常见的算法时间复杂度由小到大依次为：O(1) < O(logn) < (n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)。

• 分析时间复杂度的几种方法
    1）计算循环次数。运行时间往往都是集中在循环中，循环之外往往是一些简单的具有常数基本操作的运算，而这些常数次的基本操作在渐进时间复杂度中是不起作用的。这就使得运行时间往往和循环的次数具有相同的阶。下面的常见复杂度例子中的时间复杂度就是用循环次数来计算的。
    2）分析最高频度的基本操作。在某些算法中，使用统计循环次数的方法来完成算法时间复杂度的估算是非常复杂的，有时甚至是无法完成的。比如：将两个已经有序的数组 a[0,m-1]，b[0,n-1]合并为一个更大的有序数组。合并两个数组的算法是使用两个变量 pa，pb 初始时分别指向数组 a、b 的第一个元素，每次比较 a[pa]与 b[pb]，将小的放入新的数组 c。更新指向小元素的变量，使之加 1，指向后续元素。这个过程一直进行下去，直到将某个数组中的所有元素放入新的数组为止。此时再将另一个数组中剩余的数据元素依次放入新数组。示例：

	public int[] merge (int[] a, int[] b) {
		int pa = pb = pc = 0;
		int m = a.length;
		int n = b.length;
		int[] c = new int[m+n];
		while (pa<m && pb<n) {
			if (a[pa]<b[pb])
				c[pc++] = a[pa++];
			else
				[pc++] = b[pb++];
		}
		if (pa<m)
			while (pa<m) c[pc++] = a[pa++];
		else
			while (pb<n) c[pc++] = b[pb++];
		return c;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  如果使用分析循环次数的方法来求算法的时间复杂度，在这个例子中会较为复杂，因为这里有三个循环，而每个循环执行的次数会由于输入实例的不同而不同。
  在这里可以使用分析最高频度的基本操作的方法来得到算法merge的时间复杂度。在上面的例子中，主要操作有元素的赋值和比较两种操作，而赋值是使用频度最高的基本操作。因为每个元素都必须要放入新的数组，而并不是每个元素都需要比较才能放入新的数组。在算法中的每个元素至少赋值一次，至多也赋值一次，因此共有m+n次赋值，因此算法 merge 的时间复杂度 T(n) = O(m+n)。

• 常见的复杂度例子(用循环次数分析)
   1、常数时间O(1)

		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
1
2
3

  2、线性时间O(n)

	    for (int num : array) {
	        max = Math.max(max, num);
	        min = Math.min(min, num);
	    }
1
2
3
4

  算法循环体中的代码执行了n次，因此时间复杂度为O(n)。
  3、平方阶时间O(n²)

 for(int i=0;i<n;i++){   
      for(int j=0;j<n;i++){
         //复杂度为O(1)的算法
         ... 
      }
1
2
3
4
5

  4、O(n³)

 for(i=0;i<n;i++){  
       for(j=0;j<i;j++)  {
          for(k=0;k<j;k++)
             x=x+2;  
       }
}
1
2
3
4
5
6

  5、对数阶O(logn)

	int i = 1, n = 100;
	while( i < n )
	{
	    i = i * 2;
	}
1
2
3
4
5

   有x个2相乘后大于或等于n，则会退出循环，于是由2^x = n得到x = log(2)n，所以这个循环的时间复杂度为O(logn)。
  6>线性对数时间O(nlogn)
   常见的是归并排序。

   算法的空间复杂性是以时间复杂性为上界的。这是因为在算法中每访问一次存储空间都是需要使用一定时间的，即使每次访问的都是不同的存储空间，空间的大小也不会超过基本操作次数常数倍，因此算法的空间复杂性是以时间复杂性为上界
的。

1.2 空间复杂度

  算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数，也是一种“渐进表示法”，这些所需要的内存空间通常分为“固定空间内存”（包括基本程序代码、常数、变量等）和“变动空间内存”（随程序运行时而改变大小的使用空间）。

1.3 常用算法的时间复杂度和空间复杂度

  在基数排序中，r代表关键字的基数，d代表长度，n代表关键字的个数。

  从上面可以看出，一些排序的算法是O(n²)，这种算法效率是最差的，为什么呢？因为在某次比较、移动最值的过程中进行的比较操作结果并未记录下来，下次比较、移动最值时，不能复用上次的比较结果。
  拿归并排序来说，上次比较、合并的结果会被保留下来（即上次合并的组内，不会再进行比较），只需要和别的组内数进行比较合并即可。

二、排序算法的类别

  关于排序算法的分类，如下：

三、排序算法的综合比较

  关于排序算法的总体比较，见于下表：

四、排序算法的性能比较

  可以用生成固定长度的数组，数组内为固定范围的随机数。对该数组进行排序，来对比检测排序算法的性能，测试代码如下：

public class AllSort {
	public static void main(String[] args) {
		int arrayNum = 50;
		int arrayMax = 50;
		long start = 0L;
		long end = 0L;
		
		int[ ] array = createArray(arrayNum,arrayMax);
		int[ ] array1 = array;
		int[ ] array2 = array;
		int[ ] array3 = array;
		int[ ] array4 = array;
		int[ ] array5 = array;
		int[ ] array6 = array;
		int[ ] array7 = array;
		int[ ] array8 = array;
		int[ ] array9 = array;
		int[ ] array10 = array;
		
		start = System.currentTimeMillis();
		bubbleSort(array1);
		end = System.currentTimeMillis();
		System.out.println("1.冒泡排序所花费的时间"+(end-start)+"ms,冒泡排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array1.length;i++)
			System.out.print(array1[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		quickSort(array2,0,array2.length-1);
		end = System.currentTimeMillis();
		System.out.println("2.快速排序所花费的时间"+(end-start)+"ms,快速排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array2.length;i++)
			System.out.print(array2[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		insertionSort(array3,array3.length-1);
		end = System.currentTimeMillis();
		System.out.println("3.插入排序所花费的时间"+(end-start)+"ms,插入排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array3.length;i++)
			System.out.print(array3[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		shellSort(array4,array4.length-1);
		end = System.currentTimeMillis();
		System.out.println("4.希尔排序所花费的时间"+(end-start)+"ms,希尔排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array4.length;i++)
			System.out.print(array4[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		selectSort(array5,array5.length-1);
		end = System.currentTimeMillis();
		System.out.println("5.选择排序所花费的时间"+(end-start)+"ms,选择排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array5.length;i++)
			System.out.print(array5[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		mergeSort(array6,array6.clone(),0,array6.length-1);
		end = System.currentTimeMillis();
		System.out.println("6.归并排序所花费的时间"+(end-start)+"ms,归并排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array6.length;i++)
			System.out.print(array6[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		heapSort(array7);
		end = System.currentTimeMillis();
		System.out.println("7.堆排序所花费的时间"+(end-start)+"ms,堆排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array7.length;i++)
			System.out.print(array7[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		array = countSort(array8);
		end = System.currentTimeMillis();
		System.out.println("8.计数排序所花费的时间"+(end-start)+"ms,计数排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array8.length;i++)
			System.out.print(array8[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		bucketSort(array9);
		end = System.currentTimeMillis();
		System.out.println("9.桶排序所花费的时间"+(end-start)+"ms,桶排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array9.length;i++)
			System.out.print(array9[i]+" ");
		System.out.println("\n");
		
		start = System.currentTimeMillis();
		basicSort(array10);
		end = System.currentTimeMillis();
		System.out.println("10.基数排序所花费的时间"+(end-start)+"ms,基数排序后的数组为：");
		System.out.print("  ");
		for(int i=0;i<array10.length;i++)
			System.out.print(array10[i]+" ");
		System.out.println("\n");
		
		
	}
	
	/*生成测试数组，number为数组元素数量，max为数组元素最大值*/
	static int[] createArray(int number,int max){
		int[] array = new int[number];
        Random rand = new Random();
		for(int i=0;i<array.length;i++){
			array[i] = rand.nextInt(max); 
		}
		return array;
	}
	
	/*1.冒泡排序*/
	static void bubbleSort(int[] array) {
        int arrayLength = array.length;
        
        int preIndex = 0;
        int backIndex = arrayLength - 1;
        while(preIndex < backIndex) {
            preSort(array, arrayLength, preIndex);
            preIndex++;
            
            if (preIndex >= backIndex) {
                break;
            }
            
            backSort(array, backIndex);
            backIndex--;
        }
    }
    
    // 从前向后排序
	static void preSort(int[] array, int length, int preIndex) {
        for (int i = preIndex + 1; i < length; i++) {
            if (array[preIndex] > array[i]) {
                swap(array, preIndex, i);
            }
        }
    }
    
    // 从后向前排序
	static void backSort(int[] array, int backIndex) {
        for (int i = backIndex - 1; i >= 0; i--) {
            if (array[i] > array[backIndex]) {
                swap(array, i, backIndex);
            }
        }
    }
	
	/*2.快速排序*/
	static void quickSort(int[] arr, int startIndex, int endIndex) {
		/*当startIndex大于等于endIndex时，不再递归*/
		if (startIndex >= endIndex) {
		    return;
		}
		/*得到基准元素位置*/
		int keyIndex = divide(arr, startIndex, endIndex);
		/*递归处理基准的左右两部分*/
		quickSort(arr, startIndex, keyIndex - 1);
		quickSort(arr, keyIndex + 1, endIndex);
    }
	
	static int divide(int[] arr, int startIndex, int endIndex) {
		/*取第一个位置的元素作为基准元素*/
		int key = arr[startIndex];
		int left = startIndex;
		int right = endIndex;
		/*坑的位置，初始等于key的位置*/
		int index = startIndex;
		
		/*当right大于等于left时，执行循环*/
		while (right >= left){
		   /*right指针从右向左进行比较*/
		   while (right >= left) {
		      if (arr[right] < key) {
		    	  /*最右边的元素覆盖原来坑中的值*/
		          arr[left] = arr[right];
		          /*坑的位置改变，变成最右边元素对应的索引*/
		          index = right;
		          /*left索引右移，因为原来的值已被right索引的值所覆盖*/
	              left++;
		          break;
		      }
		      /*最右边的元素参与比较，无论是否参与与坑中元素的交换，都左移，不再参与下一轮的比较*/
		      right--;
		   }
		   
		   /*left指针从左向右进行比较*/
		   while (right >= left) {
		      if (arr[left] > key) {
		         arr[right] = arr[left];
		         index = left;
		         right--;
		         break;
		      }
		      left++;
		   }
		}
		
		/*将基准元素放在index位置，也就是大小元素放在其前后的中间位置*/
		arr[index] = key;
		return index;
	}
	
	/*3.2-路插入排序*/
	static void insertionSort(int[] arr,int len) {
        int j, first, last, mid;
        /*临时数组*/
        int[ ] tempArr =new int[len];        
        tempArr[0] = arr[0];
        /*first和last分别指临时数组tempArr中排好序的元素的第一个和最后一个位置*/
        first = last = 0;       

        for(int i = 1; i<len; i++){
        	/*j 是调整系数*/
            if(first > last){
                j = len;        
            }else{
                j = 0;
            }
            /*tempArr中间元素的位置*/
            mid = ((first+last+j)/2)%len; 
            /*arr[i]应该插入在tempArr的前半部分*/
            if(arr[i] < tempArr[mid]){      
            	/*j指向tempArr数组中的第一个元素*/
                j = first;    
                /*first 前移，取余是为了实现循环数组效果*/
                first = (first-1+len)%len;  
                /*待插元素大于 j 所指元素*/
                while(arr[i] > tempArr[j]){    
                	/*j 所指元素前移，取余是为了实现循环数组效果*/
                	tempArr[(j-1+len)%len] = tempArr[j];  
                	/*j 指向下一个元素*/
                    j = j+1;               
                }
                /*移动结束，待插元素插在tempArr[j]前*/
                tempArr[(j-1+len)%len] = arr[i];    
            /*arr[i]应该插入在tempArr的后半部分*/
            }else{   
            	/*j指向tempArr数组中的最后一个元素*/
                j = last;    
                /*last后移， 指向插入后的最后一个元素*/
                last++;            
                /*待插元素小于 j 所指元素*/
                while(arr[i] < tempArr[j]){  
                	/*j 所指元素后移*/
                	tempArr[(j+1)%len] = tempArr[j]; 
                	/*j 指向上一个元素*/
                    j = (j-1+len)%len;         
                }
                /*移动结束，待插元素插在tempArr[j]后*/
                tempArr[(j+1)%len] = arr[i]; 
            }
        }
        
        /*把在tempArr中排好序的元素依次赋给arr*/
        for(int i = 0; i < len; i++){                    
        	arr[i] = tempArr[(first+i)%len];
        }
    }	
	
	/*4.希尔排序*/
	static void shellSort(int[] arr, int len) {
		   /*初始化划分增量*/
		   int increment = len;	
		   int j,temp,low,mid,high;
		   /*每次减小增量，直到increment = 1*/
		   while (increment > 1){	
			  /*增量的取法之一：除三向下取整+1*/
			  increment = increment/3 + 1;
			  /*对每个按增量划分后的逻辑分组，进行直接插入排序*/
			  for (int i = increment; i < len; ++i) {	
				 low = 0;
				 high = i-1;
				 temp = arr[i];
		         while(low <= high){
		            mid = (low+high)/2;
		            if(arr[mid]>temp){
		                high = mid-1;
		            }else{
		                low = mid+1;
		            }
		         }
		         j = i-increment;
			     /*移动元素并寻找位置*/
				 while(j >= high+1){	
					arr[j+increment] = arr[j];
					j -= increment;
				 } 
				 /*插入元素*/
				 arr[j+increment] = temp;	
			  }
		   } 
	    }
	
	/*5.选择排序*/
	static void selectSort(int[] arr, int len) {
        /*初始化左端、右端元素索引*/
	    int left = 0;
	    int right = len - 1;
	    while (left < right){
	    	/*初始化最小值、最大值元素的索引*/
	        int min = left;
	        int max = right;
	        for (int i = left; i <= right; i++){
	        	/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
	            if (arr[i] < arr[min])
	                min = i;
	            if (arr[i] > arr[max])
	                max = i;
	        }
	        /*最大值放在最右端*/
	        int temp = arr[max];
	        arr[max] = arr[right];
	        arr[right] = temp;
	        /*此处是先排最大值的位置，所以得考虑最小值（arr[min]）在最大位置（right）的情况*/
	        if (min == right)
	            min = max;
	        /*最小值放在最左端*/
	        temp = arr[min];
	        arr[min] = arr[left];
	        arr[left] = temp;
	        /*每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1*/
	        left++;
	        right--;
	    }
	}
	
	/*6.归并排序算法*/
	static void mergeSort (int a[], int temp[], int start,int end) {
		if(end > start){
	        int mid =  start+(end-start)/2;  
	        /*对左右子序列递归*/
	        mergeSort(temp, a,start,mid);  
	        mergeSort(temp, a,mid+1,end);  
	        /*合并左右子数组*/
	        merge(a, temp, start,mid,end);  
		}
	}
		 
	static void merge (int arr[],int temp[],int start,int mid,int end) {
		/*左边子序列的头元素*/
		int i = start; 
		/*右边子序列的头元素*/
	    int j = mid+1;
	    
	    for(int k = start;k <= end;k++){
	      if(i>mid){
	    	  /*左边子序列元素用尽*/
	    	  arr[k] = temp[j++]; 
	      }else if(j>end){
	    	  /*右边子序列元素用尽*/
	    	  arr[k] = temp[i++]; 
	      }else if(temp[j]<temp[i]){
	    	  /*右边子序列当前元素小于左边子序列当前元素， 取右半边元素*/
	    	  arr[k] = temp[j++]; 
	      }else {
	    	  /*右边子序列当前元素大于等于左边子序列当前元素，取左半边元素*/
	    	  arr[k] = temp[i++]; 
	      }
	    }
    }
	
	/*7.堆排序*/
	static void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		
		/*构建大顶堆(假设按升序方式排列)，这里其实就是把原来的数
		 * 组，变成一个按大顶堆结构排列的数组
		 */
		buildMaxHeap(arr);
		/*将堆顶元素与最后一一个元素交换，总个数-1，重置大顶堆*/
		for (int i = len - 1; i > 0; i--) {
			swap(arr, 0, i);
			len--;
			heapify(arr, 0, len);
		}
	}
	 
	static void buildMaxHeap(int[] arr) {
	    for (int i = 0; i < arr.length; i++) {
	       int currentIndex = i;
	       /*父结点索引*/
	       int fatherIndex = (currentIndex - 1) / 2;
	       /*如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
	        *然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
	        */
	       while (arr[currentIndex] > arr[fatherIndex]) {
	           /*交换当前结点与父结点的值*/
	           swap(arr, currentIndex, fatherIndex);
	           /*将当前索引指向父索引*/
	           currentIndex = fatherIndex;
	           /*重新计算当前索引的父索引*/
	           fatherIndex = (currentIndex - 1) / 2;
	        }
	     }
	}
	 
	static void heapify(int[] arr, int i, int len) {
		/*先根据堆性质，找出它左右节点的索引*/
		int left = 2*i+1;
		int right = 2*i+2;
		/*默认当前节点（父节点）是最大值*/
		int largestIndex = i;
		if (left < len && arr[left] > arr[largestIndex]) {
			/*如果左边子结点的值更大，更新最大值的索引*/
			largestIndex = left;
		}
		if (right < len && arr[right] > arr[largestIndex]) {
			/*如果右边子结点的值更大，更新最大值的索引*/
			largestIndex = right;
		}
	 	if (largestIndex != i) {
			/*如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换*/
			swap(arr, i, largestIndex);
			/*互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整*/
			heapify(arr, largestIndex, len);
		}
	}
	 
	static void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	/*8.计数排序*/
	static int[] countSort(int[] array) {
	    // 找出原始数组array中的最大值、最小值
	    int max = 0;
	    int min = 0;
	    for (int num : array) {
	        max = Math.max(max, num);
	        min = Math.min(min, num);
	    }
	    /*初始化计数数组count，长度为最大值减最小值加1*/
	    int[] count = new int[max-min+1];
	    /*对计数数组各元素赋值*/
	    for (int num : array) {
	        /*array中的元素要减去最小值，再作为新索引*/
	        count[num-min]++;
	    }
	    /*计数数组变形，新元素的值是前面元素累加之和的值*/
	    for (int i=1; i<count.length; i++) {
	        count[i] += count[i-1];
	    }
	    /*结果数组*/
	    int[] result = new int[array.length];
	    /*遍历array中的元素，填充到结果数组中去，从后往前遍历*/
	    for (int j=array.length-1; j>=0; j--) {
	    	/*计数数组下标*/
	    	int countIndex = array[j]-min;
	    	/*结果数组下标*/
	    	int resultIndex = count[countIndex]-1;
	        result[resultIndex] = array[j];
	        count[countIndex]--;
	    }
	    return result;
	}

	/*9.桶排序*/
	static void bucketSort(int[] arr){
	    /*计算最大值与最小值*/
	    int max = 0;
	    int min = 0;
	    for(int i = 0; i < arr.length; i++){
	        max = Math.max(max, arr[i]);
	        min = Math.min(min, arr[i]);
	    }
	    
	    /*计算桶的数量*/
	    int bucketNum = (max-min)/arr.length+1;
	    /*用ArrayList组织对应的桶*/
	    List<ArrayList<Integer>> bucketArr = new ArrayList<ArrayList<Integer>>(bucketNum);
	    for(int i = 0;i<bucketNum;i++){
	        bucketArr.add(new ArrayList<Integer>());
	    }
	    
	    /*将每个元素放入对应的桶*/
	    for(int i = 0; i<arr.length;i++){
	    	/*找元素对应的桶*/
	        int num = (arr[i]-min)/(arr.length);
	        /*在同种放入对应的元素*/
	        bucketArr.get(num).add(arr[i]);
	    }
	    
	    /*对每个桶内的元素进行排序*/
	    for(int i = 0; i<bucketArr.size();i++){
	        Collections.sort(bucketArr.get(i));
	    }
	    
	    /*将桶中的元素赋值到原始数组arr*/
		for(int i = 0,index = 0; i < bucketArr.size(); i++){
			for(int j = 0; j < bucketArr.get(i).size(); j++){
				arr[index++] = bucketArr.get(i).get(j);
			}
		}  
	}
	
	/*10.基数排序*/
	static void basicSort (int[] array){
        //获取最大值；要看排几次，主要看这个最大值有几位；
        int max = 0;
        for (int i=0;i<array.length;i++){
            if (max<array[i]){
                max = array[i];
            }
        }

        //获取最大值位数；
        int times = 0;
        while (max>0){
            max/=10;times++;//求取这个最大值的位数，依次除以10；直到为0；
        }
        List<ArrayList> queue = new ArrayList<ArrayList>();//多维数组
        for (int i=0;i<10;i++){
            ArrayList q = new ArrayList();
                queue.add(q);//由于数字的特殊性，大数组中要添加10个小数组；
        }

        //开始比较,重点
        for (int i=0;i<times;i++){
            for (int j=0;j<array.length;j++){
                //获取每次要比较的那个数字；不管是哪个位置上的；
                //获取对应位的值（i为0是个位，1是十位，2是百位）；
                int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                ArrayList q = queue.get(x);
               //把元素添加至对应下标数组；在小数组中添加原array的数值；
                q.add(array[j]); 
                queue.set(x, q);
            }
            //开始收集；
            int count = 0;
            for (int j =0;j<10;j++){
                while (queue.get(j).size()>0){
                    ArrayList<Integer> q = queue.get(j);//拿到每一个数组；
                    array[count] = q.get(0);
                    q.remove(0);
                    count++;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557

  测试结果如下：