首页 > 代码库 > [读书笔记]算法(Sedgewick著)·第二章.初级排序算法

[读书笔记]算法(Sedgewick著)·第二章.初级排序算法

2024-07-06 03:31:54   223人阅读

本章开始学习排序算法

 第二章mindmap分支

 

1.初级排序算法

  先从选择排序和插入排序这两个简单的算法开始学习排序算法。选择排序就是依次找到当前数组中最小的元素，将其和第一个元素交换位置，直到整个数组有序。

 1 public static void sort(Comparable a[]){
 2     int N = a.length;
 3     for(int i = 0; i < N; i ++){
 4         int min = i; //最小元素索引
 5         for(int j = i + 1; j < N; j++){
 6             if(less(a[j], a[min])) min = j;
 7         }
 8             
 9     exch(a, i, min);
10     }
11 }

 

而插入排序就像打poker一样，找到每个元素在小数组中的位置。

1     public static void sort(Comparable a[]){
2         int N = a.length;
3         for(int i = 1; i < N; i ++){
4             //将a[i]插入a[i-1]、a[i-2]、a[i-3]...之中
5             for(int j = i; j > 0 && less(a[j], a[j-1]); j--){
6                 exch(a, j, j-1);
7             }
8         }
9     }

 

算法思路相当简单，而本节比较有趣的地方是可视化排序算法。我们就实现这个可视化。

  我们分为三个步骤。第一步，将一个数组的元素(这里我们选用double数据类型)用长条表示，并依次罗列在屏幕上。第二步，按照各个算法的思路将有序数组排序，画出一张可视轨迹图。第三步，将轨迹图动画化。

  接下来的重头戏是比较选择排序和插入排序。通过下图的例子，我们可以看出第i个元素都进行一次交换和N-1-i次比较。对于长度为N的数组，选择排序要进行N^2/2次比较和N次交换。

选择排序轨迹

而对于插入排序呢？情况比选择排序复杂。最坏情况（完全逆序）下，需要~N^2/2次比较和~N^2/2次交换；而最好情况（已经顺序）下，需要N-1次比较和0次交换。就如同例子中第3次插入时，S、T已经是有序的了，所以不存在交换的需要。对于随机排序的数组，在平均情况下每个元素都可能向后移动半个数组的长度，因此交换总数是~N^2/4，而比较次数是交换次数加上一个额外的项（相比N^2，可以忽略）。

插入排序轨迹

而排序前数组的倒置（比如E-A）个数越少，插入排序就越快。接下来我们用随机数组来比较两种算法。

重复一百次的1000个随机数排序比较结果：

插入排序与选择排序比较

重复一百次的10000个随机数排序比较结果：

插入排序与选择排序比较2

最后，我们可以得出：对于随机数组，插入排序和选择排序的运行时间是平方级别的，两者之比是一个较小的常数（本机测试为1.3~1.4）。

 

希尔排序的思想是使数组中任意减个为h的元素有序，也就是将插入排序的元素移动距离由1改变为逐渐增大的h。

 1 public static void sort(Comparable a[]){
 2     int N = a.length;
 3     int h = 1;
 4     while(h < N/3) h = 3*h + 1;
 5     while(h >= 1){
 6         for(int i = h; i < N; i++){
 7                 for(int j = i; j >= h && less(a[j], a[j-h]); j -= h){
 8                     exch(a, j, j-h);
 9                 }
10         }
11         h = h/3;
12     }
13 }

 希尔排序轨迹

这么做的原因是因为部分有序数组更适合插入排序。那么，我们就比较一下这两种算法的执行速度。

 希尔排序与插入排序结果

 


联系
我们