【排序】选择排序与堆排序

一、选择排序（Selection Sort）

　　选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1.算法步骤

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

2.动图演示

3.代码实现

public static void selectionSort(int[] arr){
    // 总共要经过 length-1 轮比较
    for (int i=0; i<arr.length-1; i++) {
        int min = i;
        // 每轮需要比较的次数 N-(i+1)
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }
        // 将找到的最小值和i位置所在的值进行交换
        if (i != min) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

4.时间复杂度

　　表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

性能分析

　　交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是 N。所以算法的时间效率取决于比较的次数。

　　查看代码可以精准得到，0 到 N-1 的任意 index都会进行一次交换和 N-1-index 次比较，所以对于长度为 N 的数组，选择排序需要大约 N²/2 次比较和 N 次交换。

选择排序的特点

　　①运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息；
　　②数据移动是最小的。每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。（其他大部分排序算法的增长数量级都是线性对数或是平方级别的）

5.优化

　　试想，上述方案中的主要思路是，每次遍历剩余元素，找出其中最小值，只排定最小值。（原有方案）

　　我们这样，每次遍历剩余元素的时候，找出其中最小值和最大值，并排定最小值和最大值。（优化方案）

　　这样遍历的次数会减少一半。时间复杂度是O（N/2 * N /2），还是平方级别的。但是运行时间有了相应的减少。

优化方案之后的运行轨迹

优化代码

public static void selectionSortPlus(int[] arr) {
    for (int left = 0, right = arr.length - 1; left < right; left++, right--) {
        int min = left;        // 记录最小值
        int max = right;     // 记录最大值
        for (int index = left; index <= right; index++) {
            if (arr[index]<arr[min]) {
                min = index;
            }
            if (arr[max]<arr[index]) {
                max = index;
            }
        }
        // 将最小值交换到 left 的位置
        swap(arr, left, min);
        //此处是先排最小值的位置，所以得考虑最大值（arr[max]）在最小位置（left）的情况。
        if (left == max) {
            max = min;
        }
        swap(arr, right, max);
    }
}	
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

二、堆排序（Heap Sort）

　　堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1.算法步骤

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

2.算法演示

3.代码实现

public static void heapSort(int[] arr){
    int len = arr.length;
    buildMaxHeap(arr, len);
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0, len);
    }
}
private static void buildMaxHeap(int[] arr, int len) {
    for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
        heapify(arr, i, len);
    }
}
private static void heapify(int[] arr, int i, int len) {
    int left = 2*i + 1;
    int right = 2*i + 2;
    int largest = i;
    //大顶堆：Key[i]>=Key[2i+1]&&key[i]>=key[2i+2]
    if (left<len && arr[left]>arr[largest]) {
        largest = left;
    }
    if (right<len && arr[right]>arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}