算法红皮书第四版读书笔记（二）排序

约定不等于承诺〃 2023-07-13 13:54 12阅读 0赞

排序算法类的模板

public static void sort(Comparable[] a) {
    
        }
    
        private static boolean less(Comparable v, Comparable w) {
            return v.compareTo(w) < 0;
        }
    
        private static void exch(Comparable[] a, int i, int j) {
            Comparable t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    
        private static void show(Comparable[] a) { // 在单行中打印数组
            for (int i = 0; i < a.length; i++) StdOut.print(a[i] + " ");
            StdOut.println();
        }
    
        public static boolean isSorted(Comparable[] a) {
            // 测试数组元素是否有序
            for (int i = 1; i < a.length; i++) if (less(a[i], a[i - 1])) return false;
            return true;
        }
    
        public static void main(String[] args) { // 从标准输入读取字符串，将它们排序并输出
            String[] a = In.readStrings();
            sort(a);
            assert isSorted(a);
            show(a);
        }

### 一、选择排序 ###

> 首先，找到数组中**最小的那个元素**，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序，这个方法叫做选择排序。它在不断选择剩余元素中最小者。

public class Selection {
        public static void sort(Comparable[] a) {
            // 将a[]按升序排列
            int N = a.length;
            // 数组长度
            for (int i = 0; i < N; i++) {
                // 将a[i]和a[i+1..N]中最小的元素交换
                int min = i; // 最小元素的索引
                for (int j = i+1; j < N; j++) {
                    if (less(a[j], a[min])) {
                        min = j;
                    }
                }
                exch(a, i, min);
            }
        }
            // less()、exch()、isSorted()和main()方法见“排序算法类模板”
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70][]

### 二、插入排序 ###

> 将其余所有元素在插入之前**都向右移动一位**，这种算法叫做插入排序

在索引i 由左 向 右变化的过程中，左侧的元素总是有序的，所以当 i 到达数组的右端时排序就完成了

public class Insertion { 
        public static void sort(Comparable[] a) { 
            // 将a[]按升序排列 
            int N = a.length; for (int i = 1; i < N; i++) { 
                // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中 
                for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
                exch(a, j, j-1); 
            } 
        }
        // less()、exch()、isSorted()和main()方法见“排序算法类模板” 
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1][]

***插入排序、选择排序***

> 选择排序***不会访问索引左侧***的元素
> 
> 插入排序***不会访问索引右侧***的元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2][]

### 三、希尔排序 ###

***希尔排序为了加快速度简单地改进了插入排序*** ，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

> 希尔排序的思想是使 **数组中任意间隔为 h 的元素都是有序** 的。这样的数组被称为  h  有序数组。换句话说，一个  h  有序数组
> 
> 就是  h  个互相独立的有序数组编织在一起组成的一个数组（见图  2.1.2）。 在进行排序时，如果  h  很大，我们就能将元素移动到很远的地方，为实现更小的  h  有序创造方便。用这种方式，对于任意以  1  结尾的  h  序列，我们都能够将数组排序。这就是希尔排序
> 
>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3][]

> 实现希尔排序的一种方法是对于每个  h ，用插入排序将  h 个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在  h- 子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要在插入排序的代码中将移动元素的距离由  1  改为  h 即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程
> 
>

希尔排序更高效的原因是它权衡了 ***子数组的规模*** 和 ***有序性*** 。

public class Shell {
        public static void sort(Comparable[] a) {
            // 将a[]按升序排列 
            int N = a.length;
            int h = 1;
            while (h < N / 3) h = 3 * h + 1;
            // 1, 4, 13, 40, 121, 364, 1093, ...
            while (h >= 1) {
                // 将数组变为h有序 
                for (int i = h; i < N; i++) {
                    // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 
                    for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) exch(a, j, j - h);
                }
                h = h / 3;
            }
        }// less()、exch()、isSorted()和main()方法见“排序算法类模板” 
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4][]

目前算法基础不好，先囫囵吞枣吧，慢慢在消化。。。。有好的学习方法一起分享吧

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70]: /images/20230529/bb282698ed3942058311a60fdf0e09c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1]: /images/20230529/ee99151c1ea14678b64713622e5ffca6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2]: /images/20230529/84d690dcf4804115b6cbd942b87ce569.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3]: /images/20230529/dd69b3e266b74cd1b232aba824c75fc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4]: /images/20230529/1217c91e3bc740329b2a1c9b5020dbcd.png