排序算法

对一序列对象根据某个关键字进行排序

（1）稳定性

在排序中对于相等的两个元素a、b。如果排序前a在b的前边，排序之后a也总是在b的前边。位置不会因为排序而改变称之为稳定。反之，如果排序后a、b的位置可能会发生改变，那么就称之为不稳定

（2）时间复杂度

一个算法执行所耗费的时间
时间复杂度本意是预估算法的执行时间，但实际上一个程序在计算机上执行的速度是非常快的，时间几乎可以忽略不计了，也就是失去了意义，所以这里意思是算法中执行频度最高的代码的执行的次数。反应当n发生变化时，执行次数的改变呈现一种什么样的规律

（3）空间复杂度

运行完一个程序所需内存的大小
指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数

（4）排序

内排序：所有排序操作都在内存中完成
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

常见排序算法可以分为两大类

（1）非线性时间(比较类排序)

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O（nlogn），因此称为非线性时间比较类排序
快速排序、归并排序、堆排序、冒泡排序等属于比较排序
在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置

比较排序优势：适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况

（2）线性时间(非比较类排序)

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序

计数排序、基数排序、桶排序则属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解 = 据规模和数据分布有一定的要求

冒泡排序（Bubble Sort）

一种简单的排序算法。重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

即对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序

（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
（3）针对所有的元素重复以上的步骤，除了最后一个
（4）重复步骤1~3，直到排序完成

public static int[] bubbleSort(int[] array) {
	if (array == null){
		return;
	}
	int len = array.length;
	// i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
	for (int i = 0; i < len - 1; i++) {
		// j控制比较次数，第i次循环内需要比较len-i次
		// 但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
		for (int j = 0; j < len - i - 1; j++) {
			// 如果前一个数比后一个数大，则交换位置将大的数往后放
			if (array[j] > array[j + 1]) {
				int temp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = temp;
			}
		}
	}
	return array;
}

选择排序（Selection Sort）

表现最稳定的排序算法之一 ，简单直观。因为无论什么数据进去都是O（n2）的时间复杂度 ，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法

选择排序可以说是冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟 所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标 这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序。 这样相对于冒泡排序来说，比较的次数并没有改变，但是数据交换的次数大大减少

工作原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果
（1）初始状态：无序区为R[1…n]，有序区为空
（2）第i趟排序（i=1、2、3、…、n-1）开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
（3）n-1趟结束，数组有序化了

public static int[] selectSort(int[] array) {
	if (array == null){
		return;
	}
	int len = array.length;
	// i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
	for (int i = 0; i < len - 1; i++) {
		// minIndex 用来保存每次比较后较小数的下标
		int minIndex = i;
		// j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可
		for (int j = i + 1; j < len; j++) {
			// 每比较一次都需要将较小数的下标记录下来
			if (array[minIndex] > arr[j]) {
				minIndex = j;
			}
		}
		// 当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置
		if (minIndex != i) {
			int temp = array[i];
			array[i] = array[minIndex];
			array[minIndex] = temp;
		}
		//如果完成一次循环，最小数是本身则不作操作，继续进行下一循环
		// 打印每次循环结束之后数组的排序状态（方便理解）
		System.out.println("第" + (i + 1) + "次循环之后效果：" + Arrays.toString(array));
	}
	return array;
}

插入排序（Insertion Sort）

简单直观的排序算法（见缝插针）
工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

一般来说，插入排序都采用in-place在数组上实现
（1）从第一个元素开始，该元素可以认为已经被排序
（2）取出下一个元素，在已经排序的元素序列中从后向前扫描
（3）如果最后一个已排序元素大于新元素，将该元素移到下一位置
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到该位置后
（6）重复步骤2~5

public static int[] insertionSort(int[] array) {
	if (array == null){
		return;
	}
	int len = array.length;
	// i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
	for (int i = 1; i < len; i++) {
		int j = i;// 变量j用来记录即将要排序的数的位置即目标数的原位置
		int target = array[j];// target用来记录即将要排序的那个数的值即目标值
		// while循环用来为目标值在已经排好序的数中找到合适的位置,因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
		while (j > 0 && target < array[j - 1]) {
			// 当目标数的值比它当前位置的前一个数的值小时，将前一个数的位置向后移一位。并且j--使得目标数继续与下一个元素比较
			array[j] = array[j - 1];
		j--;
		}
		// 更目标数的位置
		array[j] = target;
		// 打印每次循环结束之后数组的排序状态（方便理解）
		System.out.println("第"+(i)+"次循环之后效果："+Arrays.toString(array));
	}
	return array;
}

希尔排序（Shell Sort）

希尔排序也称为“缩小增量排序”，原理是先将需要排的数组分成多个子序列，这样每个子序列的元素个数就很少，再分别对每个对子序列进行插入排序。在该数组基本有序后 再进行一次直接插入排序就能完成对整个数组的排序。所以，要采用跳跃分割的策略。这里引入“增量”的概念，将相距某个增量的记录两两组合成一个子序列，然后对每个子序列进行直接插入排序， 这样得到的结果才会使基本有序（即小的在前边，大的在后边，不大不小的在中间）。希尔排序就是 直接插入排序的升级版

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
（2）按增量序列个数k，对序列进行k 趟排序
（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

public static int[] shellSort(int[] array) {
	if (array == null){
		return null;
	}
	
	int len = array.length; // 数组的长度
	int k = len / 2; // 初始的增量为数组长度的一半
	// while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
	// 增量的最小值为1，即最后一次对整个数组做直接插入排序
	while (k > 0) {
		// 里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
		// 所以直接将直接插入排序中的‘1’变为‘k’就可以了
		for (int i = k; i < len; i++) {
			int j = i;
			int target = array[i];
			while (j >= k && target < array[j - k]) {
				array[j] = array[j - k];
				j -= k;
			}
			array[j] = target;
		}
		// 不同增量排序后的结果
		System.out.println("增量为" + k + "排序之后：" + Arrays.toString(array));
		k /= 2;
	}
	return array;
}

归并排序（Merge Sort）

从上到下递归拆分，然后从下到上逐步合并

（1）递归拆分

先把待排序数组分为左右两个子序列，再分别将左右两个子序列拆分为四个子子序列，以此类推直到最小的子序列元素的个数为两个或者一个为止。

（2）逐步合并

将最底层的最左边的一个子序列排序，然后将从左到右第二个子序列进行排序，再将这两个排好序的子序列合并并排序，然后将最底层从左到右第三个子序列进行排序… 合并完成之后记忆完成了对数组的排序操作
一定要注意是从下到上层级合并，可以理解为递归层级返回

1.把长度为n的输入序列分成两个长度为n/2的子序列
2.对这两个子序列分别采用归并排序
3.将两个排序好的子序列合并成一个最终的排序序列

// 递归拆分
public static int[] MergeSort(int[] array) {
	if (array.length < 2){
		return array;
	}
	int mid = array.length / 2;
	int[] left = Arrays.copyOfRange(array, 0, mid);
	int[] right = Arrays.copyOfRange(array, mid, array.length);
	return merge(MergeSort(left), MergeSort(right)); //递归
}

// 逐步合并；先排序，再合并
@param left
@param right
public static int[] merge(int[] left, int[] right) {
	int[] result = new int[left.length + right.length];
	// index：临时数组下标
	// l：左数组下标
	// r：右数组下标
	for (int index = 0, l = 0, r = 0; index < result.length; index++) {
		if (l >= left.length){
			result[index] = right[r++];
		} else if  (r >= right.length){
			result[index] = left[l++];
		} else if (left[l] > right[r]){
			result[index] = right[r++];
		} else {
			result[index] = left[l++];
		}
	}
	return result;
}

快速排序（Quick Sort）

快速排序也采用了分治的策略，这里引入了“基准数”的概念
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）

1.数列中挑出一个元素为基准数（pivot ）（一般将待排序的数组的第一个数作为基准数）
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
3.重复1、2步骤。**递归（recursive）**把小于基准值元素的子数列和大于基准值元素的子数列排序
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

/**
  * 分区过程
  * @param arr   待分区数组
  * @param left  待分区数组最小下标
  * @param right 待分区数组最大下标
  */
public static void quickSort(int[] arr, int left, int right) {
	if (left < right) {
		int temp = qSort(arr, left, right);
		quickSort(arr, left, temp - 1);
		quickSort(arr, temp + 1, right);
	}
}

/**
  * 排序过程
  * @param arr   待排序数组
  * @param left  待排序数组最小下标
  * @param right 待排序数组最大下标
  * @return 排好序之后基准数的位置下标，方便下次的分区
  * /
public static int qSort(int[] arr, int left, int right) {
	int temp = arr[left];// 定义基准数，默认为数组的第一个元素
	
	// 循环执行的条件
	while (left < right) {
		// 因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
		// 如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
		while (left < right && arr[right] > temp) {
			right--;
		}
		
		// 跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
		// 这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
		if (left < right) {
			arr[left++] = arr[right];
		}
		
		// 下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
		// 因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
		while (left < right && arr[left] <= temp) {
			left++;
		}
		// 跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
		if (left < right) {
			arr[right--] = arr[left];
		}
	}
	
	// 当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
	// 这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
	arr[left] = temp;
	return left;
}

public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] arr = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
	quickSort(arr, 0, 9);
	System.out.println(Arrays.toString(arr));
}

/**
  * 快速排序方法
  * /
public static int[] QuickSort(int[] array, int start, int end) {
	if (array.length < 1 || start < 0 || end >= array.length || start > end){
		return null;
	}
	int smallIndex = partition(array, start, end);
	if (smallIndex > start){
		QuickSort(array, start, smallIndex - 1);
	}
	if (smallIndex < end){
		QuickSort(array, smallIndex + 1, end);
	}
	return array;
}

/**
  * partition分区，
  * @param arr   待排序数组
  * @param start  待排序数组最小下标
  * @param end 待排序数组最大下标
  * @return 排好序之后基准数的位置下标，方便下次的分区
  * /
public static int partition(int[] array, int start, int end) {
	int pivot = (int) (start + Math.random() * (end - start + 1));
	int smallIndex = start - 1;
	swap(array, pivot, end);
	for (int i = start; i <= end; i++)
		if (array[i] <= array[end]) {
			smallIndex++;
			if (i > smallIndex){
				swap(array, i, smallIndex);
			}
		}
	}
	return smallIndex;
}

// 交换数组内两个元素
public static void swap(int[] array, int i, int j) {
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

堆排序（Heap Sort）

堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
堆是一种特殊的完全二叉树，分为大顶堆和小顶堆

大顶堆：每个结点的值都大于它的左右子结点的值，升序排序用大顶堆
小顶堆：每个结点的值都小于它的左右子结点的值，降序排序用小顶堆

所以，需要先将待排序数组构造成大顶堆的格式，这时候该堆的顶结点就是最大的数，将其与堆的最后一个结点的元素交换。再将剩余的树重新调整成堆，再次首节点与尾结点交换，重复执行直到只剩下最后一个结点完成排序

算法描述
步骤1：
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

步骤2：
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

步骤3：
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void heapSort(int[] arr) {
		if (arr == null) {
			return;
		}
		int len = arr.length;
		// 初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
		for (int i = len / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, len);
		}
		// 将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
		for (int j = len - 1; j > 0; j--) {
			swap(arr, 0, j);
			adjustHeap(arr, 0, j);
		}
	}

	/**
	 * 整理树让其变成堆
	 * 
	 * @param arr 待整理的数组
	 * @param i   开始的结点
	 * @param j   数组的长度
	 */
	public static void adjustHeap(int[] arr, int i, int j) {
		int temp = arr[i];// 定义一个变量保存开始的结点
		// k就是该结点的左子结点下标
		for (int k = 2 * i + 1; k < j; k = 2 * k + 1) {
			// 比较左右两个子结点的大小，k始终记录两者中较大值的下标
			if (k + 1 < j && arr[k] < arr[k + 1]) {
				k++;
			}
			// 经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
			if (arr[k] > temp) {
				arr[i] = arr[k];
				i = k;
			} else {// 说明已经是大顶堆
				break;
			}
		}
		arr[i] = temp;
	}

	/**
	 * 交换数据
	 * 
	 * @param arr
	 * @param num1
	 * @param num2
	 */
	public static void swap(int[] arr, int num1, int num2) {
		int temp = arr[num1];
		arr[num1] = arr[num2];
		arr[num2] = temp;
	}

	// 声明全局变量，用于记录数组array的长度；
	static int len;

	/**
	 * 堆排序算法
	 *
	 * @param array
	 * @return
	 */
	public static int[] HeapSort(int[] array) {
		len = array.length;
		if (len < 1)
			return array;
		// 1.构建一个最大堆
		buildMaxHeap(array);
		// 2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
		while (len > 0) {
			swap(array, 0, len - 1);
			len--;
			adjustHeap(array, 0);
		}
		return array;
	}

	/**
	 * 建立最大堆
	 *
	 * @param array
	 */
	public static void buildMaxHeap(int[] array) {
		// 从最后一个非叶子节点开始向上构造最大堆
		// for循环这样写会更好一点：i的左子树和右子树分别2i+1和2(i+1)
		for (int i = (len / 2 - 1); i >= 0; i--) {
			adjustHeap(array, i);
		}
	}

	/**
	 * 调整使之成为最大堆
	 *
	 * @param array
	 * @param i
	 */
	public static void adjustHeap(int[] array, int i) {
		int maxIndex = i;
		// 如果有左子树，且左子树大于父节点，则将最大指针指向左子树
		if (i * 2 < len && array[i * 2] > array[maxIndex])
			maxIndex = i * 2; // 感谢网友矫正，之前是i*2+1
		// 如果有右子树，且右子树大于父节点，则将最大指针指向右子树
		if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
			maxIndex = i * 2 + 1; // 感谢网友矫正，之前是i*2+2
		// 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
		if (maxIndex != i) {
			swap(array, maxIndex, i);
			adjustHeap(array, maxIndex);
		}
	}

计数排序（Counting Sort）

计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序(Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

算法描述
步骤1：找出待排序的数组中最大和最小的元素；
步骤2：统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
步骤3：对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
步骤4：反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

计数排序采用了一种全新的思路，不再是通过比较来排序，而是将待排序数组中的最大值+1作为一个临时数组的长度，然后用临时数组记录待排序数组中每个元素出现的次数。最后再遍历临时数组，因为是升序，所以从前到后遍历，将临时数组中值>0的数的下标循环取出，依次放入待排序数组中，即可完成排序。计数排序的效率很高，但是实在牺牲内存的前提下，并且有着限制，那就是待排序数组的值必须 限制在一个确定的范围

算法分析
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存

public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] arr = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
	countSort(arr);
	System.out.println(Arrays.toString(arr));
}

public static void countSort(int[] arr) {
	if (arr == null)
		return;
	int len = arr.length;
	// 保存待排序数组中的最大值，目的是确定临时数组的长度（必须）
	int maxNum = arr[0];
	// 保存待排序数组中的最小值，目的是确定最终遍历临时数组时下标的初始值（非必需，只是这样可以加快速度，减少循环次数）
	int minNum = arr[0];
	// for循环就是为了找到待排序数组的最大值和最小值
	for (int i = 1; i < len; i++) {
		maxNum = maxNum > arr[i] ? maxNum : arr[i];
		minNum = minNum < arr[i] ? minNum : arr[i];
	}
	// 创建一个临时数组
	int[] temp = new int[maxNum + 1];
	// for循环是为了记录待排序数组中每个元素出现的次数，并将该次数保存到临时数组中
	for (int i = 0; i < len; i++) {
		temp[arr[i]]++;
	}
	// k=0用来记录待排序数组的下标
	int k = 0;
	// 遍历临时数组，重新为待排序数组赋值。
	for (int i = minNum; i < temp.length; i++) {
		while (temp[i] > 0) {
			arr[k++] = i;
			temp[i]--;
		}
	}
}

	/**
	 * 计数排序
	 *
	 * @param array
	 * @return
	 */
	public static int[] CountingSort(int[] array) {
		if (array.length == 0)
			return array;
		int bias, min = array[0], max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] > max)
				max = array[i];
			if (array[i] < min)
				min = array[i];
		}
		bias = 0 - min;
		int[] bucket = new int[max - min + 1];
		Arrays.fill(bucket, 0);
		for (int i = 0; i < array.length; i++) {
			bucket[array[i] + bias]++;
		}
		int index = 0, i = 0;
		while (index < array.length) {
			if (bucket[i] != 0) {
				array[index] = i - bias;
				bucket[i]--;
				index++;
			} else
				i++;
		}
		return array;
	}

桶排序（Bucket Sort）

桶排序 是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

算法描述
步骤1：人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
步骤2：遍历输入数据，并且把数据一个一个放到对应的桶里去；
步骤3：对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
步骤4：从不是空的桶里把排好序的数据拼接起来。

注意：如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

桶排序其实就是计数排序的强化版，需要利用一个映射函数首先定义有限个数个桶，然后将待排序数组内的元素按照函数映射的关系分别放入不同的桶里边，现在不同的桶里边的数据已经做了区分，比如A桶里的数要么全部大于B桶，要么全部小于B桶里的数。但是A，B桶各自里边的数还是乱序的。所以要借助其他排序方式（快速，插入，归并）分别对每一个元素个数大于一的桶里边的数据进行排序。最后再将桶里边的元素按照顺序依次放入待排序数组中即可。

	/**
	 * 桶排序
	 *
	 * @param array
	 * @param bucketSize
	 * @return
	 */
	public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
		if (array == null || array.size() < 2)
			return array;
		int max = array.get(0), min = array.get(0);
		// 找到最大值最小值
		for (int i = 0; i < array.size(); i++) {
			if (array.get(i) > max)
				max = array.get(i);
			if (array.get(i) < min)
				min = array.get(i);
		}
		int bucketCount = (max - min) / bucketSize + 1;
		ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
		ArrayList<Integer> resultArr = new ArrayList<>();
		for (int i = 0; i < bucketCount; i++) {
			bucketArr.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < array.size(); i++) {
			bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
		}
		for (int i = 0; i < bucketCount; i++) {
			if (bucketSize == 1) { // 如果带排序数组中有重复数字时
				for (int j = 0; j < bucketArr.get(i).size(); j++)
					resultArr.add(bucketArr.get(i).get(j));
			} else {
				if (bucketCount == 1)
					bucketSize--;
				ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
				for (int j = 0; j < temp.size(); j++)
					resultArr.add(temp.get(j));
			}
		}
		return resultArr;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
		bucketSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void bucketSort(int[] arr) {
		if (arr == null)
			return;
		int len = arr.length;
		// 定义桶的个数，这里k的值要视情况而定，这里我们假设待排序数组里的数都是[0,100)之间的。
		int k = 10;
		// 用嵌套集合来模拟桶，外层集合表示桶，内层集合表示桶里边装的元素。
		List<List<Integer>> bucket = new ArrayList<>();
		// for循环初始化外层集合即初始化桶
		for (int i = 0; i < k; i++) {
			bucket.add(new ArrayList<>());
		}
		// 循环是为了将待排序数组中的元素通过映射函数分别放入不同的桶里边
		for (int i = 0; i < len; i++) {
			bucket.get(mapping(arr[i])).add(arr[i]);
		}
		// 这个循环是为了将所有的元素个数大于1的桶里边的数据进行排序。
		for (int i = 0; i < k; i++) {
			if (bucket.size() > 1) {
				// 因为这里是用集合来模拟的桶所以用java写好的对集合排序的方法。
				// 其实应该自己写一个方法来排序的。
				Collections.sort(bucket.get(i));
			}

		}
		// 将排好序的数重新放入待排序数组中
		int m = 0;
		for (List<Integer> list : bucket) {
			if (list.size() > 0) {
				for (Integer a : list) {
					arr[m++] = a;
				}
			}
		}
	}

	/**
	 * 映射函数
	 * 
	 * @param num
	 * @return
	 */
	public static int mapping(int num) {
		return num / 10;
	}

基数排序（Radix Sort）

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数
组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述
步骤1：取得数组中的最大数，并取得位数；
步骤2：arr为原始数组，从最低位开始取每个位组成radix数组；
步骤3：对radix进行计数排序（利用计数排序适用于小范围数的特点）

就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字； 第1个排序关键字，第2个排序关键字，第3个排序关键字…然后，根据子关键字对待排序数据进行排序。

基数排序有两种方法：
①MSD 从高位开始进行排序
②LSD 从低位开始进行排序

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 720, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
		redixSort(arr, 10, 3);
		System.out.println(Arrays.toString(arr));
	}

	public static void redixSort(int[] arr, int radix, int d) {
		// 缓存数组
		int[] tmp = new int[arr.length];
		// buckets用于记录待排序元素的信息
		// buckets数组定义了max-min个桶
		int[] buckets = new int[radix];

		for (int i = 0, rate = 1; i < d; i++) {

			// 重置count数组，开始统计下一个关键字
			Arrays.fill(buckets, 0);
			// 将data中的元素完全复制到tmp数组中
			System.arraycopy(arr, 0, tmp, 0, arr.length);

			// 计算每个待排序数据的子关键字
			for (int j = 0; j < arr.length; j++) {
				int subKey = (tmp[j] / rate) % radix;
				buckets[subKey]++;
			}

			for (int j = 1; j < radix; j++) {
				buckets[j] = buckets[j] + buckets[j - 1];
			}

			// 按子关键字对指定的数据进行排序
			for (int m = arr.length - 1; m >= 0; m--) {
				int subKey = (tmp[m] / rate) % radix;
				arr[--buckets[subKey]] = tmp[m];
			}
			rate *= radix;
		}
	}

	/**
	 * 基数排序
	 * 
	 * @param array
	 * @return
	 */
	public static int[] RadixSort(int[] array) {
		if (array == null || array.length < 2)
			return array;
		// 1.先算出最大数的位数；
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			max = Math.max(max, array[i]);
		}
		int maxDigit = 0;
		while (max != 0) {
			max /= 10;
			maxDigit++;
		}
		int mod = 10, div = 1;
		ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < 10; i++)
			bucketList.add(new ArrayList<Integer>());
		for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
			for (int j = 0; j < array.length; j++) {
				int num = (array[j] % mod) / div;
				bucketList.get(num).add(array[j]);
			}
			int index = 0;
			for (int j = 0; j < bucketList.size(); j++) {
				for (int k = 0; k < bucketList.get(j).size(); k++)
					array[index++] = bucketList.get(j).get(k);
				bucketList.get(j).clear();
			}
		}
		return array;
	}

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序： 根据键值的每位数字来分配桶
计数排序： 每个桶只存储单一键值
桶排序： 每个桶存储一定范围的数值