java排序算法

概述

1. 交换类排序
   • 冒泡排序     时间复杂度 O(n2)
   • 快速排序     时间复杂度 O(N*logN)
2. 插入类排序
   • 直接插入排序     时间复杂度 O(n2)
   • 希尔排序     时间复杂度 O(N*logN)
3. 选择类排序
   • 直接选择排序     时间复杂度 O(n2)
   • 堆排序     时间复杂度 O(N*logN)
4. 归并排序
   • 归并排序     时间复杂度 O(N*logN)

一、交换类排序

1. 冒泡排序

    /**
     * 冒泡排序
     * 时间复杂度 O(n2)
     */
    public void bubbleSort(int[] nums) {

        int len = nums.length;
        boolean flag;  // 是否交换标志

        for (int i = 0; i < len - 1; i++) {
            flag = false;
            for (int j = 0; j < len - 1 - i; j++) {
                if (nums[j] > nums[j+1]) {
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    flag = true;
                }
            }
            // 如果为false，说明后面的元素已经有序
            if (!flag) {
                break;
            }
        }

    }

2. 快速排序

    /**
     * 快速排序
     * 时间复杂度 O(N*logN)
     */
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int i = left, j = right;
        int key = nums[i];  // 第一个作为key

        while (i < j) {
            // 从右向左走第一个小于key的值
            while (i < j && nums[j] >= key) {
                j--;
            }

            if (i < j) {
                nums[i] = nums[j];
                i++;
            }

            // 从左向右找第一个大于key的值
            while (i < j && nums[i] < key) {
                i++;
            }

            if (i < j) {
                nums[j] = nums[i];
                j--;
            }

        }
        nums[i] = key;
        quickSort(nums, left, i -1);
        quickSort(nums, i+1, right);
    }

二、插入类排序

1. 直接插入排序

基本有序或者规模较小时高效

    /**
     * 直接插入排序
     * 时间复杂度 O(n2)
     */
    public void insertSort(int[] nums) {

        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > temp) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = temp;
        }

    }

2. 希尔排序

    /**
     * 希尔排序
     * 时间复杂度 O(N*logN)
     */
    public void shellSort(int[] nums) {
        int len = nums.length;

        // gap为步长，每次减为原来的一半
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 共gap个组，对每组都执行直接插入排序
            for (int k = 0; k < gap; k++) {
                for (int i = k + gap; i < len; i+=gap) {
                    int temp = nums[i];
                    int j = i - gap;
                    while (j >= 0 && nums[j] > temp) {
                        nums[j + gap] = nums[j];
                        j -= gap;
                    }
                    nums[j + gap] = temp;
                }
            }
        }
    }

三、选择类排序

1. 直接选择排序

    /**
     * 直接选择排序
     * 时间复杂度 O(n2)
     */
    public void selectSort(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len - 1; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (nums[min] > nums[j]) {
                    min = j;  // 保存位置
                }
            }
            if (min != i) {
                int temp = nums[i];
                nums[i] = nums[min];
                nums[min] = temp;
            }
        }
    }

2. 堆排序

四、归并排序

1. 归并排序