排序算法

一、初级排序算法

1、选择排序

思路：找到数组中最小的元素，其次，将它和数组的第一个元素交换位置，再找第二小，如此往复。

有两个鲜明的特点： 运行时间和输入无关和 数据移动是最少的。

直接上代码：

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);
        }
    }
    
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

2、插入排序

插入排序对于实际应用中常见的某些类型的非随机数组非常有效。依次找到最大的元素并移动到最末尾，然后再找第二大……

直接上代码

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);
    }

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

3、希尔排序

二、归并排序

1、自顶向下的归并排序

2、自底向上的归并排序

3、排序算法的复杂度

三、快速排序

1、基本的算法

2、性能特点

3、算法改进

四、优先队列

有时候，我们不需要将所有的元素排序，例如手机要运行优先级高的程序，每次取优先级最高的程序出来运行就可以了，而不必将所有程序按照优先级排序。

这种情况下，需要一个合适的数据结构： 删除最大元素和 插入元素，这种数据结构叫做 优先队列。

1、堆的定义

数据结构二叉堆能够很好的实现优先队列的基本操作。在二叉堆数组中，每个元素要保证大于等于另外的两个特定位置的元素，相应的，这两个特定位置的元素又要保证大于各自位置特定两个位置的元素，如此套娃。

当一棵二叉树的每个结点都大于等于它的两个特定节点时，它被称为堆有序

Hello Programmer