数据结构与算法（排序）_算法sort执行的元素的外层循环交换语句中赋值的最多次数是多少

3. 排序

3.1 如何进行选择排序（选择排序）

对于给定的一组记录，经过第一轮比较后得到最小的记录，将该记录与第一个记录位置进行交换；对不包含第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

package paixu;
import java.util.*;
public class XuanZe {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			double[] d = new double[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextDouble();
			}
			int flag = 0;
			double temp = 0.0;
			int k = 0;
			for(int j=0;j<d.length;j++){
				flag = j;
				temp = d[j];
				for(k=j+1;k<d.length;k++){
					if(d[k]<temp){
						flag = k;//比d[j]小的元素下标
						temp = d[k];//比d[j]小的元素与d[j]互换
					}
				}
				if(flag!=j){
					d[flag] = d[j];
					d[j] = temp;
				}
			}
			for(int l=0;l<d.length;l++){
				System.out.print(d[l]+",");
			}
		}
	}

}

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

复杂度分析：
空间复杂度：仅使用常数个辅助单元，空间效率为O（1）
时间复杂度：元素移动次数少，不超过3（n-1）次，最好时移动0次，对应的表已经有序；元素之间比较的次数与序列的初始状态无关，为n（n-1）/2次，时间复杂度为O（n^2）
稳定性：在第i 趟找到最小 元素后，和第i个元素交换，可能会导致第 i个元素与其含有相同关键字元素的相对位置发生改变。所以是不稳定的。

3.2 如何进行插入排序（插入排序）

将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组，把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。这样的话，n个元素需要进行n-1趟排序。
例如我们有一组数字：｛5，2，4，6，1，3｝，我们要将这组数字从小到大进行排列。 我们从第二个数字开始，将其认为是新增加的数字，这样第二个数字只需与其左边的第一个数字比较后排好序；在第三个数字，认为前两个已经排好序的数字为手里整理好的牌，那么只需将第三个数字与前两个数字比较即可；以此类推，直到最后一个数字与前面的所有数字比较结束，插入排序完成。
插入排序的关键点：
1、采用双层循环：时间复杂度也是O（n的平方）
（1）外层循环表示的是排序的趟数，n个数字需要n-1趟，因此，外层循环的次数是n-1次；同时也代表数的位置。
（2）内层循环表示的是每一趟排序的数字。根据插入排序的思想，第i趟排序时，有序数组中的数字就有i个，就需要进行i次比较，因此循环i次。注意采用的是从后往前进行比较。
2、从后往前扫描的时候，如果必须插入的数大于有序数组中当前位置的数，则有序数组中的数和它之后的数均往后移一个位置，否则，把插入的数插入到有序数组中。（稳定排序）
实现步骤：
1、从第一个元素开始，序列中的第一个元素被认为已经排好序了。
2、取下一个元素，在已经排序的元素序列中从后向前扫描。
3、如果该元素（已排序）大于新元素，将该元素移到下一位置。
4、重复步骤3直到找到已排序元素小于或等于新元素的位置。
5、将新元素插入到该位置中。
6、重复步骤2-5。
过程如下图所示：

复杂度分析：
平均时间复杂度：O(N^2)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定
(1) 最好情况：序列已经是升序排列，在这种情况下，需要进行的比较操作需(n-1)次即可。
(2) 最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。
插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(N^2)。
最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
平均的空间复杂度为O(1)

package paixu;
import java.util.*;
public class ChaRu {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			double[] d = new double[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextDouble();
			}
			double temp = 0;
			for(int j=1;j<d.length;j++){
				temp = d[j];
				int k;
				for(k=j-1;k>=0;k--){
					if(d[k]>temp){
						d[k+1] = d[k];
					}else{
						break;
					}
					
				}
				d[k+1] = temp;
			}
			for(int l=0;l<d.length;l++){
				System.out.print(d[l]+",");
			}
		}
	}
}

					
								
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

3.3 如何进行归并排序（归并排序）

归并排序利用递归和分治将数据序列分为越来越小的半子表，再对半子表排序，再用递归方法将排好序的半子表合并成越来越大的有序序列。原理如下：对给定的共n个元素的序列，首先将无序数组划分为数量相等的两部分，然后对每一部分再从中间进行划分，直到每一部分子序列都只有一个元素时停止。 将每两个相邻的长度为1的子序列进行归并，得到n/2（向上取整）个长度为2或1的有序子序列，再将两两归并，反复执行直到得到一个有序序列。因此总共两个步骤：1、划分半子表，2、对两个相邻的元素进行排序，3、合并半子表。

1、迭代法：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入合并后的空间，移动指针到下一个位置。
重复上一步骤直到某一指针到达序列尾。

public static void sort(int[] arr){
	int len = arr.length();
	int [] result=new int[len];
	int end=len-1;
	int start,block;
	for(block=1;block<len*2;block=block*2){
		for(start=0;start<len;start+=block*2){
			int mid=(start+block)<len?(start+block):len;
			int high=(start+block*2)<len?(start+block*2):len;
			int low=start;
			int start1=low,end1=mid;
			int start2=mid+1,,end2=high;
			while(start1<end1&&start2<end2){
				result[low++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2];}
			while(start1<end1){
				retsult[low++]=arr[start1++];}
			while(start2<end2){
				result[low++]=arr[start2++];}
				}
			}
		int[] temp=arr;
		arr=result;
		result=temp;
		}
		result=arr;
		}
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

2、递归法：
将序列每相邻两个元素进行归并操作，形成n/2（向上取整）个序列，排序后每个序列包含两个元素。
将上述序列再次归并，形成n/4（向上取整）个序列，每个序列包含四个元素。
重复上一步骤，直到所有元素排序完。

public static void recurisve(int[]  result,int[] arr,int start,int end){
	if(strat>end){
	return ;
	}
	int mid=(arr.length()+start)/2;
	int start1=start,end1=mid;
	int start2=mind+1,end2=end;
	int r=start;
	while(start1<end1&&start2<end2)
		result[k++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++];
	while(start1<end1)
		result[k++]=arr[start1];
	while(start2<end2)
		result[k++]=arr[start2];
	recurisve(arr,reslut,start1,end1);
	recurisve(arr,reslut,start2,end2);
	for(k=0;k<arr.length();k++)
		arr[k]=result[k];
	}
public static void sort(int[] arr){
	int len=arr.length;
	int[] result=new int[len];
	recurisve(arr,result,start,len-1);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析：
平均时间复杂度：O(nlogn)
最佳时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
排序方式：In-place
稳定性：稳定
不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O( nlogn )
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。

3.4 冒泡排序（交换排序）

冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
实现步骤：
1、比较相邻的元素，如果第一个比第二个大，则交换。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
3、针对所有的元素重复以上步骤，除过最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有热呢一对数要比较。
通过两层循环控制：
第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
第二个循环（内循环），负责两两比较交换。
复杂度分析：
平均时间复杂度：O(N^2)
最佳时间复杂度：O(N)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定
冒泡排序涉及相邻两两数据的比较，故需要嵌套两层 for 循环来控制;
外层循环 n 次，内层最多时循环 n – 1次、最少循环 0 次，平均循环(n-1)/2;
所以循环体内总的比较交换次数为：n*(n-1) / 2 = (n^2-n)/2 ;
按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2) ;
最优的空间复杂度为开始元素已排序，则空间复杂度为 0;
最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);
平均的空间复杂度为O(1) .

package paixu;
import java.util.*;
public class MaoPao {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			double[] d = new double[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextDouble();
			}
			double temp = 0.0;
			for(int j=0;j<d.length;j++){
				for(int k=j+1;k<d.length;k++){
					if(d[k]<d[j]){
						temp = d[j];
						d[j] = d[k];
						d[k] = temp;
					}
				}
			}
			for(int l=0;l<d.length;l++){
				System.out.print(d[l]+",");
			}
		
		}
	}
}

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

3.5 快速排序（交换排序）

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
实现步骤：
1、从数列中挑出一个元素，称为“基准”。
2、重新排序数列，所有元素比基准值小的放在基准前面，所有元素比基准值大的放在基准后面（与基准相同的数可放在任意一侧），在这个分区退出之后，该基准处于数列中间位置。
3、递归将小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
复杂度分析：
平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同

public class sort{
	int tmp;
	int [] arr;
	private void swap(int a,int b){//将两个元素交换
		tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
		}
	private void queick_sort(int start,int end){
		int mid = arr[end];//将序列的最后一个元素设为基准
		if(start>end){
			return null;
		}
		int left = start;
		int right = end-1;
		while(left<right){
			while(arr[left]<mid){//当左侧指针对应的值小于基准值
				left++;//左侧指针右移
				}
			while(arr[right]>mid){//当右侧指针对应的值大于基准值
				right--;//右侧指针左移
				}
			swap(left,right);//当左侧指针对应的值大于右侧指针对应的值，则将两者转换
		if(arr[left]>arr[end]){//当左侧指针对应的元素大于基准值
			swap(left,end);//将两者转换
		else{ 
			left++;}//否则，左侧指针右移
		sort(start,left-1);//分别对基准值两侧的子序列进行排序
		sort(left+1,end);
	private void sort(int [] arrin){
		int [] arr = arrin;
		queick_sort(0,arr.length()-1);
	}
}
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

3.6 希尔排序（插入排序）

希尔排序的实质就是分组插入排序，该方法又称递减增量排序算法，因DL．Shell于1959年提出而得名。希尔排序是非稳定的排序算法。
先将整个待排元素序列分割成若干个子序列，形如 [i i + d, i + 2d,…, i + d]（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

• 实现步骤：
  1、先取一个小于n的整数d1作为第一个增量，将文件中的全部记录分为d1个组。
  2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。
  3、取第二个增量d2小于d1重复上述的分组和排序，直到所取增量dt=1，所有记录在同一组中进行直接插入排序为止。
  希尔提出的增量变化的方法：d1 = n/2, di+1 = Ldi/2」，并且最后 个增量等于1。
  
• 复杂度分析：
  空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
  时间效率 : 希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当 在某个特定范围肘，希尔排序的时间复杂度约为 O(n^1.3)。在最坏情况下希尔 序的时间复杂度为 O(n ^2)。
  稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因 此希尔排序是一种不稳定的排序方法。
  适用性：希尔排序算法仅适用于线性表为顺序存储的情况。
  希尔排序的效率取决于增量值gap的选取，时间复杂度并不是一个定值。开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
  最优的空间复杂度为开始元素已排序，则空间复杂度为 0；最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);平均的空间复杂度为O(1)希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化。比如上面的例子中希尔排序中相等数据5就交换了位置，所以希尔排序是不稳定的算法。

package paixu;
import java.util.*;
public class XiEr {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			double[] d= new double[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextDouble();
			}
			for(int dk=n/2;dk>=1;dk/=2){//步长序列
				for(int j=dk+1;j<=n;++j){//总共划分的组数
					if(d[j]<d[j-dk]){//将d[i]插入到有序增量子表，当每一组中的后一个值小于前一个值
						d[0] = d[j];
						int k;
						for(k=j-dk;k>0&&d[0]<d[k];k-=dk){//则在该组进行插入排序直到该组元素顺序正确
							d[k+dk] = d[k];
						}
						d[k+dk] = d[0];
					}
				}
			}
			for(int l=0;l<d.length;l++){
				System.out.print(d[l]+",");
			}
		}
	}
}

				
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

3.7 堆排序

堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树。

• 堆的性质：
  ① 是一棵完全二叉树
  ② 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。
• 堆的存存储
  一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)。
  
• 堆的操作：
  在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
  ① 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  ② 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  ③ 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

堆排序：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
实现步骤：
① 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
② 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1…n-1]调整为堆。然后再次将R[1…n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1…n-2]和有序区R[n-1…n]，且仍满足关系R[1…n-2].keys≤R[n-1…n].keys，同样要将R[1…n-2]调整为堆。
④ 直到无序区只有一个元素为止。
调整为大顶堆的过程如下所示：

当把堆顶元素87输出后，将最后一个节点的值9放在根节点处并对堆进行调整，重新成为大顶堆。

package paixu;
import java.util.*;
public class DuiPai {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			double[] d = new double[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextDouble();
			}
			HeapSort(d,d.length);
			System.out.print(Arrays.toString(d));
		}
	}
	//创建大顶堆
	public static void BuildMaxHeap(double[] d,int n){
		for(int j=n/2-1;j>=0;j--){//从第n/2个节点开始进行调整
			AdjustHead(d,j,n);
		}
	}
	//调整堆
	public static void AdjustHead(double[] d,int k,int len){
		double ds=d[k];//子树的根节点暂存到d【0】
		for(int j=k*2+1;j<len;j=j*2+1){//从子树的根节点开始向后遍历，比较根节点与子树节点的大小
			if(d[j]<d[j+1]&&j+1<len){//当左子节点小于右子节点
				j++;
			}
			if(d[k]<d[j]){//若子树的根节点的值小于子树节点j的值
				d[k]=d[j];//将该子树节点的值放入根节点
				k=j;//将子树节点j给k
			}else{
				break;
			}
		}
		d[k]=ds;//将之前的根节点值放入到之前j的位置
	}
	//排序算法
	public static void HeapSort(double[] d,int len){
		//建立大顶堆
		/*for(int j=d.length/2-1;j>=0;j--){//从第n/2个节点开始进行调整
			AdjustHead(d,j,d.length);
		}**/
		BuildMaxHeap(d,len);//首先建造初始堆，
		//调整堆结构，交换对顶和末尾元素
		for(int l=len-1;l>0;l--){//从右到左，从下到上，将堆中的每个节点与根节点进行交换
			swap(d,0,l);//将树的第l个节点与根节点交换
			AdjustHead(d,0,l);//将交换后的堆进行调整，重新变为大顶堆
		}
		//return d;
	}
	public static void swap(double[] d,int a,int b){
		double temp;
		temp = d[a];
		d[a] = d[b];
		d[b] = temp;
	}
}

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

堆中也可以插入元素。首先将新节点放在堆的末端，对新节点向上执行调整操作。过程如下所示：

复杂度分析：
空间复杂度：使用常数个辅助单元，空间复杂度为O（1）
时间复杂度：建堆时间为O（n），之后有n-1次向下调整操作，每次调整的时间复杂度为O（h），因此在最好、最坏、平均筛选时，堆排序的时间复杂度为O（nlog2n）。
稳定性：筛选时可能将后面相同的关键字元素调整到前面，因此是不稳定的排序方法。

3.8 基数排序

基数排序（Radix sort）是一种非比较型整数排序算法。

• 原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
  MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
  LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

• 实现步骤：
  1、将所有待比较的数值（正整数）统一为同样的数位长度，数位较短的数前面补零
  2、从最低位开始一次进行一次排序
  3、这样从最低位排序一直到最高位排序完成以后，数列变成一个有序序列

  过程如下所示：
  

package paixu;
import java.util.*;
public class JiShu  {
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		System.out.println("输入多个数字：");
		while(s.hasNext()){
			int n = s.nextInt();
			int[] d = new int[n];
			for(int i=0;i<n;i++){
				d[i] = s.nextInt();
			}
			System.out.println(sort(d));
		}
	}
	public static int[] sort(int[] d){
		//对d数组进行拷贝
		int[] newd = Arrays.copyOf(d,d.length);
		int maxDigit = getMaxDigit(d);//获取最高位数
		return radixSort(d,maxDigit);
	}
	public static int getMaxDigit(int[] d){
		int maxValue = getMaxValue(d);
		return getNumLength(maxValue);
	}
	public static int getMaxValue(int[] d){
		int maxValue = d[0];
		for(int value:d){
			if(maxValue<value){
				maxValue = value;
			}
		}
		return maxValue;
	}
	protected static int getNumLength(long num){
		if(num==0){
			return 1;
		}
		int lenght = 0;
		for(long temp = num;temp!=0;temp/=10){
			lenght++;
		}
		return lenght;
	}
	public static int[] radixSort(int[] d,int maxDigit){
		int mod=10;
		int dev=1;
		for(int i=0;i<maxDigit;i++,dev*=10,mod*=10){
			int[][] counter = new int[mod*2][0];
			 for(int j=0;j<d.length;j++){
				 int bucket = (int)((d[j]%mod)/dev)+mod;
				 counter[bucket] = arrayAppend(counter[bucket],d[j]);
			 }
			 int pos = 0;
			 for(int[] bucket:counter){
				 for(int value:bucket){
					 d[pos++] = value;
				 }
			 }
		}
		return d;
	}
	
	public static int[] arrayAppend(int[] d,int value){
		d = Arrays.copyOf(d, d.length);
		d[d.length-1]=value;
		return d;
	}
}

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

• 复杂度分析：

  时间复杂度：O(k*N)
  空间复杂度：O(k + N)
  稳定性：稳定

  设待排序的数组R[1…n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。

  处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为O(n+r)。所以，总的时间复杂度为O(d*(n+r))。

  基数排序过程中，用到一个计数器数组，长度为r，还用到一个rn的二位数组来做为桶，所以空间复杂度为O(rn)。

  基数排序基于分别排序，分别收集，所以是稳定的。

3.9 桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。
桶排序接近彻底的分治思想，假设待排序的一组数均匀独立分布在一个范围内，将这一范围分为几个子范围。基于映射函数f=array[i]/k；k^2=n;n是所有元素个数。将待排列的关键字k映射到第i个桶中，则该关键字k作为B[i]中的元素(每个桶B[i]都是一组大小为N/M 的序列 )。接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。
为了使桶排序更加高效，我们需要做到这两点：
1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；
实现步骤：
1、设一个定量的数组作为空桶
2、寻访序列，将元素挨个放到对应的桶中
3、对每个不是空的桶进行排序
4、从不是空的桶中将元素放回原来的序列中
设有数组 array = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]，对其进行桶排序：

复杂度分析：
平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：O(n * k)
稳定性：稳定
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

3.10 各种排序算法的比较

从时间 复杂度看 简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为O(n2），且 实现过程也较简单，但直接插入排序和 冒泡排序最好情况下的时间复杂度 可以达到O（n），而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，到较大规模的排序都可以达到很高的效率，但目前未得到其精确的渐近时间。堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆，且在 O(n log2n) 完成排序过程。快速排序基于分治的思想，虽然最坏情况下快速排序时间会达到 O(n^2 ），但快速排序平均性能可以达到 O(nlog2n) ，在实际应用中常常优于其他排序算法。 归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 O(nlog2n）。
各种排序算法的比较：

3.11 排序算法的应用

通常情况，对排序算法的比较和应用应考虑 以下情况：
1 ）选取排序方法需要考虑的因素：
①待排序的元素数目n
②元素本身信息量的大小
③关键字的结构及其分布情况
④稳定性的要求
⑤语言工具的条件，存储结构及辅助空间的大小等。
2）排序算法小结：