排序算法思想

[红楼鬼影]

冒泡排序: 保证数组前部或后部有序，可以将小的元素冒泡到前部，或者将大的元素冒泡到后部。冒泡每趟都是相邻元素比较，一趟只贡献一个最大或最小的，剩余再接着冒泡，直至元素穷尽。

冒泡排序就是从序列中的第一个元素开始，依次对相邻的两个元素进行比较，如果前一个元素大于后一个元素则交换它们的位置。如果前一个元素小于或等于后一个元素，则不交换它们；这一比较和交换的操作一直持续到最后一个还未排好序的元素为止。

选择排序: 与冒泡排序极像，可以说是冒泡排序的优化。冒泡排序是每趟多次相邻元素交换，来获取最小的元素，而选择排序，则是每趟只记录最小元素的索引，最终交换一次，大大减少了无意义的交换。选排重在选。

插入排序: 保证数组前部有序，遇到无序元素，该元素与前面所有有序元素比较，到有序位置停止，前面比较的所有元素依次后移，在该位置插入无序元素。重复该过程直到后面的所有元素有序。插排得有插。

希尔排序: 插入排序的优化版，扩大间隔为gap。希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入 排序算法的一种更 高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

快速排序: 找中间点，一边小，一边大，二分，继续一边小，一边大，直至无法二分。

归并排序: 找中间点，二分，左边有序，右边有序，合并两个有序数组，想法非常自然质朴。