排序算法

title: 排序算法
date: 2019-03-19 20:07:46
categories: 代码
tags: 算法学习

排序算法

前言

待排序的元素需要实现Java的Comparable接口，该接口有compareTo()方法，可以用它来判断两个元素的大小关系。
在此使用less()和swap()来进行比较和交换的操作，使得代码的可读性和可移植性更好（具体原因参考《算法》第四版）

public abstract class Sort<T extends Comparable<T>> {
    public abstract void sort(T[] nums);
    protected boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }
    protected void swap(T[] a, int i, int j) {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

a) 原理: 每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序

b) 简单选择排序的基本思想：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2] ~ arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。

{% asset_img 选择排序.gif 选择排序过程 %}

public class Selection<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 0; i < N - 1; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++) {
                if (less(nums[j], nums[min])) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }
}

冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

{% asset_img 冒泡排序.gif 冒泡排序过程 %}

public class Bubble<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        boolean hasSorted = false;
        for (int i = N - 1; i > 0 && !hasSorted; i--) {
            hasSorted = true;
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) {
                    hasSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }
}

插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。

平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。
*以下演示了在一轮循环中，将元素 2 插入到左侧已经排序的数组中。

{% asset_img 插入排序.gif 插入排序过程 %}

public class Insertion<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
                swap(nums, j, j - 1);
            }
        }
    }
}

希尔排序

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。

希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

{% asset_img 希尔排序.png 希尔排序过程 %}

public class Shell<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

{% asset_img 归并排序.png 归并排序过程 %}

1.归并方法

归并方法将数组中两个已经排序的部分归并成一个。

public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {
    protected T[] aux;
    protected void merge(T[] nums, int l, int m, int h) {
        int i = l, j = m + 1;
        for (int k = l; k <= h; k++) {
            aux[k] = nums[k]; // 将数据复制到辅助数组
        }
        for (int k = l; k <= h; k++) {
            if (i > m) {
                nums[k] = aux[j++];
            } else if (j > h) {
                nums[k] = aux[i++];
            } else if (aux[i].compareTo(aux[j]) <= 0) {
                nums[k] = aux[i++]; // 先进行这一步，保证稳定性
            } else {
                nums[k] = aux[j++];
            }
        }
    }
}

2.自顶向下归并排序

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {
    @Override
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums, 0, nums.length - 1);
    }
    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int mid = l + (h - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, h);
        merge(nums, l, mid, h);
    }
}

3.自底向上归并排序

先归并那些微型数组，然后成对归并得到的微型数组

public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {
    @Override
    public void sort(T[] nums) {
        int N = nums.length;
        aux = (T[]) new Comparable[N];
        for (int sz = 1; sz < N; sz += sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}

快速排序

待补

堆排序

堆

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树

堆可以用数组来表示，这是因为堆是完全二叉树，而且完全二叉树很容易就存储在数组中。位置k的节点的父节点位置为k/2,而它的两个子节点的位置分别为2k和2k+1。这里不使用数组索引为0的位置，是为了更清晰地描述节点的位置关系。

{% asset_img 堆排序.png %}

public class Heap<T extends Comparable<T>> {
    private T[] heap;
    private int N = 0;
    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }
    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
}

上浮和下沉

在堆中，当一个节点比父节点大，那么需要交换这两个节点。交换后还可能比它的新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称作上浮。

{% asset_img 上浮.gif %}

private void swim(int k){
    while(k > 1 && less(k / 2, k)){
        swap(k /2, k);
        k = k / 2;
    }
}

类似的，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，这种操作叫作下沉。一个节点如果有两个子节点，应当与两个子节点中最大的那个节点进行交换。

{% asset_img 下沉.gif %}

private void sink(int k){
    while(2 * k <= N){
        int j = 2 * k; //
        if(j < N && less(j, j + 1))
            j++;
        if(!less(k, j))
            break;
        swap(k, j);
        k = j;
    }
}

插入元素

将新元素放到数组末尾，然后上浮到适合的位置

public void insert(Comparable v){
    heap[++N] = v;
    swim(N);
}

删除最大元素

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到适合的位置。

public T delMax() {
    T max = heap[1];
    swap(1,N--);
    heap[N--] = null;
    sink(1);
    return max;
}

堆排序

把最大元素和当前堆中数组的最后一个元素交换位置，并且不能删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

构建堆

无序数组建立堆最直接的方法就是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。

{% asset_img 堆排序.gif %}

交换堆顶元素与最后一个元素

交换之后需要进行下沉操作维持堆的有序状态。

{% asset_img 交换.gif %}

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /**
     * 数组第 0 个位置不能有元素
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);
        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }
    private void sink(T[] nums, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1))
                j++;
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }
    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }
}

分析

一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

小结

待补

编程学习

排序算法详解