排序第二节——选择排序（选择排序+堆排序）（两个视频讲解）

2.2 选择排序

2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.2.2 直接选择排序 O(N^2) （不稳定）

***（视频讲解 直接选择排序+优化 14分钟）

1. 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

【直接选择排序的特性总结】

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

模板（选择排序，一个循环找一个）

    /** * 直接选择排序 * 时间复杂度：O(n^2) -> 对数据不敏感 不管你是有序的还是无序的 时间复杂度都是这样的 * 空间复杂度：O(1) * 稳定性：不稳定的排序 * @param array */
    public static void selectSort(int[] array) {
    
        for (int i = 0; i < array.length; i++) {
    
            //每次将i下标的 值 当做是 最小值
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
    
                if(array[j] < array[minIndex]) {
    
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    /** * 交换函数 * @param array * @param i * @param j */
    private static void swap(int[] array,int i,int j) {
    
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

*优化：一次找两个极值

    /** * O(N^2) * @param array */
    public static void selectSort2(int[] array) {
    
        int left = 0;
        int right = array.length-1;
        while (left < right) {
    
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right ; i++) {
    
                if(array[i] < array[minIndex]) {
    
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
    
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //修正 max的下标
            if(left == maxIndex) {
    
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

2.2.3 堆排序**O(NlogN) （不稳定）

视频讲解

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
【直接选择排序的特性总结】

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

模板

思想：

1. 建立一个大根堆（堆顶一定是 最大的元素）
2. 堆顶和堆低互换，然后再重新根据 堆顶建堆（循环）

    /** * 时间复杂度：O(n*logn) * N^0.5 logn * 空间复杂度：O(1) * 稳定性：不稳定的 * @param array */
    public static void heapSort(int[] array) {
    
        createBigHeap(array);
        int end = array.length-1;
        while (end >= 0) {
    
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array) {
    

        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
    
            shiftDown(array,parent,array.length);
        }
    }

    private static void shiftDown(int[] array,int parent,int len) {
    
        int child = 2*parent+1;
        //最起码保证有左孩子
        while (child < len) {
    
            if(child+1 < len && array[child] < array[child+1]) {
    
                child++;
            }
            if(array[child] > array[parent]) {
    
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
    
                break;
            }
        }
    }