九大排序算法（Java实现）

标签：排序算法   sel   插入   ati   java   wap   ready   public   索引   

1、冒泡排序

public class Bubble_sort {

    /**
     * 公共冒泡排序接口
     * @param arr 带排序数组
     */
    public static void sort(int[] arr) {
        if (arr == null) return;
        int len = arr.length;
        for (int j = len - 1; j > 0; j--) {
            for (int i = 0; i  arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }

    /**
     * 通用交换方法
     * @param arr  数组
     * @param i    元素1索引
     * @param j    元素2索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}    

2、选择排序

public class Select_sort {

    /**
     * 选择排序公共接口
     * @param arr
     */
    public static void sort(int[] arr) {
        if (arr == null) return;
        int len = arr.length;
        for (int j = len - 1; j > 0; j--) {
            int max = j;
            for (int i = 0; i = arr[max]) {
                    max = i;
                }
                swap(arr, max, j);
            }
        }
    }

    /**
     * 通用交换方法
     * @param arr  数组
     * @param i    元素1索引
     * @param j    元素2索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3、插入排序

public class Insertion_sort {

    /**
     * 插入排序
     * @param arr 待排序数组
     */
    public static void sort(int[] arr) {
        if (arr == null) return;
        // 待排序区间 [1...len-1]
        for (int j = 1; j = 0 && arr[i] > key) {
                arr[i + 1] = arr[i];
                i--;
            }
            arr[i + 1] = key;
        }
    }
}

4、快速排序

public class Quick_sort {
    private static final int MIN_VALUE = 7;

    public static void sort(int[] arr) {
        if (arr == null) return;
         sorting(arr, 0, arr.length - 1);
    }

    private static void sorting(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        if (hi- lo 

6、归并排序

public class Merge_sort {
    /**
     * 转为插入排序的临界值
     */
    private static final int MIN_SIZE = 7;

    /**
     * 公共归并排序
     * @param arr 待排序数组
     */
    public static void sort(int[] arr) {
        if (arr == null) return;
        int[] temp = new int[arr.length];
        sorting(arr, temp, 0, arr.length - 1);
    }

    /**
     * 归并排序（私有）
     */
    private static void sorting(int[] arr, int[] temp, int lo, int hi) {
        if (lo >= hi) return;
        // less than MIN_SIZE  user insertion_sort
        if (hi - lo >> 1;
        sorting(arr, temp,  lo, mid);
        sorting(arr, temp, mid + 1, hi);
        merge(arr, temp, lo, mid, hi);
    }

    /**
     * 归并方法
     */
    private static void merge(int[] arr, int[] temp,  int lo, int mid, int hi) {
        for (int i = lo; i  mid) {
                arr[k] = temp[j++];
            } else if (j > hi) {
                arr[k] = temp[i++];
            } else if (temp[i] 

7、堆排序

public class Heap_sort {

    /**
     * 公共堆排序方法
     * @param arr
     */
    public static void sort(int[] arr) {
        int len = arr.length;

        // 1.堆有序
        for (int k = (len / 2) - 1; k >= 0; k--) {
            sink(arr, k, len);
        }

        // 2.交换，调整
        while (len  > 1) {
            swap(arr, 0, len - 1);
            len--;
            sink(arr, 0, len);
        }
    }

    /**
     * 下沉操作
     * 构建堆有序：任意节点大于等于其子节点的值
     */
    public static void sink(int[] arr, int k, int len) {
        while ((2 * k + 1) 

8、希尔排序

public class Shell_sort {
    public static void sort(int[] arr) {
        int len = arr.length;
        int h = 1;
        while (h = 1) {
            // 内部包裹一个插入排序
            for (int j = h; j = 0 && arr[i] > key) {
                    arr[i + h] = arr[i];
                    i -= h;
                }
                arr[i + h] = key;
            }
            h = h / 3;
        }
    }
	// 数组交换
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

9、计数排序

public class Count_sort {

    public static void sort(int[] arr, int max) {
        int[] aus = new int[max + 1];
        // 统计
        for (int num : arr) {
            aus[num] += 1;
        }
        // 重写
        int idx = 0;
        for (int i = 0; i 

九大排序算法（Java实现）

标签：排序算法   sel   插入   ati   java   wap   ready   public   索引   

原文地址：https://www.cnblogs.com/xfzhao1419/p/14017205.html