常见排序算法总结

算法入门学习

排序算法

选择排序

package xyz.base01;

import java.util.Arrays;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 9:38
 * @desc: 选择排序 时间复杂度为 O(n ^ 2)
 */
public class Code01_SelectionSort {

    public static int[] selectSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
        // 0 ~ n-1
        // 1 ~ n-1
        // ...

        return arr;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int testTimes = 1000000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long start = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            selectSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("一共执行了 ：" + (end - start) / 1000 + "秒钟");
        System.out.println(succeed ? "YES!!!" : "Occured a mistake");

//        int[] arr = generateRandomArray(maxSize,maxValue);
//        printArray(arr);
//        selectSort(arr);
//        printArray(arr);
    }

    private static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
        }
        return arr;
    }
}

冒泡排序

package xyz.base01;

import java.util.Arrays;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 9:39
 * @desc: 冒泡排序 时间复杂度为O(n ^ 2)
 */
public class Code02_BubbleSort {
    public static void bubblerSort(int[] arr) {
        //处理边界
        if (arr == null || arr.length < 2) {
            return;
        }
        /**
         * 0 ~ N - 1 依次比较,最大放在最后面
         * 0 ~ N - 2
         * ...
         * 0 ~ 2 比较谁大,谁大就放在后面
         * 0 ~ 1 比较谁大,谁大就放在后面
         */
/*        for (int i = 0;i < arr.length;i++){
//            int max = arr[i];
            for (int j = 1;j < arr.length - i;j++){
                if (arr[j-1] > arr[j]){
                    swap(arr,j - 1,j );
                }
            }
        }*/

        //optimize function
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }


    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int testTimes = 1000000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long start = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            bubblerSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("一共执行了 ：" + (end - start) / 1000 + "秒钟");
        System.out.println(succeed ? "YES!!!" : "Occured a mistake");

//        int[] arr = generateRandomArray(maxSize,maxValue);
//        printArray(arr);
//        selectSort(arr);
//        printArray(arr);
    }

    private static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
        }
        return arr;
    }
}

插入排序

package xyz.base01;

import java.util.Arrays;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-11 9:40
 * @desc: 插入排序 时间复杂度为O(n ^ 2)
 */
public class Code03_InsertionSort {
    public static void insertSort(int[] arr) {

        int n = arr.length;
        //处理边界
        if (arr == null || n < 2) {
            return;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int testTimes = 1000000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long start = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            insertSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("一共执行了 ：" + (end - start) / 1000 + "秒钟");
        System.out.println(succeed ? "YES!!!" : "Occured a mistake");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }

    private static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
        }
        return arr;
    }
}

希尔排序

package xyz.standalon.sort;

import java.util.Arrays;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-12 20:46
 * @desc: 希尔排序 时间复杂度为: O(n ^ 1.3 ~ n ^ 2) 比 时间复杂度 nlogn 要大
 * 1. shell排序是建立在 插入排序的基础上
 */
public class Code01_ShellSort {
    public static void shellSort(int[] arr) {
        int N = arr.length;
        //处理边界
        if (arr == null || N < 2) {
            return;
        }
        // 定义增量
        int step = N / 2;
        int left = 0;
        int right = N - 1;
        while (step > 0) {
            //logic code
            for (int i = step; i <= right; i++) {
                //当step为 1 时,执行插入排序
                for (int j = i; j >= step; j -= step) {
                    if (arr[j] < arr[j - step]) {
                        swap(arr, j, j - step);
                    } else {
                        break;
                    }
                }
            }
            //循环增量
            step = step / 2;
        }
        //方式二: 使用for循环但是 运行耗时比方式一短
        /*for (;step > 0;step = step / 2){
            for (int i = step;i <= right;i++){
                for (int j = i;j >= step;j -= step){
                    if (arr[j] < arr[j - step]){
                        swap(arr,j,j - step);
                    }
                }
            }
        }*/

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int testTimes = 2000000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long start = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            shellSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("一共执行了 ：" + (end - start) / 1000 + "秒钟");
        System.out.println(succeed ? "YES!!!" : "Occured a mistake");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        shellSort(arr);
        printArray(arr);
    }

    private static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
        }
        return arr;
    }
}

归并排序

package xyz.standalon.sort;

import java.util.Arrays;

/**
 * @version 22.05
 * @author: javacoldeyes
 * @date: 2022-05-12 21:45
 * @desc: 归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。
 * 1. 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 * 2. 归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。
 * 3. 归并排序适用于数据量大，并且对稳定性有要求的场景。
 */
public class Code02_MergeSort {

    // 递归使用归并排序,对arr[left...right]的范围进行排序
    //需优化改进
    // todo...
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if (arr[mid] > arr[mid + 1]) {
            //进行merge排序
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            //开始处理元素
            if (l > mid) { //左边元素全部处理完成
                arr[k] = aux[j - l];
            } else if (j > r) { //右边元素全部处理完成
                arr[k] = aux[i - l];
            } else if (arr[i - l] < arr[j - l]) { // 左半部分所指元素 < 右半部分所指元素
                arr[k] = arr[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = arr[j - l];
                j++;
            }
        }

    }

    // 参考百度百科
    public static int[] mergeSortInBaidu(int[] nums, int l, int h) {
        if (l == h)
            return new int[]{nums[l]};

        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSortInBaidu(nums, l, mid); //左有序数组
        int[] rightArr = mergeSortInBaidu(nums, mid + 1, h); //右有序数组
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组

        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }

    public static void main(String[] args) {
        int testTimes = 10;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        long start = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSortInBaidu(arr1, 0, arr1.length - 1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("一共执行了 ：" + (end - start) / 1000 + "秒钟");
        System.out.println(succeed ? "YES!!!" : "Occured a mistake");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
//        int[] mergeArr =mergeSortInBaidu(arr,0,arr.length - 1);
        mergeSort(arr, 0, arr.length - 1);
       /* for (int num :
                mergeArr) {
            System.out.print(num + " ");
        }*/
        printArray(arr);
    }

    private static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    private static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (maxValue + 1) * Math.random());
        }
        return arr;
    }
}

随机化快速排序

双路快速排序

三路排序算法