额，首先最近在刷leetcode，所以接触的算法还是蛮多的，然后今天群里闲聊又说到这个，所以顺便做个整理！
目前为止其实我也就只写过冒泡选择插入归并快排和桶排。
最熟悉的归并本来我以为手到擒来，但是真的写的时候一点小错（就是合并的时候一遍完了之后另一边while全部续上的时候脑抽用了if，然后debug好久才找到错误原因）只能说细节决定成败。而且思路和实现是不一样的。在此面壁一分钟，为我之前的盲目的自信和现实的打脸。
然后闲话少于，我一个个说排序的思路和java代码的实现。为了写这个我其实也看了好多帖子，大家说的都挺好的，但是我这里还要重复的写个文章一来每个人的思路不一样，我自己肯定觉得我言语的表达比别人说的清楚（起码对于我自己来说是这样。）另一方面总结也是学习的过程。然后我不会按照顺序来，刚刚写了归并，所以第一个也会先写归并。我计划这个星期把这个帖子写完就满意了，所以不会着急，没事的时候写两个就好了。
归并排序
归并排序的实现：这个其实就是层次的问题，把一个很长的数组分段排好序，然后用比较插入的方式一次遍历把两个排好序的数组合并成一个。就这样递归最后整个数组排好序了。
其实这个名字叫的我觉得很形象。归并：递归合并。
当然了，归并排序使用的其实是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
下面是整个归并排序的图解（我画图很渣，理解意思就行了）
其实最开始我就说了，知道思路和真正写出代码是两件事，但是有了思路再照着思路来写代码只是时间问题，而没有思路则真的是很难解决的问题。说了这么多我直接贴上java实现归并的代码：
public static void sort(int[] nums,int l,int r) {
if(l>=r) return;
int mid = (r+l)/2;
//递归
sort(nums, l, mid);
sort(nums, mid+1, r);
//合并
merge(nums,mid,l,r);
}
public static void merge(int[] nums,int mid,int start,int end) {
int[] temp = new int[end-start+1];
int r = mid+1;
int l = start;
int idx = 0;
while(l<=mid && r<=end) {
if(nums[l]<nums[r]) {
temp[idx] = nums[l];
l++;
}else {
temp[idx] = nums[r];
r++;
}
idx++;
}
while(l<=mid) temp[idx++] = nums[l++];
while(r<=end) temp[idx++] = nums[r++];
for(int i = start;i<=end;i++) {
nums[i] = temp[i-start];
}
}
其实整个代码的逻辑我觉得都很清楚的，无非就是中间拆分到不可再分，然后合并。我一开始是合并的时候出了点小纰漏（while用的if），但是也不是因为难而是我个人的马虎。总体来说我觉得这个是一个很模块化的方法，一个专门用来递归，一个专门用来合并。反正这个代码就这样了，下一个算法了。
冒泡排序
想了想还是绝对先从简单的开始整理。毕竟冒泡选择插入我觉得是很符合人的常规思维的排序做法。就是一点数学功底没有的人也可以想到的。
冒泡排序我觉得就是在一堆数据中找到最大的那个，然后放到最后一个的位置（我说的是常用的升序排序，降序的话就是反过来。），然后从生下的一堆数据中继续找到最大的然后再放到最后，直到最后只剩下最后一个元素，那样肯定就是最小的元素了，直接放到第一的位置，排序完成。不过这个找最大的是个不断比较的过程。
冒泡排序总结起来就一句话（划重点）：，从左到右，数组中相邻的两个元素进行比较，将较大的放到后面。
这个感觉图解比较简单，其实不用图也能理解，不过为了统一格式我还是画一个：
接下来是java代码实现：
public static void sort(int[] nums) {
for(int i = nums.length-1 ;i>=0;i--) {
for(int j = i-1;j>=0;j--) {
if(nums[i]<nums[j]) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
}
冒泡的代码比较简洁，也可以说是无脑。然后我觉得其实常规写法应该是放在前头，顺序遍历。。但是我之前画图脑抽画成了放在后面，没办法，只能双层从后往前的循环。代码就是这么回事。没别的难度，冒泡排序就这样了。
选择排序
选择排序与冒泡排序有很大的相同点，甚至时间复杂度都是一样的，但是也还是不同的，两个都是遍历一次找到最大的元素（或最小的元素）。不过冒泡是不断交换的过程，而选择是遍历一次找到最大值，并记住下标，然后直接用最后位置的元素与最大值元素交换。一次选择只交换一次元素，一次冒泡不知道要交换多少次。
然后选择排序java代码实现：
public static void sort(int[] nums) {
for(int i = nums.length-1 ;i>=0;i--) {
int max = i;
for(int j = i-1;j>=0;j++) {
if(nums[max]<nums[j]) max = j;
}
int temp = nums[max];
nums[max] = nums[i];
nums[i] = temp;
}
}
上面图解上有个小bug，就是第一步应该只换8和99的位置。。不过我画的时候写顺手了。所以这里8,1都换了。但是既然画都画出来了也懒得重新画了，就这样吧。
关于冒泡和选择，我感觉这是一种很暴力的解法，但是好理解而且不难，所以就这样了，下一个算法。
插入排序
我理解的插入排序就是从第一个开始，一个一个把元素放到他本该放置的位置。保证已经插入过的元素组是排好序的。
挺喜欢百度百科上的一个比喻：比如扑克牌，牌组里牌是无序的，但我们抓一张牌在手中就会把它排好序摆放在手中。如果最后一个人抓完了一副扑克牌，同时会排好序。
这个其实用动图来解释比较好，但是问题是我不会做动图，甚至复制粘贴都不会。所以还是要用画图来展示：
这个我没画完，因为后面都是一样的道理，所以不浪费时间了。另外其实这个插入排序是有很大的优化空间的。不同于选择冒泡，我们可以在选择插入点的时候用一些遍历的算法。比如最基本的头尾比较（大于最后一个直接插入到最后，小于第一个直接插入到第一个。中间部分也可以用二分法降低时间复杂度。）我简单的写一下java实现的代码：
public static void sort(int[] nums) {
for(int i = 1 ;i<nums.length;i++) {
//说明现在顺序是对的，所以不变
if(nums[i]>nums[i-1]) continue;
int idx = -1;
int temp = nums[i];
//比最小值小直接插入到首个
if(nums[0]>nums[i]) {
idx = 0;
}else {
idx = findInsertIndex(nums, 1, i-1, temp);
}
//插入点后面的元素都要顺序后移
for(int j = i;j>idx;j--) {
nums[j] = nums[j-1];
}
nums[idx] = temp;
}
}
//二分找插入点
public static int findInsertIndex(int[] nums, int L, int R, int value) {
while(L <= R) {
int mid = L + ((R - L) / 2);
if(value > nums[mid]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return L;
}
我感觉我写的是很麻烦的，因为我能想到的优化都做了。首先是首尾判断，省的做无用功。其次是二分查找插入点。所以diamante我觉得好啰嗦，甚至比之前的归并都啰嗦。。。再附上一个无脑暴力版本的吧：
public static void sort(int[] nums) {
for(int i = 1; i < nums.length; i++) {
int n = nums[i];
for(int j = 0; j <i; j++) {
if(n>=nums[j])continue;
int temp = nums[j];
nums[j] = n;
n = temp;
}
nums[i] = n;
}
}
然后这个插入排序就这样了，继续下一个排序算法。
快速排序
快排是个很常用是排序，起码我个人而言用的不少。大概的思路就是选择一个元素（一般多为中间下标的元素，只不过最坏的情况是选择了个极端值），比这个元素大的找出来放一起，比这个元素小的找出来放一起。然后目前可知的就是这两堆是有序的，但是具体 到某个元素还是没序。所以继续递归，分组。最终分为只剩下单个元素，那么这个数组也就有序了（判断大小的过程中完成了数组元素的排列）
其实我觉得这个快排和归并是有一定的共同点的，比如都是分治的思想。只不过归并是用元素数目分，而快排是用元素值分。而且归并是稳定的。但是快排如上面我说的如果点背到选择的每个值都是端值（最大值最小值）那么性能会很可怕，所以是不稳定的。
接下来我直接贴java代码实现：
public void quickSort(int[] nums, int left, int right) {
if(left>=right) return;
int l = left;
int r = right;
int temp = nums[l];//把最左元素看成标准值
while(l<r) {
while(r>=left && nums[r]>temp) r--;//找到第一个小于目标值的元素
while(l<right && nums[l]<temp) l++;//前面都比temp小。找到第一个大于的元素
if(l <= r) {//这里添加等于是为了让r是
int cur = nums[r];
nums[r] = nums[l];
nums[l] = cur;
r--;
l++;
}
}
//到这里我们确定left-r的值都是小于等于
quickSort(nums, left, r);
quickSort(nums, l, right);
}
说一下和归并比较的好处：首先这个是不用额外的数组空间的。而归并是需要额外空间的，这是一个大优点。至于缺点应该就是不稳定性吧。反正实现就是上面的逻辑，我再去画个图解。我觉得代码上的注释写的很详细了。
因为这种递归问题画起来没完没了，所以我只画了一层。后面的递归都差不多逻辑。然后这个快速排序也就这么多，下一中排序了。
希尔排序
首先这个算法其实我在此之间没使用过。不过为了这篇文章看了一些介绍，我更理解这个希尔排序是分片的插入排序！更甚至我觉得这个有点类似于归并。只不过归并用递归的形式，而这个是迭代的形式。
把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序；随着步长逐渐减小，所分成的组包含的记录越来越多；当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；
其实这个看的话我是有点懵的，但是看了图解瞬间悟了。再看解法。。。觉得有点费解了都。。费解代码的复杂性。都说这么做是把插入排序分片，是一种简化，，但是在较少数字的情况下我只觉得是更复杂。老规矩，先贴图解（这个不是我自己画的，之前看资料觉得这个比较清楚了）。
额，想了想最终决定还是自己画了个图，丑归丑，但是起码是自己的劳动成果，而且也是一个复习巩固的过程。
其实这两个图是差不多的，而且我是真的不是很能理解这个排序的优点。非要说的话看运气吧也就是。如果数组情况极端的话，也就那样。下面是我的疑问：
当然也可能是我理解的不全面，如果有大佬清楚优点，欢迎指点。我单纯的知道是插入排序的优化，但是优化点在哪里不太懂。接下来是java代码实现：
public static void Xsort(int[] nums) {
int step = nums.length/2;
while(step>=1) {//步长为1是合并成一个排序序列。结束迭代
//第一个元素肯定是从0开始。步长是增量
for(int i = 0;i<step;i++) {
//从一个排序的第二个开始往前比较（第一个是i）
for(int j = i+step;j<nums.length;j += step) {
int temp = nums[j];
int k = j-step;//从同一个排序的前一个开始判断要不要插入
//这就是一个插入排序的过程。只不过把正常的顺序+1变成了+step
while(k>=0 && nums[k]>temp) {
nums[k+step] = nums[k];
k -= step;
}
nums[k+step] = temp;//该插入的地方赋值
}
}
step /= 2;
}
}
其实我觉得希尔排序的代码不复杂，不过因为我以前没写过，所以在写的时候要理思路，我也都用注释的形式写出来了。写注释其实不仅仅是为了看得人方便，也是可以让写的人思路清晰。
然后关于希尔排序，我也是刚刚查了一下才发现这个算法最上面的图片上的时间复杂度是有点问题的，下面是百度百科上的，我觉得还靠谱一些。
然后这个也就到这里了，继续下一个排序算法。
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
我用我自己的话来表述一下，首先数组元素构建二叉树。保证根节点大于或者小于左右节点。如果二叉树满足这个特性，那么根节点不是最大值就是最小值。这样找出最大最小值后放到数组的首或者尾。然后剩下的元素再构建树，再找最大值/最小值。再放到首或者尾。依次这样，最终整个数组实现排序。
其实这个和选择排序挺像的。只不过如果是没有优化的选择排序是从头对比到尾，就是很麻烦。而而过用大顶堆或者小顶堆的方式选择出最大/最小值是时间复杂度会下来（弱弱的说一句，我觉得也就是优化后的选择排序，上面我有用二分法选择，感觉这两个差不多的）。
然后我去画个图:
其实我真的觉得所谓的堆排序就是选择排序中选择最大/最小值时候的一个优化而已。也比较好理解，接下来是java实现堆排序的代码：
public static void sort(int[] nums,int len) {
//构建大顶堆
for(int i = len/2;i>=0;i--) {
Adjust(nums,i,len);
}
//当i=1的时候，下次构建树的长度是0，构不成树，所以i要大于1
for(int i = len;i>1;i--) {
//交换堆顶最大元素和堆尾最小元素
int temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
//下次构建树不用管最后一个元素了。这是个递减的过程
Adjust(nums, 0, i-1);
}
}
public static void Adjust(int[] nums,int start,int len) {
int temp = nums[start];
for(int i = 2*start;i<len;i *= 2) {
if(i<len && nums[i]<nums[i+1]) i++;
if(temp>= nums[i]) break;
//将较大元素赋值给父节点
nums[start] = nums[i];
start = i;
}
nums[start] = temp;
}
代码中的从len/2开始遍历还有i= 2*start是根据二叉树的性质来的。首先这个树要建成完全二叉树（除了最后一层每一层都是满树。）这样的直接表现就是第一个非叶子节点是第len/2个元素。然后我们去判断这个元素下面两个叶子元素的大小，如果叶子元素大于跟节点元素则要换位置的。
这里2start则是当前元素的子节点的下标位置。另一个子节点是2start+1.
如果左节点大于右节点，则指针指左节点，不然指针指右节点。
如果根节点大于指针指向的节点说明根节点最大，直接break。否则较大值和根节点的值交换。这样保证了根节点是最大的。但是这样又有问题了，如果只有一层的根节点可以这么做，但是如果是多层，并且当节点发生交换，原本是大顶堆的节点被换走了，剩下的不满足大顶堆的要求了怎么办呢？还要继续往下判断的。所以是for循环判断。直到最底层的非叶子结点才算判断完毕。
最后当整个数组堆排以后，第一个元素就是根节点，也就是最大的那个元素了。和最后一个节点交换。再次建树,这个时候就不用管最后一个元素了，所以总长度-1、什么时候只剩下一个元素了则自动排第一位。排序也就完毕了。
其实整个过程不难，也就是建大顶堆的时候可能略显费解，不过如果知道完全二叉树的特性也很容易的。这个算法就到这了，下一个。
计数排序
其实这个计数排序我经常用，但是也是前不久才知道这个叫做计数排序！一个常用的称呼叫做：数组下标代替数值！对的，就是这么个情况。这个其实使用起来时间复杂度很低，性能不错，但是限制太多了。比如这个需要的额外空间是整个数组的数值范围。而且要求数组的数必须是整数（不非要正整数，只不过如果还涉及到了负数则操作更繁琐了。）比如数组的值是1-10000000.那么需要的额外数组的大小也是10000001.简直吓人。不过如果数值范围不大的话，确实性能不错。
大体思路就是用另一个数组的下标存储当前数值，数组的值存储出现的次数。这样这个数组的所有的数值都按照顺序排好了，然后重新通过读取那个计数的数组来重新赋值。整个数组的排序也就做好了。
我直接贴代码：
public static void sort(int[] nums,int k) {
int[] d = new int[k+1];
for(int i : nums) {
d[i]++;
}
int idx = 0;
for(int i = 0;i<d.length;i++) {
while(d[i]-->0) {
nums[idx++] = i;
}
}
}
讲真，这个做法其实很容易理解而且代码简单，但是局限也蛮大的。首先要知道数组的值的范围。其次这个范围不能太大，还有元素只能是整数。
如果都满足的话这个方法还是不出错的。感觉刷题的时候经常使用这个方法。另外判断出现次数最多的元素，只出现一次的元素，出现指定次数的元素之类的也都可以。至于图解，我去画一个吧。感觉不画个图就缺了点什么。
桶排序
其实这个桶排我个人觉得更像是计数排序的一种优化。计数排序的最大问题就是占用的空间太多。比如说数值范围1000000。就需要这么大的一个数组。但是桶排是把一个范围放进一个桶。如果是1000000数值范围。那么1000个放在一个桶。则只需要10000个空间了。但是要注意1000个放在一个桶，那么每个桶里也是要排序的。不过我之前用桶排一直都搭配PriorityQueue使用（PriorityQueue是java中的优先队列，就是进入队列的元素自动排序。）我记得以前看过PriorityQueue的实现，好像就是通过小顶堆实现的。感觉其实算法什么的好多地方都是通用的。
反正桶排的思路我觉得就是计数排序的进化。理解计数以后桶排其实挺好理解的。
我直接去画个图：
对了，桶排也是要求数值要有一个固定的范围的，只不过比计数排序的范围可以大一点。另外一些关于桶排的说法：
- 桶排序是稳定的；
- 桶排序是常见排序算法中最快的一种，大多数情况下比快排和归并排序还要快
- 桶排序非常快但是也非常消耗空间，典型的以空间换时间，基本上是最耗内存的一种排序算法。
java代码的实现：
public static void sort(int[] nums) {
//我计划一个桶十个元素
Map<Integer,PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();
int max = -1;
for(int n : nums) {
max = Math.max(n/10, max);
if(map.get(n/10)==null) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
map.put(n/10, priorityQueue);
}
map.get(n/10).offer(n);
}
int idx = 0;
for(int i = 0;i<=max;i++) {
PriorityQueue<Integer> p = map.get(i);
if(p == null) continue;
while(!p.isEmpty()) {
nums[idx++] = p.poll();
}
}
}
这个其实我觉得我写的比较麻烦，主要是用了优先队列。其次就是我个人认为排序算法纯粹是思路，其实实现的方式是多种多样的！不是说不这么写就不是桶排，同样用不用map，list，PriorityQueue都是自己的选择。同样上上一道题堆排的时候大顶堆，小顶堆，大到小，小到大什么的也都是个人选择。而且我的这些代码我是自己在编译器上跑的，用了一些例子，都ok 的，但是也可能有的地方细节上忽略了什么所以出现一些问题！如果真的是用了我上面的代码运行报错千万要指出来！也不要因为这个骂我啥的，哈哈。最后一个排序算法了。
基数排序
基数排序是一种很有意思的排序，是按照位数排序的。也是要看整个数组中数字范围的。比如最大是一位，则一次排序。最大是两位，则两次排序（个位排一次，十位拍一次），三位则三次排序（个十百分别一次）。
其实这个比较简单，我直接画图解：
然后这个原理不难理解，我直接贴java代码：
public static void sort(int[] nums,int n) {
int[][] temp = new int[10][nums.length]; //数组的第一维表示0-9
int[] order = new int[10]; //0-9个纬度中下标
int m = 1;
int x = 1;
while(m <= n){
for(int i = 0; i < nums.length; i++){
int lsd = (nums[i]/x) % 10 ;
temp[lsd][order[lsd]] = nums[i];
order[lsd]++;
}
int k = 0;
//整理数组
for(int i = 0; i < 10; i++){
if(order[i] != 0)
for(int j = 0; j < order[i]; j++)
{
nums[k++] = temp[i][j];
}
order[i] = 0;
}
//下一位数，所以乘10
x *= 10;
m++;
}
}
写的时候关于java获取数值类型指定位数的值我是用数/位数%10.这个很好理解的。不过一开始我想错了所以这块改了两次，印象比较深刻。剩下别的都没啥难度。
然后这篇笔记就记到这里，十大算法也算是都理解了一遍，而且都画了图，其实我觉得画图是理解思路的一个比较好的方式。虽然很丑。哈哈，另外在重复一遍！！我个人认为排序算法纯粹是思路，其实实现的方式是多种多样的！思路是一样的就行了。尤其是很多细节处理都可以自由发挥的。另外如果发现我代码上有什么漏洞也欢迎指出！我会留意私信和留言，如果稍微帮到你了记得点个喜欢点个关注！也祝大家工作顺顺利利，生活健健康康！另外打个广告。java技术交流群130031711招人，欢迎各位萌新大佬踊跃加入！
