数据结构-8.Java. 七大排序算法(上篇)

/**
     * 选择排序
     *
     * 时间复杂度:
     *      最好: O(N^2)
     *      最坏: O(N^2)
     *空间复杂度:O(N)
     *
     * 稳定性: 不稳定
     *
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

选择排序有 第二种写法,  反正都要遍历一遍数组, 不如把最大值和最小值都找出来, 最小的往最前放, 最大的往最后放. 

第二种写法步骤:

 1.  定义 left = 0, right = array.length-1, i = left + 1; minIndex = maxIndex = 0;

2.   while( left < right )循环,  i 在循环中, 遍历数组 找到最小元素下标 和 最大元素下标, 出循环 与 minIndex 和 maxIndex 交换.  

3. 出循环后 考虑一个特殊情况 , 当 left = 0 下标 对应的值就是最大值时, 第二步出循环后的交换操作 将最大值交换到minIndex下标处了. 需要 再将 maxIndex 标记到最大值.

第二种写法代码实现:

public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //选择排序的第二种写法.
    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; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            //有一种情况是maxIndex原本就在left位置上,上面的交换将最大值交换到minIndex下标处了.导致后续的排序不正确.
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

第四步 直接选择排序的特性总结:

2.2.3 堆排序

 /**
     *堆排序
     *
     * 时间复杂度:O(N)+O(N*logN) 约等于 O(N*logN)
     *
     * 如果都以最坏的情况来看,堆排序是目前来说最快的,希尔排序其次.
     * 假设希尔排序为O(N^1.3) 当N越大时,logN趋于不变所以,堆排序O(N*logN)要快一些.
     *
     *  空间复杂度:O(1)
     *  稳定性:不稳定
     */
    public static void heapSort(int[] array) {
        //建大堆
        createBigHeap(array);//O(N)
        int end = array.length-1;
        //O(N*logN)
        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 end) {
        int child = (parent*2)+1;
        while(child < end) {
            //保证右子树存在并且当右子树大的时候,child++来到右子树的下标.
            if(child+1 < end && array[child+1] > array[child]) {
                child++;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else {
                //本身就是大根堆
                break;
            }
        }
    }