注意：代码大同小异，最好自己理解了思想后自己写一遍

1.直接插入排序

顾名思义就是从数组中一个一个取元素，然后一个一个插入形成有序序列。比如说一个int型无序数组，从小到大排序。

特点：平均时间复杂度O(n2) 空间复杂度O(1) 稳定的
适用情况：数据量比较少的排序

步骤：
（1）选取第一个元素arr[0]，因为只有一个元素，无须比较，直接插 入arr[0]的位置。
（2）选取第二个元素arr[1]插入前面已经排好顺序的序列中，这里前面排序好的序列里 面只有arr[0],所以只许将arr[1]和arr[0]进行比较，如果arr[1]<arr[0],则交换顺序，小的 排在前面。
（3）选取第三个元素arr[2]插入前面已经排好顺序的序列中（这里只有arr[0]arr[1]两个 元素）,这里注意要从后往前比较，如果该元素比前面的小，则和前面一个元素换位置， 继续和更前面的元素比较，如果还比前面的小，还要跟前面继续换位置，直到到达正确 的顺序位置（这里就是升序嘛）就停止比较了，也不再需要跟更前面的元素比较了。
（5）选取第四个元素arr[3],同步骤
（6）以此类推……

Java实现代码：

//直接插入排序，从小到大
int[] arr = {2,5,6,1,3,0,9,8};//从第二个元素开始插入for(int i=1;i<arr.length;i++){int value = i;int j = i-1;//第i个要插入的元素从后往前比较，即与i-1开始比较while(j>=0&&arr[value]<arr[j] )//要插入的元素比前面已经排好序的元素小{int temp;temp = arr[value];arr[value] = arr[j];arr[j] = temp;j--;value--;}}for(int a :arr){System.out.println(a);}

控制台结果：

代码详解：这里定义了一个无序int数组，进行从小到大的排序
（1）for语句是从int=1，即第二个元素开始插入，因为第一个元素无需判断，所以从i=1到i=arr.length-1都要一个一个插入。
（2）Value变量的定义：这里为什么要定义一个中间变量value呢，因为在插入的过程中要一直比较新元素与前一个元素的大小来判断是否要互换位置，如果互换位置了，就需要value来保存互换位置后新元素的下标，也就是说value保存了整个变换过程中插入的新元素的位置。
（3）While语句判断j是否是>=0,如果j=0,表示要插入的新元素在arr[1]的位置，此时要比较arr[0]和新元素的大小来判断是否互换位置，完成这一步之后j=-1，所以不再循环，插入已经完成。（这里有个小细节就是while语句里的判断内容：j>=0要写在&&之前是因为当不满足j>=0时，编译器不会去判断后面的arr[value]<arr[j]，也就不会抛出数组越界的异常，如果arr[value]<arr[j]放在&&前面挡j<0时就会有arr[-1],编译器就会报错）
（4）While语句里面互换元素位置后更新新元素的位置value（value–；）和j的位置（j–；），再继续比较。
（5）最后foreach语句打印查看结果。

2.折半插入排序（基于折半查找法，即二分查找法）

折半插入排序就是对直接插入排序的一个小变化，在已经完成排序的部分中找出第一个比即将插入的新元素大的元素位置，将新元素插入到该位置，该位置后面的元素一次向后移动一个位置。通俗点将就是找到一个位置将这个新元素插入进去，该位置之后的元素一次向后移动一个位置。怎样找到这个位置的，就是通过折半（二分）查找法。

特点：平均时间复杂度O(n2) 空间复杂度O(1) 稳定的
适用情况: 元素初始序列接近有序序列时

Java代码实现：

//折半插入排序int[] arr = {2,5,6,1,3,0,9,8};//待排序的数组int left ,right;//已经完成排序部分的左右边界int middle;for(int i=1;i<arr.length;i++)//遍历待排序的部分，一个一个插入{left = 0;right = i-1; while(left<=right){middle = (left + right)/2;if(arr[middle]>arr[i]){right = middle-1;}else{left = middle+1;}}int temp = arr[i];for(int j=i-1;j>=left;j--){arr[j+1] = arr[j];}arr[left] = temp;}for(int a :arr){System.out.println(a);}

代码详解：
折半插入排序的重点就是折半查找，left和right用来指示新元素插入的区间，通过折半的方法逐渐缩小left和right之间的区间，while语句控制区间的缩小，边界条件是left=right=middle，也就是最终区间缩小到最后只剩一个元素，left和right同时指向该元素，此时判断如果arr[middle]>arr[i],此时right左移，新元素放在left位置上，也就是当前位置。如果arr[middle]<=arrileft右移一个单位，所以还是应该放在left位置上，但不是刚刚的当前位置了，而是此位置的下一个位置。求出来存放新元素的left位置及其之后的位置应该先一次后移一个位置，然后把新元素放到求出来的这个位置，即当前left指向的位置。

3.希尔排序

希尔排序是对直接插入排序的改进，在元素量较少或者初始数据接近有序的时候，直接插入排序效率较高。希尔排序就针对这两点进行了改进。首先是分组，将大量的数据分成了一组一组的，这样就实现了对少量数据的处理；其次是不断地慢慢的使数组序列变得接近有序。

特点：时间复杂度跟增量序列有关，极其复杂 空间复杂度O(1) 不稳定

Java代码实现：

int[] arr = {14,5,4,5,3,13,9,8};//待排序的数组int gap = arr.length;while(gap>，0){gap = gap/2;for(int i=0;i<arr.length;i++){int value = i;int j = value - gap;while(j>=0&&arr[j]>arr[value]){int temp;temp = arr[j];arr[j] = arr[value];arr[value] = temp;value-=gap;j-=gap;}}System.out.println(Arrays.toString(arr));

控制台结果：

代码详解：
（1）希尔排序原理上跟直接插入排序是相同的，通俗点说，不同点就是在处理大量元素时，可以“分组”，将大量数据分组成几组少量数据，每一组数据之间又是有序的，所以等间隔抽取数据组成一组，这样所有数据合在一起的时候整个数据也是接近有序的，只需要做稍微变动即可完成排序。
（2）gap就是增量，也就是间隔取值量，所有元素将分成gap个组，gap越大，每个组中的元素就越少。分完组以后arr[i]不再是与arr[i-1]相比较了，而是跟arr[i-gap]比较，即跟同组内的前一个元素相比较。直到gap=1的时候表示的就是所有的元素分成一个组，也就是对所有的元素进行排序。因为前面已经经过多次不同gap值情况下的排序，所以这时候的元素基本上已经接近有序，只需要稍加改动即可完成排序。
（3）“分组”实际上是虚拟的分组，并不是真正意义上的分组。与直接插入排序相比，只是多了个控制器而已。
（4）为了形象的理解，举一个例子。军训的时候为了排列队形，教官说大家站成一排，从1-5循环报数，最后说，报1的出列，形成第一排；报2的出列，形成第二排；最后形成了五排；然后每一排当中按照高矮个站队。这就相当于gap=5时进行的一次调整，每一排就相当于一个组；经过多次gap不同值的调整，元素逐渐接近有序。

4.冒泡排序

冒泡排序顾名思义就是像开水一样不断冒泡泡。简单地说，如果是将元素从小到大排序，每次就冒出一个最大的元素，放在数组的最后面。怎样保证冒一次泡后最大的元素就放在最后面了呢？冒泡排序是通过交换相邻元素来实现的。

步骤解析：
（1）比较arr[0]和arr[1]，小的放在前面，大的放在后面，此时a[1]存放的一定是a[0]、 a[1]这两个元素中最大的元素；
（2）再次比较arr[1]和arr[2]，小的放在前面，大的放在后面，此时a[2]存放的一定是a[0]、 a[1]、a[2]这三个元素中最大的元素；
（3）同理，继续比较a[2]和a[3],小的放在前面，大的放在后面,此时a[3]存放的一定是a[0]、 a[1]、a[2]、a[3]这四个元素中最大的元素；
（4）以此类推，经过一轮的比较之后，arr[arr.length-1]中存放的就是所有元素中最大的元 素；
（5）那么要经过多少轮才能完成排序呢？我们知道，经过一轮我们就可以将未排序部分中的最大值放到后面。假如有五个元素，那么经过四轮之后，后面四个元素已经排好序了，只剩一个元素和第一个位置，所以一定是最小的元素，不用比较了；同理如果有i个元素，我们最多也只需要i-1轮就能完成排序。

java代码实现：

int[] arr = {49,38,65,97,76,13,27,49,55,4};//i控制比较的轮数，累计比较arr.length-1轮for(int i=0;i<arr.length-1;i++){//每一轮不断比较arr[j]和arr[j+1],j不断递增；for(int j=0;j<arr.length-1;j++){if(arr[j]>arr[j+1]){int temp;temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}System.out.println(Arrays.toString(arr));//打印数组查看结果}

控制台结果：

代码详解：
（1）i控制比较的轮数，也可以用while来控制，都一样的，只要保证能循环arr.length-1轮就可以了，不要那么死板！
（2）j表示数组元素的下标，从0开始到arr.length-2结束，所以控制条件写的j<arr.length-1;因为要比较arr[j]和arr[j+1]的大小，j不需要等于arr.length-1，否则下标溢出了！
（3）最后System.out.println是打印数组查看结果，没学过java的可以用其他编程语言代替。
（4）最后看结果，每一次把前面未排序部分中的最大的值冒泡冒出来放到后面俩排序，这就是冒泡；

5.快速排序

快速排序的思想：在所有元素中随便选取一个元素i，假设从小到大排序，那么比i小的元素放在i的左边，比i大的元素放在i的右边，但是不保证i左右两边的元素是有序的，只能保证i左边的元素小于等于i，i右边的元素大于等于i.

但是怎样才能完成排序的？很明显可以看出来在完成上面这样一轮的变化之后（并没有完成排序），元素i的位置就完全确定了，加入此时i是第五个元素，那么完成排序之后i仍然是第五个元素。所以我们就把i左右两边“分成”两个数组，对每个数组继续执行上面的操作，这样又能确定一个元素的位置了，然后i左边继续“分成”两个数组，i右边也继续“分成”两个数组，对每个数组再继续执行上面的操作……逐渐的所有的元素的位置就慢慢确定了，最终的序列就是正确的顺序。

具体实现方法：
（1）一般用第一个数当成基准数temp（temp = arr[0]），然后从数组后面开始，和temp比较。
（2）如果比temp大或者等于temp，应该放在temp右边（等于temp时放在右边是为了保证稳定性），所以位置不用动，右指针j左移继续判断，当arr[j]<temp时，应该放在temp的左边，所以放在arr[0]的位置，因为此时arr[0]的值已经保存在temp中了，不用担心覆盖。
（3）这时候开始移动左指针i，当arr[i]<=temp时（等于是为了保证稳定性），继续移动左指针i，当arr[i]>temp时，应该放在temp的右边，可是放在右边哪里呢？刚刚arr[j]的值已经赋值给了arr[0],所以arr[j]也可以覆盖，而且正好在temp的右边，就覆盖它吧，于是arr[j]=arr[i].
（4）然后又轮到移动判断右指针了，还是按照上面的方法依次移动右指针和左指针，直到i=j的时候，此时这个位置就是temp的位置，左边的所有元素比temp小，右边的所有元素比temp大；
（5）把temp左右两边看成两个新的数组，分别对他们用这种办法排序，直到begin=end，也就是只有一个元素的时候就不用再比较了，排序已经完成了。

Java代码实现：

public class QuickSortDemo 
{public static void main(String[] args) {int[] arr = {49,38,65,97,76,13,27,49,55,4};QuickSortDemo.quickSort(arr, 0, 9);System.out.println(Arrays.toString(arr));}static void quickSort(int[] arr, int begin, int end){//如果begin<end说明temp左边或者右边不止一个元素，所以要继续递归//结束条件就是begin=endif(begin < end){int i = begin;int j = end;int temp = arr[i];while(i<j){//右边尾部开始判断，比temp大或者等于temp就继续左移指针while(i<j&&arr[j]>=temp){j--;}//找到第一个比temp小的元素，应该放在temp左边arr[i] = arr[j];//左边首部开始判断，比temp小或者等于temp就继续右移指针while(i<j&&arr[i]<=temp){i++;}//找到第一个比temp大的元素，应该放在temp右边arr[j] = arr[i];}arr[i] = temp;quickSort(arr,begin,i-1);quickSort(arr,i+1,end);}}
}

控制台结果：

代码解释：
（1）这里我定义了一个函数quickSort()来接收排序的数组，排序的开始位置begin和排序的终止位置end。并且用的递归，递归的最终条件就是begin=end，此时要排序的范围就是一个元素，根本不用排序，所以不会进入if，什么也不做，这一层函数结束完毕，逐渐返回上一层函数，上上一层函数，返回到最后一层函数时所有代码执行完毕，排序已经完成。
（2）代码中需要注意的几个点：begin和end表示的是要排序的范围，在函数中不能改变，所以要用i，j来复制begin和end，（i，j其实保存的是下标，告诉我们前面移动到哪里了，后面移动到哪里了）以便在代码中控制循环。另一个就是最内部的两个while语句要判断i<j,因为i，j在内部也是不断变化的，不能只在外层while判断。

参考：https://blog.csdn.net/elma_tww/article/details/86164674

6.选择排序

选择排序的思想：假如我们要从小到大排序，假设第一个元素arr[0]是最小的元素，然后将arr[0]与之后的所有元素依次比较，谁小谁就到前面来，遍历完以后整个数组中最小的元素就在arr[0]这个位置上了。再从arr[1]开始，假设arr[1]是最小的元素，arr[1]与之后所有的元素依次比较，谁小就到arr[1]这个位置上来。依次类推，当arr[arr.length-2]这个位置元素确定时，最后一个元素就在最后一个位置了，排序结束了。

**注意：**选择排序与冒泡排序的共同点就是每次选出一个最大或者最小的；但是选择排序的特点就是我只管我这个位置，只要后面的元素你比我小，你就到我这里来，就像擂台一样，谁小谁就是霸主。而冒泡排序就的特点就是相邻元素之间进行比较，最终大的元素逐渐逐渐向后移动，也就是逐渐逐渐冒泡出来。

Java代码实现：

int[] arr = {49,38,65,97,76,13,27,49,55,4};for(int i=0;i<arr.length-1;i++){for(int j=i+1;j<arr.length;j++){if(arr[i]>arr[j]){int temp;temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}System.out.println(Arrays.toString(arr));}

控制台结果：

代码很简单，外层循环i控制要放最小元素的位置，内层循环j控制arr[i]与其之后的每一个元素进行比较，从结果可以看出每循环一次，就排一个最小的元素。

7.归并排序

归并排序的思想就是分治。将一个大数组分成一个一个的小数组，使每一个小数组内部有序，然后再两两合并成一个中型数组，使中型数组也有序，最后合并成一个整形数组。排序的过程是在合并的时候完成两个数组的排序。所以整个排序算法分为两部分，一部分就是递归思想的实现，其实我个人感觉递归还是挺难理解的。另一部分就是怎样在合并的时候排序了。

递归的理解：
首先递归要有一个终止条件，不然递归永远不会终止，程序就会崩溃。程序中定义了两个函数，其中一个sort函数来实现排序。我们可以这样考虑，我们定义这个函数来干嘛？来排序嘛对吧。这个函数有什么参数？有排序的数组arr，排序的左右边界范围left和right，还有一个中间数组用来临时存储数值的。这个sort函数怎么用？给出要排序的数组arr和排序的范围边界left，right和一个跟arr同长度的数组，通过这个函数以后就能给arr数组排好序。既然这样那么我们将这个数组分成两个子数组（不是一定要从中间分的，从任何一个位置分都可以），对每个子数组再继续使用sort排序，只不过是参数稍有改变，就这样sort1中使用sort2，sort2中使用sort3，sort3中使用sort4，依次类推，直到遇见了终止条件，然后sort函数开始一层一层的返回。因为是sort函数是入栈的，所以刚才是一层一层的入栈，遇到终止条件以后就一层一层的出栈，也就是sort函数一层一层的返回，这里不理解没关系哈。

如何在合并的时候排序：
可以这样理解，左右两个子数组都是有序的，合并完以后怎样有序呢？可以这样，比较两个子数组的“头”元素，也就是arr[0]，元素值小的，就把头砍下来放在临时数组temp中，被砍数组就会有一个新的“头”了，两个数组再继续比较“头”元素的大小，谁的小，就砍下来依次放入到temp中，当其中一个数组全部放入temp中时，剩下的另一个数组就可以把剩下的元素按照顺序依次放入temp中了，自己可以举个简单的例子尝试一下哈，很好理解。

Java代码实现：

public class GuiBingSort 
{public static void main(String []args){int[] arr = {49,38,65,97,76,13,27,49,55,4};int[] temp = new int[arr.length];GuiBingSort.sort(arr, 0, arr.length-1, temp);System.out.println(Arrays.toString(arr));}private static void sort(int[] arr, int left,  int right, int[] temp) {//递归的终止条件就是left = right，也就是说待排序的数组只有一个元素，根本无需排序if(left<right){int middle = (left + right)/2;//左边数组排序GuiBingSort.sort(arr,left,middle,temp);//右边数组排序GuiBingSort.sort(arr,middle+1,right,temp);// 两个数组合并并完成最终排序join(arr,left,middle,right,temp);}}private static void join(int[] arr, int left, int middle, int right, int[] temp) {int i = left;int j = middle+1;int count = 0;while(i<=middle&&j<=right)//终止循环的条件就是其中一个子数组已经全部添加进temp数组{if(arr[i]<=arr[j]){temp[count] = arr[i];i++;count++;}else{temp[count] = arr[j];j++;count++;}}//如果左边数组全部遍历完成的话i=middle+1，所以如果i<=middle说明右边子数组全部遍历完成//所以把左边子数组还未遍历的部分直接添加进temp数组就可以，也是有序的。while(i<=middle){temp[count] = arr[i];i++;count++;}//同理判断右边子数组while(j<=right){temp[count] = arr[j];j++;count++;}//最后将temp数组的内容拷贝给arrcount = 0;while(left<=right){arr[left] = temp[count];left++;count++;}}}

控制台结果：

代码详解:
（1）我要排序整个数组我要怎么办？将这个数组分成两个子数组，将两个子数组分别排好序，然后合并在一起时排好序不就好了吗，所以代码中将数组arr分成了两个数组，left_{middle和middle+1}right，怎样给这两个数组排序的，用sort呀，两个子数组排序好后开始合并，用join函数，所以排序就已经完成了。
（2）Sort递归的终止条件就是left=right，表示只有一个元素参与排序，根本不用排，所以直接跳过if，此sort函数执行完毕，返回上一层sort继续执行，上一层sort函数执行完毕，继续返回上上一层函数，就这样最上面一层sort执行完以后，数组也就完成了排序。

参考：https://www.cnblogs.com/chengxiao/p/6194356.html

8.堆排序

堆排序顾名思义就是利用堆来排序，什么是堆呢？这里所说的堆其实就是一个完全二叉树结构。（不懂完全二叉树的可以去了解一下，很简单）

堆排序的思想：将要排序的数组按照下标依次放入完全二叉树中，然后经过一系列变化将这颗乱序的二叉树变成一个大顶堆，此时arr[0]存放的是整个数组中最大的元素，然后将这个元素放在数组最后一个位置arr[arr.length-1]上，再将前面arr[0]~arr[arr.length-2]重新生成一个大顶堆，然后将arr[0]放在倒数第二个位置，循环往复，数组从后往前逐渐排好顺序，而且是升序排列。

java代码实现：

package package_3;
import java.util.Arrays;
public class TreeSort 
{public static void main(String[] args) {int[] arr = {49,38,65,97,76,13,27,49,55,4};
//for循环控制每次拿出一个最大值后剩下的数组部分继续重新构建大顶堆，直到排序完成for(int length=arr.length;length>0;length--){buildTree(arr,length);exchange(arr,0,length-1);}System.out.print(Arrays.toString(arr));}//定义一个函数，能够将arr数组转换成大顶堆结构static void buildTree(int[] arr,int length){if(length>1){for(int i=length/2-1;i>=0;i--){if(2*i+2<=length-1){if(arr[2*i+1]<arr[2*i+2]){int t = arr[2*i+1];arr[2*i+1] = arr[2*i+2];arr[2*i+2] = t;}}if(arr[2*i+1]>arr[i]){int t = arr[i];arr[i] = arr[2*i+1];arr[2*i+1] = t;}}}}//交换根节点元素和数组最后一个元素static void exchange(int[] arr, int begin, int end){int temp = arr[begin];arr[begin] = arr[end];arr[end] = temp;}
}

控制台结果：

代码详解：代码中的重点就是buileTree这个函数如何将数组变成大顶堆了
（1）首先找到二叉树的第一个非叶子节点，数组下标为arr.length/2-1(为什么是arr.length/2-1,自己话一个三四层的完全二叉树验证一下，注意下标是从0开始的)
（2）这个非叶子节点下标之前的节点一定都是非叶子节点，非叶子节点一定都有叶子（可能只有左叶子，可能左右叶子都有，不可能只有右叶子），我们只要保证所有的节点的父节点一定比子节点的值大就行了，也就是说左右节点的值谁大谁小无所谓，但是父节点的值一定比子节点的值大，所以我们在父节点和两个子节点这三个值之间找出最大的值放在父节点处就ok了。
（3）buildTree函数里面第一个for循环控制遍历所有的非叶子节点。当遍历到一个非叶子节点时我们要做什么操作呢？第一个if判断节点i是否有右叶子节点，嵌套里面的if判断如果有右叶子节点，那么将左右叶子节点的值进行比较，大的值放在左叶子节点；下面的if是将左叶子节点与其父节点进行比较（这时候就没有右叶子节点的事了），大的值放在父节点i中，这样就完成了父节点、左右节点三个值的比较并且把最大的值放在了父节点中，遍历完所有的非叶子节点，此时根节点存放的就是最大的值，而根节点的位置是arr[0].

参考: https://www.cnblogs.com/liuqiyun/p/9415003.html

9.计数排序

计数排序的思想：找出所有元素中的最大值，然后申请一个长度为最大值+1的数组空间，然后将待排序数遍历，将遍历的每一个值存入与其相等的新数组的下标所在的位置，而新数组的值就是该下标值出现的次数。

举个例子：
（1）比如说有数组arr={5,3,5,2,8}，排序的时候首先找出最大值8，然后申请一个长度为8+1=9的数组newarr[]，自动初始化全为0；
（2）接着遍历arr数组，第一个遍历arr[0]=5,就将newarr[5]的值+1，表示5出现一次；
（3）继续遍历，第二个遍历arr[1]=3,将newarr[3]的值+1；
（4）依次遍历arr数组，最终newarr={0,0,1,1,0,2,0,0,1};
（5）最后将newarr数组转化成正确的排序顺序；

图解：

Java代码实现：

package package_3;
import java.util.Arrays;
public class CountSort 
{public static void main(String[] args) {int[] arr = {49,38,65,97,76,13,27,49,55,4};int max = getMax(arr);int[] temp = new int[max+1];sort(arr,temp);System.out.println(Arrays.toString(arr));}//给定int数组，返回数组中的最大值maxstatic int getMax(int[] arr) {int max = arr[0];for(int i=1;i<arr.length;i++){if(arr[i]>max){max = arr[i];}}return max;
}//进行排序的函数static void sort(int[] arr, int[] temp){//遍历arr数组，数组temp计数for(int i=0;i<arr.length;i++){temp[arr[i]]++;}int i = 0;//将temp数组转换成正确的顺序存回arr数组for(int j=0;j<temp.length;j++){if(temp[j]>0){for(int m=1;m<=temp[j];m++){arr[i] = j;i++;}}}}
}

结果：

代码详解：
（1）这里定义了两个函数，一个是找出数组中的最大值，另一个是将arr数组进行排序。
（2）Sort函数中，遍历数组的同时在temp数组中计数，这里注意arr数组的值对应temp数组的下标，因为下标是有序的，所以当arr数组转换成temp数组时，也就是在对arr数组中的值进行排序。Temp数组中存储的是对应位置的下标值在arr数组中出现的次数。
（3）将temp数组转换成有序的并且存回arr数组时，遍历temp数组，值>0表示该位置下标值存在于arr数组中，值为几就表示位置下标值在arr数组中出现了几次。
（4）如果是升序排列，就从前往后遍历temp数组；如果是降序排列，就从后往前遍历temp数组；

计数排序的局限性：
（1）如果我要排的数如果我要排的数据里有0呢？ int[]初始化内容全是0，排毛线。
（2）如果我要排的数据范围比较大呢？比如[1,9999]，我排两个数你要创建一个int[10000]的数组来计数？
对于第一个bug，我们可以使用偏移量来解决，比如我要排[-1,0,-3]这组数字，这个简单，我全给你们加10来计数，变成[9,10,7]计完数后写回原数组时再减10。不过有可能也会踩到坑，万一你数组里恰好有一个-10，你加上10后又变0了，排毛线。
对于第二个bug，确实解决不了，如果是[9998,9999]这种虽然值大但是相差范围不大的数据我们也可以使用偏移量解决，比如这两个数据，我减掉9997后只需要申请一个int[3]的数组就可以进行计数。
由此可见，计数排序只适用于正整数并且取值范围相差不大的数组排序使用，它的排序的速度是非常可观的。

10.桶排序

桶排序就是对计数排序的一个升级，计数排序就相当于每一个数据一个桶，相同的数据放在同一个桶中，应该属于特殊的桶排序。当数据差很大时，直接使用计数排序需要开辟很大的一块空间，简直就是浪费！所以我们将数据按照区间分在一个一个桶中（比如数据为1_{9放在一个桶中，10}19放在另一个桶中……）。每个桶中进行排序，最后再将所有的桶按照顺序连接起来，就完成了排序。

Java中可以使用Arraylist来表示桶。Arraylist内部也是由数组实现的，大小可变，有序，数据可重复（因为前两天刚刚学习java的集合框架，ArrayList实现了Collection、List接口），这里我们用到Arraylist的add()方法和get()方法完成存取数据就可以了。

Java代码实现：

 package package_3;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;class TongSort
{public static void main(String[] args){int[] arr = {49,38,65,97,76,13,27,49,55,4,0};//创建10个桶，并将桶保存在ArrayList表list中，list表中存放的是ArrayList类型的数据ArrayList<ArrayList> list = new ArrayList<ArrayList>() ;for(int i=0;i<10;i++){list.add(new ArrayList());}//遍历arr数组，将元素分桶store(arr,list);//每个桶内部进行排序sort(arr,list);//打印数组查看结果System.out.println(Arrays.toString(arr));   }/** 遍历arr数组，将元素存入对应的桶中*/private static void store(int[] arr, ArrayList<ArrayList> list) {for(int i=0;i<arr.length;i++){//数据为0-9存放在list.get(0)表中//数据为10-19存放在list.get(1)表中//依次类推……list.get(arr[i]/10).add(arr[i]);}   }/** sort方法对每一个桶中的数据进行排序*/private static void sort(int[] arr, ArrayList<ArrayList> list){//count来保存arr数组下标，因为这里我们排好一个桶之后就将该桶中的有序序列//直接放入arr数组中，然后继续排下一个桶int count =0;// 遍历每一个桶，对桶中元素排序for(int i=0;i<list.size();i++){//桶中的元素不止一个，则排序；否则不用排序if(list.get(i).size()>=1){//类Collections提供的Sort方法可以将list类型的数据按照字典顺序排序//也可以自己定义比较器comparator，此时就将按照比较器定义的方法排序Collections.sort(list.get(i));//桶内排序完成之后就将有序数列存入arr数组for(int j=0;j<list.get(i).size();j++){arr[count] = (int) list.get(i).get(j);count++;}}}}
}

结果：

11.基数排序

基数排序是对桶排序的升级，基数排序不管你数据量大小，数据宽度多大，个位十位百位提取以后就是0-9，所以我们定义10个桶完全就够了，也不需要考虑桶排序的区间划分问题。

计数排序的方法：
（1）创建10个桶，标号0-9
（2）根据arr数组中数据的个位进行一次升序排序，也就是说我只看arr数组中数据的 各位数，十位百位是多少都不管，各位数小的就排在前面，各位数大的就排在后 面。比如说231排在123前面。
（3）然后再根据arr数组中十位数的大小进行一次升序排序（注意此时arr是根据个位 排序过后的新的arr）。
（4）直到根据最高位的大小排序后，才算结束，此时就是有序的数列

基数排序的理解：
为什么要依次根据个位十位百位排序呢？为什么不根据百位划分出组，然后再根据十位划分出组，然后组内排序呢？
答：首先，如果根据百位划分出组，组内再继续划分其实这个思想就是桶排序，跟桶排序一样的思想。桶排序的思想就是划分有序的区间，元素属于哪个桶就放入哪个桶中，桶中排序好后，有序桶连接在一起就是完整的排序，先根据百位排序就相当于区间划分成了100而已，实质上就是桶排序。

而先根据个位排序其实就是进行微调，因为比较两个数大小，不管你个位数谁大谁小，谁十位数大，谁就是大的；不管你十位数大小，谁百位数大谁就是大的；不管你百位数大小，谁千位数大，谁就是大的。所以最后谁大谁小还是根据最高位来判断的，最高位相同怎么办，那就根据次高位呗，次高位相同怎么办，那句根据次次高位判断呗。所以从低位开始排序实际上就是进行微调，是为了解决高位相同时大小的比较。但是最终元素大小的决定权还是在高位。

Java代码实现：

package package_3;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;public class JiShuSort {public static void main(String[] args) {int[] arr = {133,124,563,345,895,329,8862,3249,1234};//创建包含10个桶的列表listArrayList<ArrayList> list = new ArrayList<ArrayList>() ;for(int i=0;i<10;i++){list.add(new ArrayList());}//按照个位排序int[] temp = new int[arr.length];for(int i=0;i<arr.length;i++){//提取出个位放入temp数组temp[i] = arr[i]%10;}//将arr数组的元素存入相应的桶中store(arr,temp,list);//对每个桶中的元素排序，并重新存入arr数组sort(arr,list);//清空桶中的所有数据，以便下一次使用clearTong(list);System.out.println(Arrays.toString(arr));//按照十位排序for(int i=0;i<arr.length;i++){//提取出十位放入temp数组temp[i] = (arr[i]%100)/10;}store(arr,temp,list);sort(arr,list);clearTong(list);System.out.println(Arrays.toString(arr));//按照百位排序for(int i=0;i<arr.length;i++){//提取出百位放入temp数组temp[i] = (arr[i]%1000)/100;    }store(arr,temp,list);sort(arr,list);clearTong(list);System.out.println(Arrays.toString(arr));//按照千位排序for(int i=0;i<arr.length;i++){temp[i] = (arr[i]%10000)/1000;  }store(arr,temp,list);sort(arr,list);clearTong(list);System.out.println(Arrays.toString(arr));}/** 清空桶*/private static void clearTong(ArrayList<ArrayList> list) {for(int i=0;i<list.size();i++){list.get(i).clear();}   }/** 遍历arr数组，将元素存入对应的桶中*/private static void store(int[] arr,  int[] temp, ArrayList<ArrayList> list) {//获取只保存个位数的数组temp//遍历temp数组，根据各位数将arr数组分桶for(int i=0;i<temp.length;i++){list.get(temp[i]).add(arr[i]);}}/** sort方法对每一个桶中的数据进行排序*/private static void sort(int[] arr, ArrayList<ArrayList> list){//count来保存arr数组下标，因为这里我们排好一个桶之后就将该桶中的有序序列//直接放入arr数组中，然后继续排下一个桶int count =0;// 遍历每一个桶，对桶中元素排序for(int i=0;i<list.size();i++){//桶中的元素不止一个，则排序；否则不用排序if(list.get(i).size()>=1){//类Collections提供的Sort方法可以将list类型的数据按照字典顺序排序//也可以自己定义比较器comparator，此时就将按照比较器定义的方法排序Collections.sort(list.get(i));//桶内排序完成之后就将有序数列存入arr数组for(int j=0;j<list.get(i).size();j++){
//                  System.out.println(count);
//                  System.out.println((int) list.get(i).get(j));arr[count] = (int) list.get(i).get(j);count++;}}}}
}

控制台结果：

效率比较：

本人没有对复杂度进行分析，感兴趣的朋友可以仔细的分析一下。

稳定性的理解：相同的元素排序前后位置的对比。假如一个int数组中有两个数据a1=a2；排序前a1在a2前面，排序后a1仍然在a2前面则是稳定的；否则就是不稳定的！

若有不足，欢迎指正。