也许你已经学会了这些常见的排序算法，或者你已经看过别人写的文章，但是这篇文章绝对不会浪费你的时间，你一定会有所收获。正如我之前写的，这不是要庆祝中国新年。元大厨想给元记餐厅的同事一些年终奖，让大家回家过个好年。让餐厅里的服务员，二蛋也回家娶媳妇了。元记餐厅元厨：小二，马上就要过年了，我们餐厅要给大家发年终奖了。大家可以去我们的红黑豆小册子看看每个人应该发多少年终奖，然后按照金额从小到大排列，钱会依次一笔一笔的发。大家都回去过个好年，你年纪也不小了，还是回去娶个媳妇吧。小二：掌柜辛苦了，我这就去。上面所说的按照金额从小到大的排序，就是我们今天要说的---排序。排序是我们生活中经常遇到的问题。在体育课上，老师会让我们从矮到高排列。收到你心仪学校的大信封），我们在网购的时候，有时候会按照销量从高到低，价格从低到高的顺序列出最符合我们预期的商品。的例子。排序概念：通过一定的方法（排序算法）将杂乱无章的数据元素按关键字的顺序排列的过程称为排序。比如上面的销量和价格就是关键词。排序算法的稳定性排序算法的稳定性是什么？因为待排序的记录序列中可能有两条或多条关键字相等的记录，排序结果可能不唯一，所以我们排序之后，如果相等元素的原始顺序不变。使用的排序方法称为稳定的，否则称为不稳定的。见下图。比如上图中，我们的数组中有两个相同的元素4，我们用不同的排序算法对它们进行排序。算法一排序后，两个相同元素的相对位置没有变化，我们称之为稳定排序算法，如果算法二排序后相对位置发生变化，则为不稳定排序算法。那么排序算法的稳定性有什么用呢？我们的大部分问题只是对数组进行排序。我们只需要考虑时间复杂度、空间复杂度等指标即可。一般不考虑排序算法是否稳定。但是排序算法的稳定性在实际软件开发中是一个特别重要的衡量标准。继续我们之前的例子。我们要将年终奖从少到多排序，然后将同一年终奖范围内的红豆数量从少到多排序。排序算法的稳定性在这里至关重要。为什么是这样？如下图第一次排序后，所有员工按照红豆的数量从少到多排序。在第二次排序时，我们采用了稳定的排序算法，所以第二次排序后，年终奖相同的员工仍然保持红豆的顺序（相对位置不变），红豆仍然从小到大排序到大。我们使用稳定的排序算法，只需要排序两次。稳定排序允许第一个键排序的结果服务于那些在第二个键排序中值相等的数字。在上面的情况下，如果我们使用不稳定的排序算法，要达到这样的效果是非常复杂的。比较和非比较我们根据元素是否依赖于与其他元素的比较来确定元素的相对顺序。这样就区分了比较排序算法和非比较排序算法。内排序和外排序内排序就是排序的全过程，所有要排序的记录都放在内存中。外部排序是由于排序记录的数量不能同时放在内存中。整个分拣过程需要在内部和外部存储器之间进行多次数据交换。常见的内排序算法包括：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。对于我们的内排序，主要受三个方面的影响：时间性能、辅助空间和算法复杂度。时间性能在我们的排序算法执行过程中，我们主要执行两个操作：比较和交换。比较是排序算法中最重要的部分。至少，移动是指记录从一个位置移动到另一个位置。所以我们高效的排序算法应该尽可能少的比较和移动。辅助空间执行算法所需的辅助空间大小也是衡量排序算法性能的重要指标。这里的算法复杂度不是指算法的时间复杂度，而是算法本身的复杂度，过于复杂的算法也会影响排序的性能。接下来我们来回顾一下冒泡排序和简单选择排序这两个简单的排序算法，看看有没有之前忽略的地方。后面会继续连载，总结常见实用的排序算法。冒泡排序（BubbleSort）当我们在各种算法书上学习排序时，最先想到的就是冒泡排序。主要是这个排序算法的思路最简单，也最容易理解，（可能名字好听，哈哈），和学过它的老哥们一起温习一下吧，让我们深挖一下bubble一起排序。冒泡排序的基本思想是将相邻记录的关键字两两比较，如果倒序就交换，直到没有倒序为止。冒泡排序一个冒泡会将至少一个元素移动到它应该在的位置，所以如果数组有n个元素，那么重复n次肯定会完成排序。根据定义，冒泡排序显然是一种比较排序。最简单的排序实现看一下这段代码+1;jnums[j]){swap(nums,i,j);}}}returnnums;}publicvoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}我们思考一下上面的代码，让关键字nums[i]和nums[j]进行比较和交换ifnums[i]>nums[j]，使得nums[0]一定是一个循环后的最小值。那么这段代码是冒泡排序吗？很明显不是。我们冒泡排序的思想是将相邻记录的关键词成对比较。注意里面有相邻的记录，所以这段代码不是我们的冒泡排序。下面我们用动画来模拟冒泡排序的执行过程。看完你绝对能写出地道的冒泡排序。冒泡排序代码classSolution{publicint[]sortArray(int[]nums){intlen=nums.length;for(inti=0;inums[j+1]){swap(nums,j,j+1);}}}returnnums;}publicvoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}上图中的代码是正宗的冒泡排序代码，但是我们有没有发现这个问题呢？这时候数组已经完全有序了，可以直接返回了，但是动画并没有返回，而是继续执行，那我们怎么做才能让它完全有序，直接返回而不是继续执行呢？想象一下，我们比较nums[j]和nums[j+1]，如果大于则交换。我们想象一下，如果一个完全有序的数组，我们进行冒泡排序，不需要每次比较都交换。那么如果没有发生交换，则说明当前订单已经完全有序。那我们是不是可以用一个flag来判断是否发生了exchange呢？当然有可能。让我们改进冒泡排序。改进后的冒泡排序代码classSolution{publicint[]sortArray(int[]nums){intlen=nums.length;//flag位booleanflag=true;//注意for循环条件for(inti=0;inums[j+1]){swap(nums,j,j+1);//发生交换，变为真，下次继续判断j]=temp;}}这样我们就可以避免在顺序已经顺序的情况下进行无意义的循环判断。时间复杂度分析最好的情况是待排序的表完全有序时。根据改进后的代码，我们只需要遍历一次，只需要n-1次比较，时间复杂度为O(n)。在最坏的情况下，即待排序列表的倒序，需要比较(n-1)+(n-2)+....+2+1=n*(n-1)/2，并进行等级交换，时间复杂度为O(n^2)。平均需要n*(n-1)/4次交换操作，比较操作大于等于交换操作，复杂度上限为O(n^2)，所以平均时间复杂度是O(n^2)。空间复杂度分析因为冒泡排序只是相邻元素之间的交换操作，所以只使用了恒定级别的额外空间，所以空间复杂度为O(1)稳定性分析那么冒泡排序稳定吗？当然是Stable，在我们的代码中，当nums[j]>nums[j+1]时，会进行交换，相等时不交换，相等元素的相对位置没有改变，所以冒泡排序是稳定的。简单选择排序（SimpleSelectionSort）我们的冒泡排序是不断交换的，最后的排序是靠交换完成的。我们简单选择排序的思路也很好理解。选择关键字最小的记录作为有序序列的第i条记录，见下图，例如上图，绿色代表已排序的元素，红色代表未排序的元素。我们当前的指针指向4，所以我们遍历红色元素，从中找到最小值，并与4交换。我们发现选择排序执行一个循环后至少可以返回1个元素。我们来看看代码的执行过程。看完之后，我们一定能写出代码来。注意：为了更容易理解，min值保存的是值，不是索引。实际代码保存索引。简单的选择排序代码classSolution{publicint[]sortArray(int[]nums){intlen=nums.length;intmin=0;for(inti=0;inums[j])min=j;}if(min!=i)swap(nums,i,min);}returnnums;}publicvoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}时间复杂度分析从简单选择排序过程来看，它最大的特点是交换移动元素的次数相当少，节省了排序时间，简单选择不同于冒泡排序。我们发现无论是最好的情况还是最坏的情况，元素之间的比较次数都是一样的。第i次排序需要n-i次比较，n代表元素个数。那么一共需要比较(n-1)+(n-2)+....+2+1=n*(n-1)/2次。对于交换，最好的情况是0次交换，最坏的情况（倒序）是n-1次交换。那么简单选择排序的时间复杂度也是O(n^2)，但是交换次数比冒泡排序小很多，所以它的效率比冒泡排序要好。空间复杂度分析从我们的动画中可以看出，我们的简单选择排序只使用了恒定级别的额外空间，因此空间复杂度为O(1)。稳定性分析大家想一想，我们的简单选择排序稳定吗？显然不稳定，因为我们需要找到指针后面的最小值，和指针指向的值交换，如下图。这时候我们需要从后面的元素中找出最小的元素和指针指向的元素也就是元素2交换。但是我们交换之后发现两个相等的元素3的相对位置有变了，所以简单选择排序是一种不稳定的排序算法。本文转载自微信公众号“元初的算法之家”，可通过以下二维码关注。转载本文请联系元初算法之家公众号。
