八种经典排序算法总结，妈妈再也不用担心我不会了
算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。
思路：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
- 排除最大的数，接着下一轮继续相同的操作，确定第二大的数…
- 重复步骤1-3，直到排序完成。
动画演示：
实现代码：
平均时间复杂度：O(n²)
空间复杂度：O(1)
算法稳定性：稳定
思路：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
动画演示：
实现代码：
平均时间复杂度：O(n²)
空间复杂度：O(1)
算法稳定性：稳定
思路：
第一轮，找到最小的元素，和数组第一个数交换位置。
第二轮，找到第二小的元素，和数组第二个数交换位置…
直到最后一个元素，排序完成。
动画演示：
实现代码：
算法复杂度：O(n²)算法空间复杂度：O(1)算法稳定性：不稳定
思路：
把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。
动画演示：
实现代码：
算法复杂度：O(nlog2n)算法空间复杂度：O(1)算法稳定性：稳定
，面试最喜欢问的排序算法。这是运用分治法的一种排序算法。
思路：
- 从数组中选一个数作为基准值，一般选第一个数，或者最后一个数。
- 采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
- 对左边的数列，重复上面1，2步骤。对右边重复1，2步骤。
- 左右两边数列递归结束后，排序完成。
动画演示：
实现代码：
算法复杂度：O(nlogn)算法空间复杂度：O(1)算法稳定性：不稳定
归并排序是采用分治法的典型应用，而且是一种稳定的排序方式，不过需要使用到额外的空间。
思路：
- 把数组不断划分成子序列，划成长度只有2或者1的子序列。
- 然后利用临时数组，对子序列进行排序，合并，再把临时数组的值复制回原数组。
- 反复操作1~2步骤，直到排序完成。
归并排序的优点在于最好情况和最坏的情况的时间复杂度都是O(nlogn)，所以是比较稳定的排序方式。
动画演示：
实现代码：
算法复杂度：O(nlogn)算法空间复杂度：O(n)算法稳定性：稳定
大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。
思路：
- 对原数组构建成大顶堆。
- 交换头尾值，尾指针索引减一，固定最大值。
- 重新构建大顶堆。
- 重复步骤2~3，直到最后一个元素，排序完成。
构建大顶堆的思路，可以看代码注释。
动画演示：
实现代码：
算法复杂度：O(nlogn)算法空间复杂度：O(1)算法稳定性：不稳定
思路：
- 找出最大值，最小值。
- 根据数组的长度，创建出若干个桶。
- 遍历数组的元素，根据元素的值放入到对应的桶中。
- 对每个桶的元素进行排序(可使用，插入排序等)。
- 按顺序合并每个桶的元素，排序完成。
对于数组中的元素分布均匀的情况，排序效率较高。相反的，如果分布不均匀，则会导致大部分的数落入到同一个桶中，使效率降低。
动画演示(来源于五分钟学算法，侵删)：
实现代码：
算法复杂度：O(M+N)
算法空间复杂度：O(M+N)
算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。
动画演示来源于算法学习网站：https://visualgo.net
讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应付笔试面试？平时开发也没用得上这些。
我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？
我的理解是：第一，普及一些常识性的问题。第二，锻炼思维，提高解决问题的能力。第三，为了区分人才。
回到学排序算法有什么用的问题上，实际上也一样。这些最基本的排序算法就是一些常识性的问题，作为开发者应该了解掌握。同时也锻炼了编程思维，其中包含有双指针，分治，递归等等的思想。最后在面试中体现出来的就是人才的划分，懂得这些基本的排序算法当然要比不懂的人要更有竞争力。
建议大家看完之后，能找时间动手写一下，加深理解。
本文为阿里云原创内容，未经允许不得转载。
java快速排序
快速排序是一种非常高效的排序算法，它的实现，增大了记录和比较和移动的距离，从而减少总的比较此时和移动次数。采用分而治之的思想，将一个大的问题拆成一个小的问题，小的问题拆成更小的问题。
public static void quickSort(int []array,int low,int high) {
if(low>=high){
return;
}
int left=low;
int right=high;
int base = array[low];
while (left!=right) {//从后面开始检索 遇到比基准数小的就停下，遇到比基准数大于等于的就继续检索
while (array[right]>=base&&left<right) {//left小于right 防止越界 比如数组内所有元素都比base小就会一路走下去
right–;
}
while (array[left] <= base&&left<right) {
left++;
}
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
//交换基准值和相遇位置的值
array[low]=array[left];//相遇的值一定小于基准值
array[left]=base;
quickSort(array,low,left-1);
quickSort(array,left+1,high);
}
快速排序
时间复杂度最好情况是都能分割成较完美的两部分 O（nlog(n)）,最坏情况是数组是有序的每次分割只有一边 O（n^2）
空间复杂度为O（nlog(n)） 稳定性：不稳定
快速排序再最坏的情况下可以优化，即优化基准值
三数取中法即low mid high 取中间大小的数字为基准值
看动画学算法之：排序 – 快速排序
快速排序也采用的是分而制之的思想。那么快速排序和归并排序的区别在什么地方呢？
归并排序是将所有的元素拆分成一个个排好序的数组，然后将这些数组再进行合并。
而快速排序虽然也是拆分，但是拆分之后的操作是从数组中选出一个中间节点，然后将数组分成两部分。
左边的部分小于中间节点，右边的部分大于中间节点。
然后再分别处理左边的数组合右边的数组。
假如我们有一个数组：29,10,14,37,20,25,44,15，怎么对它进行快速排序呢？
先看一个动画：
我们再分析一下快速排序的步骤。
我们选择的是最左边的元素29作为中间点元素，然后将数组分成三部分：[0, 14, 15, 20, 25],[29],[44, 37]。
中间节点29已经排好序了，不需要处理。
接下来我们再对左右分别进行快速排序。最后就得到了一个所有元素都排序的数组。
我们先来看最核心的部分partition，如何将数组以中间节点为界，分成左右两部分呢？
我们的最终结果，是要将array分割成为三部分。
首先我们选择最左侧的元素作为中间节点的值。然后遍历数组中的其他元素。
假如m=middleIndex，k=要遍历的元素index
考虑两种情况，第一种情况是数组中的元素比中间节点的值要大。
这种情况下，m不需要移动，k+1继续遍历即可。
第二种情况下，数组中的元素比中间节点的值要小。
因为m左边的元素都要比中间节点的值要小，所以这种情况下m需要+1，即右移一位。
现在m+1位置的元素要么还没有进行比较，要么就是比中间节点的值要大，我们可以巧妙的将m+1位置的元素和k位置的元素互换位置，这样仍然能够保证m左侧的元素要比中间节点的值要小。
将上面的分析总结成java代码如下：
最后我们需要将最左侧的元素和中间节点应该在的index的元素互换下位置，这样就将中间节点移动到了中间位置，并返回中间位置。
再来看下divide的代码：
divide的代码就很简单了，找到中间节点的位置之后，我们再分别遍历数组的左右两边即可。最后得到排好序的数组。
上面的例子中，我们的中间节点的选择是数组的最左元素，为了保证排序的效率，我们可以从数组中随机选择一个元素来作为中间节点。
上面的代码，我们在分区的时候，先选择出一个随机的节点，然后将这个随机的节点和最左侧的元素交换位置，后面的代码就可以重用上面的QuickSort的代码逻辑了。
从上面的分析我们可以看出，每次分区的时间复杂度应该是O(N)，而divide又近似二分法，所以总的时间复杂度是O(N logN)。
本文为阿里云原创内容，未经允许不得转载。
本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com
文章为作者独立观点不代本网立场，未经允许不得转载。
投诉举报&联系我们：
