第2章 排序

TOC

排序算法

需要关注问题

排序是将一组数据按照某种逻辑重新排列的过程。相对比较常用，在考虑排序算法时，我们往往要考虑以下几个方面：

1. 排序算法的时间复杂度
2. 排序算法的空间复杂度
3. 排序算法的稳定性（即：在需要进行排序操作的数据中，如果存在值相等的元素，在排序前后，相等元素之间的排列顺序不发生改变。）

排序算法的框架

注意点：

1. 需要对外公开的方法设置成public的，无需对外公开的方法设置成private。 如果作为api发布后，修改其中的private方法重新发布，远比修改public方法带来的影响要小的多，因为你几乎可以断定此方法除了本类，其它没有地方在用。当然如果第三方通过反复调用的方式除外，当然通过反射调用方法的人除外（当然这种人可以忽略了，当使用private相当于你已经发布了此方法后期修改的免责声明）
2. public 方法可以只调用私有方法，采用这种隐藏实现的方式，方便后期算法优化。
3. java适合对大的模型进行拆分，coding时只需关注当前一小模块的功能完整性（就如同下面的排序框架搭建好后，只需要关注sort方法的逻辑）
4. 可排序的对象一定时可比较的对象，不可比较，没有一个统一的比较标准是无法排序的

代码语言：java复制

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class SortExample {
    public static void sort(Comparable[] a) {

    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i  ) {
            System.out.print(a[i]   " ");
        }
        System.out.println();
    }

    /**
     * 测试元素是否有序
     *
     * @param a
     */
    public static boolean isSorted(Comparable[] a) {
        if (a == null || a.length == 1) {
            return true;
        }

        for (int i = 1; i < a.length; i  ) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断两个对象的大小
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    /**
     * 交换数组中的两个对象
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    public static void main(String[] args) {
        //此时为需要用线程安全的随机数生成器
        int N = ThreadLocalRandom.current().nextInt(10, 10000);
        Integer a[] = new Integer[N];
        for (int i = 0; i < N; i  ) {
            a[i] = Integer.valueOf(ThreadLocalRandom.current().nextInt(1000000));
        }

        System.out.println("Array size: " N ", Array isSorted: " isSorted(a));
        Arrays.sort(a);
        System.out.println("Array size: " N ", Array isSorted: " isSorted(a));
    }
}

初等排序算法

选择排序

[startPos,curPos,endPos)

[startPos,curPos) 是已排好序的列表,[curPos,endPos)是待排序的列表，依次从待排序的列表中选择最小的放到已排好序的列表中。

代码语言：java复制

    private static void selection(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i  ) {
            int minIdx = i;
            for (int j = i; j < N; j  ) {
                if (less(a[j], a[minIdx])) {
                    minIdx = j;
                }
            }
            exch(a, i, minIdx);
        }
    }

插入排序

[startPos,curPos,endPos)

[startPos,curPos) 是已排好序的列表,[curPos,endPos)是待排序的列表，依次从待排序的列表中取出的元素x的插入已排好序的列表seq中。

在seq从后往前在比较，判断是否在当前位置插入的时候，要同时兼顾移动元素。因为当前取出的元素x一定要插入到有序表seq中的，如果当前位置不比x小，那当前位置的元素往后移动一位，x则继续与再前的元素比较。

类比每学期的第一次体育课排除时，先跟前面靠近你的比，如果前面靠近你的比你高，那你们交换一上位置，然后你再跟前面的比

代码语言：java复制

    /**
     * 插入排序
     * @param a
     */
    private static void insertion(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i  ) {
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

冒泡排序

[startPos,curPos,endPos)

[startPos,curPos) 是待排序的列表,[curPos,endPos)是已排好序的列表，依次从待排序的列表中取出的元素x的放到已排好序的列表seq首部。

类比班主任抽考去乡里参加比赛，每次从剩余的中挑出一个最好的

代码语言：java复制

    /**
     * 冒泡排序
     */
    private static void bubbleSort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N - 1; i  ) {
            for (int j = 0; j < N - 1 - i; j  ) {
                if (less(a[j   1], a[j])) {
                    exch(a, j, j   1);
                }
            }
        }
    }

希尔排序

插入排序的改进，虽然说是改进，但相比插入排序有优有劣：

• 优点： 对于大规模乱序数组的排序时比插入排序快
• 缺点： 不再是稳定排序

分组： 将i,i h,i 2_h,i 3h...,i k_h 分成一组，组内使用插入排序，当递减到1的时候，就是插入排序

算法性能取决于h,还取决于h之间的数学性质，比如它们的公因子等。 下列算法使用了递增（减）序列 1/2({3}^{k}-1) ,从N/3开始减至1。关于递增（减）序列(这里翻译有点问题，可以看英文原版)，目前无法证明哪个递增（减）序列是最好的 Property. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is bounded by a small multiple of N times the number of increments used. Proposition. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is O(N3/2). algorithm4th

代码语言：java复制

    private static void shell(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h   1;
        }

        while (h >= 1) {
            for (int i = h; i < N; i  ) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

高等排序算法

归并排序以及优化

归并排序

• 类似于没有孙膑谋划之前田忌与齐王赛马，二人各自将自己的马分上中下三等（先组内排序），再上 等对上等，中等对中等，下等对下等。
• 和运动会的比赛一下，先分小组进行小组赛，各小组的胜出者再比

分自下向上的归并排序和自上向上的归并排序，二者时间和空间复杂度一样，只是自下向上的归并排序同时适用于数组和链表这两种方式存储线性表，面自上向下的归并排序只适用于数组这种方式存储的线性表。

同时归并排序有一种优化，当组内元素个数小于7时（这个是经验值），使用插入排序对组内元素进行排序。

• 当组内元素个数小于7时，能不能使用其它普通排序算法进行，比如说选择排序，或者冒泡排序？ 这里只能用插入排序和冒泡排序，而不能用选择排序，因为选择排序是不稳定的，如果使用选择排序，带来的后果是归并排序将不再是稳定排序。
• 为什么当组内元素个数小于7时（这个是经验值），使用插入排序对组内元素进行排序，性能会有提升（约10%~15%的优化）？ 递归调用的运行时间，大于了插入排序的的运行时间

归并排序算法框架

代码语言：java复制

import java.util.concurrent.ThreadLocalRandom;

public class Merge {
    private Merge() {
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    /**
     * 自顶向下
     * @param a
     * @param aux
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo   (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid   1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo   1);

        int i = lo, j = mid   1;
        for (int k = lo; k <= hi; k  ) {
            if (i > mid) {
                a[k] = aux[j  ];
            } else if (j > hi) {
                a[k] = aux[i  ];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j  ];
            } else {
                a[k] = aux[i  ];
            }
        }
    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i  ) {
            System.out.print(a[i]   " ");
        }
        System.out.println();
    }

    /**
     * 测试元素是否有序
     *
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    public static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo   1; i <= hi; i  ) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断两个对象的大小
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    /**
     * 交换数组中的两个对象
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    public static void main(String[] args) {
        //此时为需要用线程安全的随机数生成器
        int N = 100;
        Integer a[] = new Integer[N];
        for (int i = 0; i < N; i  ) {
            a[i] = Integer.valueOf(ThreadLocalRandom.current().nextInt(1000));
        }
        System.out.println("Array size: "   N   ", Array isSorted: "   isSorted(a, 0, a.length - 1));
        sort(a);
        System.out.println("Array size: "   N   ", Array isSorted: "   isSorted(a, 0, a.length - 1));
    }
}

自上向下的归并排序

代码语言：java复制

public class Merge {
    //...
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    /**
     * 自顶向下
     * @param a
     * @param aux
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo   (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid   1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo   1);

        int i = lo, j = mid   1;
        for (int k = lo; k <= hi; k  ) {
            if (i > mid) {
                a[k] = aux[j  ];
            } else if (j > hi) {
                a[k] = aux[i  ];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j  ];
            } else {
                a[k] = aux[i  ];
            }
        }
    }
    //...
}

自下向上的归并排序

代码语言：java复制

public class MergeBU {
    //...

    /**
     * 自下向上
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int step = 1; step < n; step  =step) {
            for (int lo = 0; lo < n - step; lo  = step   step) {
                int mid = lo   step - 1;
                int hi = Math.min(lo   step   step - 1, n - 1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo   1);
        int i = lo, j = mid   1;
        for (int k = lo; k <= hi; k  ) {
            if (i > mid) {
                a[k] = aux[j  ];
            } else if (j > hi) {
                a[k] = aux[i  ];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j  ];
            } else {
                a[k] = aux[i  ];
            }
        }
    }
    //...
}

优化归并排序

当分组内的元素个数小于7时，使用插入排序或者冒泡排序进行优化

代码语言：java复制

public class Merge {
    private static final int CUTOFF = 7;
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    /**
     * 自顶向下
     * @param a
     * @param aux
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo   CUTOFF) {
            insertionSort(a, lo, hi);
            return;
        }

        int mid = lo   (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid   1, hi);

        if (!less(a[mid   1], a[mid])) {
            System.arraycopy(a, lo, aux, lo, hi - lo   1);
        } else {
            merge(a, aux, lo, mid, hi);
        }
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo   1);

        int i = lo, j = mid   1;
        for (int k = lo; k <= hi; k  ) {
            if (i > mid) {
                a[k] = aux[j  ];
            } else if (j > hi) {
                a[k] = aux[i  ];
            } else if (less(aux[j], aux[i])) {
                a[k] = aux[j  ];
            } else {
                a[k] = aux[i  ];
            }
        }
    }

    /**
     * 插入排序
     * @param a
     */
    private static void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i  ) {
            for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }
    //...
}

未完待续...

java 编程算法

0 人点赞