总结五种比较高效常用的排序算法

　　说到排序算法，大家估计都比较熟悉，但要你一下子写出来又蒙圈了。所以这篇文章不会讲解所有的排序算法，而是挑选最热门的五种：冒泡排序、选择排序、插入排序、快速排序、归并排序。
　　我们通过图文流程解释的方式，让大家能快速领悟到各个排序算法的思想，从而达到快速掌握的目的。此外每个排序算法都有对应的Github代码实现，可供大家调试理解算法。同时也附上了文章中所画图的draw。io数据文件，方便大家根据自己的习惯进行修改。
　　排序算法的仓库地址：javacodechipsrcmainjavatechshuyijavacodechipsortatmasterchenyurongjavacodechip
　　如果你已经不是第一次学习排序算法，那么我建议你按照这样的思路学习：通过图解或调试，弄清楚每个算法的思想。下载Github例子，尝试自己手写实现。定期复习手写实现，不断巩固知识点。
　　好了，废话不多说，让我们开始今天的图解排序算法吧！选择排序
　　选择排序，意思是每次从待排序的元素选出极值作为首元素，直到所有元素排完为止。其详细的排序逻辑如下图所示：第1次，index下标对应值为9，找出所有最小值为1，将9与1交换位置，得到。同时，index下标加一。第2次，index下标对应值为3，找出所有最小值为3，将3与2交换位置，得到。同时，index下标加一。第3次，index下标对应值为9，找出所有最小值为3，将9与3交换位置，得到。同时，index下标加一。一直这样循环下去，直到index下标到达数组边界，如所示。
　　注意：灰色部分表示已经完成排序的部分。
　　选择排序的算法比较简单，如下所示：publicstaticvoidselectSort（int〔〕arr）｛for（inti0；iarr。length1；i）｛intmini；每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。for（intji1；jarr。length；j）｛if（arr〔j〕arr〔min〕）｛minj；｝｝进行交换，如果min发生变化，则进行交换if（min！i）｛swap（arr，min，i）；｝｝｝
　　可调式代码地址：javacodechipSelectSort。javaatmasterchenyurongjavacodechip
　　简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n1次。综合下来，时间复杂度为O（n2）。冒泡排序
　　冒泡排序，就是像池塘里的水泡一样往上冒泡。我们可以理解成一个数不断地往上冒泡（比较交换），一直到最上面（末尾）。通过不断往上冒泡，每次冒泡都会将最值浮到最上层，最终达到完全有序。其详细的排序算法逻辑如下：第1轮，9大于3，那么将9与3交换，接着继续往下比较。9大于1，那么将9与1交换，接着往下比较，最终我们将9浮到数组顶端。此时index指向数组顶端，该数是有序的了，因此index减一。第2轮，3大于1，那么3与1交换，接着往下比较。最终，我们只需要比较到index位置即可，最终我们将7浮到数组顶端。同时index也减一，此时7、9是有序的。如此这样反复循环，直到index下标达到0即可。
　　在冒泡排序的过程中，如果某一趟执行完毕，没有做任何一次交换操作，那么就说明剩下的序列已经是有序的了。例如数组〔5，4，1，2，3〕，执行了两次冒泡之后，其数组变为〔1，2，3，4，5〕。此时，index下标指向3这个值。再执行第三次冒泡时，我们会发现123，我们一次交换都没有做，这就说明剩下的序列已经是有序的，排序操作已经完成，不需要再进行排序了。publicstaticvoidbubbleSort（int〔〕arr）｛for（inti0；iarr。length1；i）｛booleanflagtrue；设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。for（intj0；jarr。length1i；j）｛if（arr〔j〕arr〔j1〕）｛swap（arr，j，j1）；flagfalse；｝｝if（flag）｛break；｝｝｝
　　可调试代码地址：javacodechipBubbleSort。javaatmasterchenyurongjavacodechip插入排序
　　插入排序，即将元素一个个插入新的数组系列中，直到所有元素插完为止。例如下图的例子，第1次将元素9插入新的数组中
　　插入排序paramarrpublicstaticvoidinsertSort（int〔〕arr）｛for（inti1；iarr。length；i）｛intji；while（j0arr〔j1〕arr〔j〕）｛swap（arr，j，j1）；j；｝｝｝
　　可调式代码地址：javacodechipInsertSort。javaatmasterchenyurongjavacodechip
　　简单插入排序在最好情况下，需要比较n1次，无需交换元素，时间复杂度为O（n）；在最坏情况下，时间复杂度依然为O（n2）。但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。快速排序
　　快速排序，顾名思义其排序效率非常高，所以才叫快速排序。快速排序的核心思想是选取一个基准数，通过一趟排序将小于此基准数的数字放到左边，将大于此基准数的数字放到右边。之后再用遍历不断地对左右子串进行同样的操作，从而达到排序的目的。快速排序的时间复杂度在最坏情况下是O（N2），平均的时间复杂度是O（NlgN）。
　　例如下图中的例子，在第一趟排序里，我们选中了基准数为9，那么此次排序就把所有比9小的数放到了左边，所有比9大的数放到了右边。在第二趟排序里，我们选中了基准数为7，那么此次排序就把所有比7小的数放到了左边，所有比7大的数放到了右边。
　　我们以对931427整数串进行排序为例，详细讲解整个快速排序的流程：选取9为基准数，从right开始，从右到左找出第一个小于9的数。第一个数是7，小于9，符合条件。于是将找到的这个数值放到left位置上，同时left加一。从left开始，从左到右选取第一个大于9的数。可以看到子串中并没有一个大于9的数，于是left会一直累加到right的位置。当leftright时，单趟排序结束，将基准数填入left所在位置。最终整个字符串被以9为基准数，切割成两部分，左边部分比9小，右边部分比9大。
　　接着进行第二次排序，第二次排序的整体流程如下：选取7为基准数，从right开始，从右到左找出第一个小于9的数。第一个数是2，小于9，符合条件。于是将找到的这个数值放到left位置上，同时left加一，此时数组变为：231429。从left开始，从左到右选取第一个大于9的数。可以看到子串中并没有一个大于9的数，于是left会一直累加到right的位置。当leftright时，单趟排序结束，将基准数填入left所在位置。最终整个字符串被以7为基准数，切割成两部分，左边部分比7小，右边部分比7大。
　　剩余的子串都进行同样的处理逻辑，最终我们可以得到一个排序的整数串。
　　代码实现：vparamarr待排序的数组paraml数组的左边界（例如，从起始位置开始排序，则l0）paramr数组的右边界（例如，排序截至到数组末尾，则rarr。length1）publicstaticvoidquickSort（intarr〔〕，intl，intr）｛if（lr）｛inti，j，x；il；jr；xarr〔i〕；while（ij）｛从右向左找第一个小于x的数while（ijarr〔j〕x）｛j；｝if（ij）｛arr〔i〕arr〔j〕；i；｝从左向右找第一个大于x的数while（ijarr〔i〕x）｛i；｝if（ij）｛arr〔j〕arr〔i〕；j；｝｝arr〔i〕x；quickSort（arr，l，i1）；quickSort（arr，i1，r）；｝｝
　　可调式代码地址：javacodechipQuickSort。javaatmasterchenyurongjavacodechip
　　参考：快速排序如果天空不死博客园归并排序
　　归并排序，其英文名为MergeSort，其意思是将排序串拆分成最小的单位之后，再一个个合并成有序的子串。例如下图的整数串，将其拆分成最小的子串就是每个只有一个整数。之后再将每个单个的子串合并起来，例如：8与4合并起来成为有序子串4、8，5与7合并起来成为有序子串5、7。4、8和5、7再合并成为有序子串4、5、7、8。
　　可以看到在这个过程中，最关键是合并两个有序子串的算法。这里我们以〔4，5，7，8〕和〔1，2，3，6〕为例，讲解有序子串合并的算法流程。首先声明一个与原有数组相同的长度的临时数组temp。接着i指向子串1开始的位置，j指向子串2开始的位置。接着比较arr1〔i〕与arr2〔j〕的值，找出较小值。因为两个子串都是有序的，所以这两个值中的最小值，就是整个串中的最小值。找出最小值后将其值放入temp的开始位置，最小值对应的子串下标加1。这里可以看到是41，即子串arr2的值较小，那么将1放入temp〔0〕位置，接着j加一，此时j指向2。接着继续对比i和j两个数的大小，继续对比步骤2的逻辑。这里可以看到arr〔i〕4arr〔j〕2，那么应该将较小值放入temp数组中，即将2放入数组中，并且将j1，即j2，此时j指向的值为3。按着上述的步骤继续不断重复步骤2的内容，我们会看到子串2首先到末尾。此时子串1还剩下一些数值，这些数值肯定是更大的值，那么直接将这些数值复制到temp数组中即可。如果子串1先到末尾，那么就应该将子串2剩余的数值写入temp数组。最后，将temp的数值写回原有数组中即可。
　　代码实现：publicstaticvoidsort（int〔〕arr）｛在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间int〔〕tempnewint〔arr。length〕；sort（arr，0，arr。length1，temp）；｝privatestaticvoidsort（int〔〕arr，intleft，intright，int〔〕temp）｛if（leftright）｛intmid（leftright）2；左边归并排序，使得左子序列有序sort（arr，left，mid，temp）；右边归并排序，使得右子序列有序sort（arr，mid1，right，temp）；将两个有序子数组合并操作merge（arr，left，mid，right，temp）；｝｝privatestaticvoidmerge（int〔〕arr，intleft，intmid，intright，int〔〕temp）｛左序列指针intileft；右序列指针intjmid1；临时数组指针intt0；while（imidjright）｛if（arr〔i〕arr〔j〕）｛temp〔t〕arr〔i〕；｝else｛temp〔t〕arr〔j〕；｝｝将左边剩余元素填充进temp中while（imid）｛temp〔t〕arr〔i〕；｝将右序列剩余元素填充进temp中while（jright）｛temp〔t〕arr〔j〕；｝t0；将temp中的元素全部拷贝到原数组中while（leftright）｛arr〔left〕temp〔t〕；｝｝
　　可调试代码地址：javacodechipMergeSort。javaatmasterchenyurongjavacodechip算法对比选择排序与冒泡排序的区别？
　　选择排序是每次选出最值，然后放到数组头部。而冒泡排序则是不断地两两对比，将最值放到数组尾部。本质上，他俩每次都是选出最值，然后放到一边。
　　其最大的不同点是：选择排序只需要做一次交换，而冒泡排序则需要两两对比交换，所以冒泡排序的效率相对来说会低一些，因为会做多一些无意义的交换操作。快速排序与归并排序的区别？
　　刚刚看了一下，快速排序和归并排序，我觉得差别可以提现在拆分合并的过程中，比较的时机。
　　快排和归并，都是不断拆分到最细。但是归并更纯粹，拆分时不做比较，直接拆！而快排还是会比较一下的。所以在拆分阶段，快排会比归并耗时一些。
　　而因为快排在拆分阶段会比较，所以其拆得没有归并多层级，因此其在合并阶段就少做一些功夫，会快一些。
　　所以快排和归并排序的区别，本质上就是拆分、合并的区别。
　　原文链接：https：www。cnblogs。comchanshuyiptopfivesortalgorithm。html