排序算法

冒泡排序

public class Test {

    public static void main(String[] args) {
       int[] array = new int[]{-1, -3, 0, -5, 10, 8, 9, 5, -10, 3};
       bubbleSort(array);
       for (int i : array) {
           System.out.println(i);
       }
    }

    private static void bubbleSort(int[] array) {
        int temp = 0;
        boolean flag = false;

        for(int i = 0; i < array.length - 1; i++) {
            for(int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) { // 这里是升序排序，如果需要降序，改为小于号即可
                    flag = true;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }
    }
}

选择排序

基本思想是：第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换；第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换；第i次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]交换

public class Test {

    public static void main(String[] args) {
       int[] array = new int[]{-1, -3, 0, -5, 10, 8, 8, 9, 5, 5, -10, 3};
       selectSort(array);
       for (int i : array) {
           System.out.println(i);
       }
    }

    /**
     * 升序排序
     */
//    private static void selectSort(int[] array) {
//        for(int i = 0; i < array.length - 1; i++) {  //进行array.length - 1轮比较
//            int min = array[i];  // 最小值
//            int minIndex = i;  // 最小值的位置
//            for(int j = i + 1; j < array.length; j++) {
//                if(array[j] < min) {
//                    min = array[j];
//                    minIndex = j;
//                }
//            }
//
//            array[minIndex] = array[i];
//            array[i] = min;
//        }
//    }

    /**
     *降序
     */
    private static void selectSort(int[] array) {
        for(int i = 0; i < array.length - 1; i++) {  //进行array.length - 1轮比较
            int max = array[i];  // 最大值
            int maxIndex = i;  // 最大值的位置
            for(int j = i + 1; j < array.length; j++) {
                if(array[j] > max) {
                    max = array[j];
                    maxIndex = j;
                }
            }

            array[maxIndex] = array[i];
            array[i] = max;
        }
    }
}

插入排序

public class Test {

    public static void main(String[] args) {
       int[] array = new int[]{-1, -3, 0, -5, 10, 8, 8, 9, 5, 5, -10, 3};
       insertSort(array);
       for (int i : array) {
           System.out.println(i);
       }
    }

    /**
     * 升序排序
     */
//    private static void insertSort(int[] array) {
//        for(int i = 1; i < array.length; i++) {  //进行array.length - 1轮比较
//            int insertVal = array[i];
//            int insertIndex = i - 1;
//
//            while(insertIndex >= 0 && insertVal < array[insertIndex]) {
//                array[insertIndex + 1] = array[insertIndex];
//                insertIndex--;
//            }
//
//            if (insertIndex + 1 != i) {
//                array[insertIndex + 1] = insertVal;
//            }
//        }
//    }

    /**
     * 降序排序
     */
    private static void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {  //进行array.length - 1轮比较
            int insertVal = array[i];
            int insertIndex = i - 1;

            while(insertIndex >= 0 && insertVal > array[insertIndex]) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 != i) {
                array[insertIndex + 1] = insertVal;
            }
        }
    }
}

堆排序

升序用大顶堆，降序用小顶堆。

public class Test {

    public static void main(String[] args) {
       int[] array = new int[]{-1, -3, 0, -5, 10, 8, 8, 9, 5, 5, -10, 3};
       heapSort(array);
       for (int i : array) {
           System.out.println(i);
       }
    }


    private static void heapSort(int[] array) {
        int temp = 0;

        // 建堆
        for (int i = array.length/2 - 1; i >= 0; i--) {  // i = array.length/2 - 1对应的是第一个非叶子节点
            adjustSmallHeap(array, i, array.length);
        }

        for (int j = array.length - 1; j > 0; j--) {
            // 交换堆顶元素与末尾元素
            temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            // 调整堆
            adjustSmallHeap(array, 0, j); // 从索引为0处开始调整，是因为下面的已经在建堆时调整好了。
        }
    }

    /**
     * 调整为大顶堆
     * @param array
     * @param i 非叶子节点的索引
     * @param length 对多少元素进行处理
     */
    private static void adjustBigHeap(int[] array, int i, int length) {

        int temp = array[i];

        // 这个for循环在找以传入的i为父节点的树的最大值，并把最大值放到传入的i的位置。
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 找左右子节点的最大值
            if (k + 1 < length && array[k] < array[k + 1]) {
                k++;
            }

            // 左右子节点大于根节点，则调整；否则，不调整
            if (array[k] > temp) {
                array[i] = array[k];
                i = k; // i不停地指向最大值的位置
            } else {
                break;
            }
        }

        // for循环结束，已经将以传入的i为父节点的树的最大值，放在了最顶（局部）
        // 此时i指向的是，以传入的i为父节点的树的最大值所在的位置
        array[i] = temp;
    }

    /**
     * 调整为小顶堆
     * @param array
     * @param i 非叶子节点的索引
     * @param length 对多少元素进行处理
     */
    private static void adjustSmallHeap(int[] array, int i, int length) {

        int temp = array[i];

        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 找左右子节点的最小值
            if (k + 1 < length && array[k] > array[k + 1]) {
                k++;
            }

            // 左右子节点小于根节点，则调整；否则，不调整
            if (array[k] < temp) {
                array[i] = array[k];
                i = k;
            } else {
                break;
            }
        }

        // for循环结束，已经将以i为父节点的树的最小值，放在了最顶（局部）
        array[i] = temp;
    }

}