java 基础排序（冒泡、插入、选择、快速）算法回顾

java 基础排序（冒泡、插入、选择、快速）算法回顾

• 冒泡排序

private static void bubbleSort(int[] array) {

        int temp;

        for (int i = 0; i < array.length; i++) {

            for (int j = 0; j < array.length - i - 1; j++) {

                if (array[j] > array[j + 1]) {

                    temp = array[j];

                    array[j] = array[j + 1];

                    array[j + 1] = temp;

                }

            }

        }

        print(array);

    }

• 插入排序

private static void insertSort(int[] array) {

        int j;

        //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的

        for (int i = 1; i < array.length; i++) {

            int tmp = array[i];//记录要插入的数据

            j = i;

            //从已经排序的序列最右边的开始比较，找到比其小的数

            while (j > 0 && tmp < array[j - 1]) {

                //向后挪动

                array[j] = array[j - 1];

                j--;

            }

            //存在比其小的数，插入

            array[j] = tmp;

        }

        print(array);

    }

• 选择排序

private static void choiseSort(int[] array) {

        //记录目前能找到的最小值元素的下标

        int min;

        //经过N-1轮比较

        for (int i = 0; i < array.length - 1; i++) {

            min = i;

            //每轮需要比较的次数

            for (int j = i + 1; j < array.length; j++) {

                if (array[j] < array[min]) {

                    min = j;

                }

            }

            //将找到的最小值和i位置所在的值进行交换

            if (i != min) {

                int temp = array[i];

                array[i] = array[min];

                array[min] = temp;

            }

        }

        print(array);

    }

• 快速排序

快速排序算法思想

 /**

     * 快速排序

     *

     * @param array

     * @param left

     * @param right

     */

    private static void quickSort(int[] array, int left, int right) {

        if (left >= right) return;

        int pivot = partition(array, left, right);

        quickSort(array, left, pivot - 1);

        quickSort(array, pivot + 1, right);

    }

    /**

     * 数组划分

     *

     * @param array

     * @param left

     * @param right

     * @return

     */

    private static int partition(int[] array, int left, int right) {

        int pivotKey = array[left];

        while (left < right) {

            while (left < right && array[right] >= pivotKey) {

                right--;

            }

            array[left] = array[right];

            while (left < right && array[left] <= pivotKey) {

                left++;

            }

            array[right] = array[left];

        }

        array[left] = pivotKey;

        return left;

    }

• 测试

private static void print(int[] array) {

        for (int i = 0; i < array.length; i++) {

            System.out.printf(array[i] + " ");

        }

    } 

 public static void main(String[] args) {

        int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};

        System.out.println("原始数据：");

        print(array);

        System.out.println("\r\n");

        System.out.println("冒泡排序：");

        bubbleSort(array);

        System.out.println("\r\n");

        System.out.println("选择排序：");

        choiseSort(array);

        System.out.println("\r\n");

        System.out.println("插入排序：");

        insertSort(array);

         int array[] = {65, 58, 95, 10, 57, 62, 13, 106, 78, 23, 85};

        System.out.println("快速排序前：" + Arrays.toString(array));

        quickSort(array, 0, array.length - 1);

        System.out.println("快速排序后：" + Arrays.toString(array));

    }