几种排序算法复习

       对排序算法的复习——插入排序、希尔排序、堆排序、归并排序、快速排序、桶式排序、外部排序。

 

一、最简单的插入排序

 

       插入排序由N-1趟排序组成，对于p=1到N-1趟，插入排序保证从0到位置p上的元素为已排序状态。什么意思呢，比如说我们要对如下一组整数进行插入排序（排序后要从小到大）：

34, 8, 64, 51, 32, 21

       当排序第一趟的时候，我们比较前两个数，也就是34和8，我们发现，34大于8，那么第一趟排序后的结果就是：

8, 34, 64, 51, 32, 21

        当排序第二趟的时候，我们比较前三个数，也就是8,34和64，我们将64与34比较，发现64大于34，那么这趟排序就结束了（因为经过第一趟排序，我们知道34一定比前一个数大，也就是排序算法的定义规则），那么第二趟排序后的结果就是：

8, 34, 64, 51, 32, 21

        当排序第三趟的时候，我们比较四个数，也就是将第四个数51，与第三位数比较，我们发现51小于64，既然小于，那么再让51与34比较，发现51大于34，那么到此，第三趟排序结束了，所以第三趟排序后的结果就是：

8, 34, 51, 64, 32, 21

        以此类推，一直进行到第5趟（这些数的长度减一）为止，排序算法就结束了，数也就排序完了。这就是排序算法。

        插入排序算法的性能不高，算是比较耗时的了，我们可以想想，因为不管怎么样都要进行N-1趟排序，那么肯定耗时了。我的git库里面有代码：https://github.com/hejiawang/Arithmetic.git    感兴趣的道友可以帮我指正一下。

对于给出的示例的完整的排序过程如图：

 核心代码：

public static void insertionSort(int[] array) {
	int j;
	for (int i = 1; i < array.length; i++) {
		int temp = array[i];
		for (j = i; j > 0 && temp < array[j - 1]; j--) {
			array[j] = array[j - 1];
		}
		array[j] = temp;
	}
}

 
二、希尔排序

       希尔排序要使用一个增量序列（稍后就会明白），在使用增量h的一趟排序之后，对于每一个位置i 我们都有a[i] <= a[i+h]，所以相隔h的元素都被排序了。

       挺不好理解的，举个例子，比如我们要对如下的13个数从小到大进行希尔排序，

81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15

        首先我们使用增量序列5进行排序，什么意思呢？就是在上面的这个数列中找第五个数，也就是12，让12这个数的左右两边的数进行比较，比如我们将81和35进行比较，81大于35，那么我们就将这两个数调换位置，然后94和17比较，11和95比较，96和28比较，凡是坐边大于右边的，我们都将这两个数调换位置，经过这样排序之后，我们能够保证，以12为中心的左右两边的数，第一个小于小于第5+1个数，第2个数小于5+2个数，以此类推；这次排序之后，从第五位也就是数字12开始数，在数5个数，也就是28，让12与58比较，35与41比较。。。。重复上一个步骤；然后从28开始在数5个数也就是15，发现15后面没数了。那么第一次的希尔排序就算结束了。

       读起来感觉希尔排序挺麻烦的，但是，希尔排序确实挺麻烦的。。。^_^    但是如果选对了增量序列希尔排序的效率还是和可观的。难就难在怎么选择增量序列。

上面的例子经过希尔排序的各个步骤如下：

 核心代码：

public static void shellSort(int[] array) {
	int j;
	for (int gap = array.length / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < array.length; i++) {
			int tmp = array[i];
			for (j = i; j >= gap && tmp < array[j - gap]; j -= gap) {
				array[j] = array[j - gap];
			}
			array[j] = tmp;
		}
	}
}

 

 三、堆排序

       堆排序到现在还不太明白。。。不做记录了。以后机缘巧合弄明白了，在记下来。。。。

 

四、归并排序

       归并排序就是将一个数组分成两份（也可以多分弄成多路归并排序），将两个数组的第一个数进行比较，把较小的那个数移到一个新的空数组中，然后重复这个操作，最后得到的新数组，就是一个经过排序的数组了。这就是归并排序，在外部排序中用归并排序的思想比较多，下面给出一个示例图：

 

五、快速排序

       快速排序对Java货c++的基本类型的排序特别有用，快速排序就是在一个数组中选取一个数作为枢纽元，在这些数中，凡是比这个数小的，放在一边，比这个数大的放一边，然后在这两边中在按这种方式排序下去，知道排序完成。效率很好。

 

六、桶式排序

       要使用桶式排序，就要知道数组中最大的数是多少，然后构建一个比这个数大一的一个空数组Array，把这个数组的各个项初始化为0，于是，当读到一个数a时，就在数组的Array[a]位置上增一，在所有的输入数据读入后，扫描数组Array，打印出排序后的表，就是经过排序的数了。。很有意思的一种排序：

 七、外部排序

       所谓外部排序就是没有内存的概念了，但是可以用磁带啊什么的，其他的思想就和归并排序一样了，还有多路归并排序，就是把原来的数组分割成对份，思想就是这样了，不重复了。。。