面试时遇到了排序的问题，平时用的不多，事先又没有总结，结果大家懂得的。回来看了一下，其实思路也都很简单，但是面试的时候没有答好，让人鄙视了（虽然面试官没那么坏，只不过我自己心虚而已）。
冒泡排序
每次遍历完序列都把最大（小）的元素放在最前面，然后再对剩下的序列从父前面的一个过程，每次遍历完之后待排序序列就少一个元素，当待排序序列减小为只有一个元素的时候排序就结束了。因此，复杂度在最坏的情况下是O（N ^ 2）。 假设一个乱序的数组，先从第0位开刀，那第0位与第1位比较，如果小，不动；如果大，第0位和第1位对调位置。这样保证第0位是最小的那个。然后再跟第2位比较。一样，如果小就不动，如果大的话还对调。直到数组结束。这样一圈下来保证第0位是整个数组最小的组。第0位搞定了，开始第1位了。这样两个for循环搞定了。
插入排序
插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排序好的了，那么就查找前面的N-1个元素把这第N个元素放在合适的位置，如此下去直到遍历完序列的元素为止。
假设有一个乱序的数组，开辟一个新的数组。把乱序数组里第0个拿出来，仍到新数组的第0位。然后开始了，刚才那步是热身。把乱序数组里的第1位拿出来，跟新建数组的第0位比较，找个适合的位置放进去。接着拿乱序数组第2个元素，同样在新建数组里找个合适的位置。这样这个新建数组一直保持在一个有序的状态。直到整个乱序数组被遍历一遍。
堆排序
新建一个有序的数组，把当前乱序的数组里，找出最大的元素，放到新建的那个有序数组里的最前或最后。这样乱序的数组每次减少一个元素，有序数组每次增加一个元素。直到乱序的数组被遍历一遍后，整个工作OK了。
快速排序
先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
大体思想是这样的：把整个乱序的数组分成2部分，怎么分？找一个元素，以它为分割线，把比它小的和比它大的元素分成2组，这样保证前面一半的元素比后面一半的小或者大，这里的一半不需要是数组长度的1/2。然后按照相同的方法对这两部分再次进行分割。把这个算法称为快速排序是因为这样能大大减少元素与元素之间的比较。
选择排序
从乱序的数组里找到最小的元素，跟第0位的元素交换位置。然后从剩下的元素里，再找到最小的，跟第1位元素交换位置。直到整个数组遍历一遍，排序工作完成。
这里写了几个常见的排序算法，总结得不是很全面，大概思想就是这些，具体在写代码的时候，还有很多些细节需要注意的。
- EOF -
本站文章除注明转载外，均为本站原创或编译。欢迎任何形式的转载，但请务必注明出处，尊重他人劳动。
转载请注明：文章转载自 Binkery 技术博客 [https://binkery.com]
本文标题： 排序算法总结
本文地址： https://binkery.com/archives/13.html