经典算法（8） MoreWindows白话经典算法之七大排序总结篇

经典算法（8） MoreWindows白话经典算法之七大排序总结篇2014-01-03 csdn MoreWindows在我的博客对冒泡排序，直接插入排序，直接选择排序，希尔排序，归并排序，快速排序和堆排序这七种常用的排序方法进行了详细的讲解，并做成了电子书以供大家下载。下载地址为： http://download.csdn.net/detail/morewindows/4443208。

有网友提议到这本《MoreWindows白话经典算法之七大排序》电子书讲解细致用来平时学习是非常好的，但是页数有22页，不太合适做面试前的复习资料。因此在这里将这七种常用的排序方法进行下总结，以便大家更好的复习这些经典的排序算法，为面试打下良好的基础。

首先回顾下各种排序的主要思路：

一．冒泡排序

冒泡排序主要思路是：

通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。

冒泡排序改进1：在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。

冒泡排序改进2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

二．直接插入排序

直接插入排序主要思路是：

每次将一个待排序的数据，插入到前面已经排好序的序列之中，直到全部数据插入完成。

三．直接选择排序

直接选择排序主要思路是：

数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。

上面这三种排序都是非常简单的，下面这四种排序略有难度，希望读者能多多实践以加深理解。

四．希尔排序

希尔排序主要思路是：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”

五．归并排序

归并排序主要思路是：

当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。

六．快速排序

快速选择排序主要思路是：

“挖坑填数+分治法”，首先令i =L; j = R; 将a[i]挖出形成第一个坑，称a[i]为基准数。然后j--由后向前找比基准数小的数，找到后挖出此数填入前一个坑a[i]中，再 i++由前向后找比基准数大的数，找到后也挖出此数填到前一个坑a[j]中。重复进行这种“挖坑填数”直到 i==j。再将基准数填入a[i]中，这样i之前的数都比基准数小，i之后的数都比基准数大。因此将数组分成二部分再分别重复上述步骤就完成了排序。

七．堆排序

堆排序主要思路用张图示来表示更好：