基础排序算法的Java实现_Java

冒泡，选择，插入，希尔，堆排序，归并排序（递归&非递归），快排（递归非递归）

package com.kuang.method;

import java.util.Arrays;
import java.util.Stack;

public class SortMethod {
    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = new int[arr1.length];
            System.arraycopy(arr1, 0, arr2, 0, arr1.length);

            quickSort_NoRecursion(arr1);// sort

            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                succeed = false;
                System.out.println(Arrays.toString(arr1));//printArray(arr1);
                System.out.println(Arrays.toString(arr2));//printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "WTF!");

        int[] arr1 = generateRandomArray(maxSize, maxValue);
        int[] arr2 = new int[arr1.length];
        System.arraycopy(arr1, 0, arr2, 0, arr1.length);
        System.out.println(Arrays.toString(arr1));//printArray(arr);
        long t1 = System.nanoTime();

        quickSort_NoRecursion(arr1);//sort

        long t2 = System.nanoTime();
        long t3 = System.nanoTime();
        Arrays.sort(arr2);
        long t4 = System.nanoTime();

        System.out.println(Arrays.toString(arr1));//printArray(arr);
        System.out.println("我的算法耗时:" +  String.format("%.8fs", (t2 - t1) * 1e-9));
        System.out.println("内置算法耗时:" +  String.format("%.8fs", (t4 - t3) * 1e-9));

    }

    //生成随机数组
    public 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()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

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

    //冒泡排序
    public static void bubbleSort(int[] arr){

        for (int i = arr.length - 1; i >= 0; i--) {
            boolean flag = false;
            for (int j = 0; j <= i; j++) {
                if (j > 0 && arr[j - 1] > arr[j]){
                    swap(arr, j - 1, j);
                    flag = true;
                }
            }
            if (!flag)break;
        }
    }

    //选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            if (min != i){
                swap(arr, i, min);
            }
        }
    }

    //插入排序
    public static void insertSort(int[] arr){
        int i, j;
        for (i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (j = i; j > 0 && arr[j - 1] > temp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    //希尔排序
    public static void shellSort(int[] arr){
        int len = arr.length;
        int i, j;
        for (int increment = len / 2; increment > 0; increment /= 2) {
            for (i = increment; i < len; i++) {
                int temp = arr[i];
                for (j = i; j > increment - 1 && arr[j - increment] > temp; j -= increment) {
                    arr[j] = arr[j - increment];
                }
                arr[j] = temp;
            }
        }
    }

    //堆排序
    public static void heapSort(int[] arr){
        int len = arr.length;
        for (int i = len / 2; i >= 0; i--){
            heapAdjust(arr, i, len);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i);
        }
    }

    //
    public static void heapAdjust(int[] arr, int start, int end){
        int child = 2 * start + 1;
        while (child < end){
            if (child + 1 < end && arr[child + 1] > arr[child]){
                child++;
            }
            if (arr[child] > arr[start]){
                swap(arr, start, child);
                start = child;
                child = 2 * start + 1;
            }else{
                break;
            }
        }
    }

    //归并排序（递归）
    public static void mergeSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int start, int end){
        if (start == end){
            return;
        }
        int mid = start + ((end - start) >> 1);
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    public static void merge(int[] arr, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        int i = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end){
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid){
            temp[i++] = arr[p1++];
        }
        while (p2 <= end){
            temp[i++] = arr[p2++];
        }
        for (i = 0; i < temp.length; i++) {
            arr[start + i] = temp[i];
        }
    }

    //归并排序（非递归）
    public static void mergeSort_NoRecursion(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int len = 1;
        while (len < arr.length){
            for (int i = 0; i + len < arr.length; i += 2 * len) {
                int mid = i + len <= arr.length ? i + len - 1: arr.length - 1;
                int end = mid + len < arr.length ? mid + len: arr.length - 1;
                merge(arr, i, mid, end);
            }
            len *= 2;
        }
    }

    //快排（递归）
    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right){
        if (left < right){
            swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
            int[] p = partition(arr, left, right);
            quickSort(arr, left, p[0] - 1);
            quickSort(arr, p[1] + 1, right);
        }
    }

    public static int[] partition(int[] arr, int left, int right){
        int less = left;
        int more = right;
        while (left < more){
            if (arr[left] < arr[right]){
                swap(arr, left++, less++);
            } else if (arr[left] > arr[right]){
                swap(arr, left, --more);
            } else {
                left++;
            }
        }
        swap(arr, more, right);
        return new int[]{less, more};
    }

    //快排（非递归）
    public static void quickSort_NoRecursion(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        quickSort_NoRecursion(arr, 0, arr.length - 1);
    }

    public static void quickSort_NoRecursion(int[] arr, int left, int right){
        Stack<Integer> stack = new Stack<>();
        if (left < right) {
            stack.push(right);
            stack.push(left);
            while (!stack.isEmpty()) {
                int l = stack.pop();
                int r = stack.pop();
                swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
                int[] p = partition(arr, l, r);
                if (p[0] - 1 > l) {
                    stack.push(p[0] - 1);
                    stack.push(l);
                }
                if (p[1] + 1 < r) {
                    stack.push(r);
                    stack.push(p[1] + 1);
                }
            }
        }
    }
}