各类排序算法

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。内排序有可以分为以下几类：

(1) 插入排序：直接插入排序、二分法插入排序、希尔排序。

(2) 选择排序：简单选择排序、堆排序。

(3) 交换排序：冒泡排序、快速排序。

(4) 归并排序

(5) 基数排序

当然，所需要辅助空间最多的是：归并排序

所需要辅助空间最少的是：堆排序

平均速度最快的：肯定是快速排序啦

具有不稳定性的：快速排序，希尔排序，堆排序

接下来我们就针对几个常用且重要的排序方法进行简单的讲解：

一、插入排序

1、思路：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

2、实例：

3、Java实现

二、简单选择排序

1、思路：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；

然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

2、实例：

3、Java实现

三、希尔排序（最小增量排序）

1、思路：算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

2、实例：

3、Java实现

四、冒泡排序

1、思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

2、实例：

3、Java实现