[数据结构与算法]排序算法汇总---Java实现各个排序

排序算法汇总

下图来自菜鸟教程：


下面所有方法都有static关键字，因为测试的时候需要被main函数调用，故添加static。
若需要c++版本的算法实现，可参考下面博文连接
排序算法汇总—C++实现各个排序

1、冒泡排序

    // 冒泡排序
    static void bubble_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { // n-1趟
            for (int j = 0; j < arr.length - i - 1; j++) { // n-趟数-1
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

2、直接插入排序

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

3、希尔排序

改进的插入排序

    // 希尔排序（改进的插入排序）
    static void shell_sort(int[] arr) {
        // 先求出间隔h
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1; // Knuth
        }
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j > h - 1; j -= h) {
                if (arr[j] < arr[j - h]) {
                    int temp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = temp;
                }
            }
        }
    }

4、选择排序

    // 选择排序
    static void select_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 找最小值
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 判断当前值是否需要与最小值交换
            if (min != i) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }

5、快速排序

// 快速排序
    // 先写出每一次划分的方法
    static int partition(int[] arr, int low, int high) {
        int mid = low + ((high - low) >> 2);
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
        int pivot = arr[low];
        while (low < high) {
            while (low < high && pivot <= arr[high]) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && pivot >= arr[low]) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 此时low == high
        arr[low] = pivot;
        return low;
    }

    // 接下来写快速排序的递归
    static void quick_sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quick_sort(arr, low, mid - 1);
            quick_sort(arr, mid + 1, high);
        }
    }

6、归并排序

// 归并排序
    // 首先写归并
    static void merge(int[] arr, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = 0;
        int[] temp = new int[high - low + 1];
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= high) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[low + m] = temp[m];
        }
    }

    // 下面写归并排序
    static void merge_sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = low + ((high - low) >> 1);
            merge_sort(arr, low, mid);
            merge_sort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

7、计数排序

桶排序的一种

 // 计数排序（桶排序的一种）稳定的排序算法
    static void count_sort(int[] arr){
        // 找出数组中的最大值, 方便我们创建计数数组
        int max = 0;
        for (int item : arr) {
            if (max < item){
                max = item;
            }
        }
        int[] count = new int[max + 1];
        // 下面开始计数
        for (int i = 0; i < arr.length; i++) {
            count[ arr[i] ] += 1;
        }
        //下面构造累加数组
        // 累加数组可以保证每个数字的相对位置不变，保证该排序算法的稳定性
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        //逆序遍历原数组，然后将原数组的值赋值给结果数组
        int[] ans = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = count[arr[i]] - 1; // 找出原数组数字 所对应的 结果数组 的下标
            ans[index] = arr[i];
            //因为可能有重复元素，此时count中的值可能不是1，故需要减一
            count[ arr[i] ]--;
        }
        // 最后将ans数组赋值给原arr数组, 此时ans数组已经为有序数组
        for (int i = 0; i < ans.length; i++) {
            arr[i] = ans[i];
        }
    }

8、基数排序

桶排序的一种

// 基数排序（桶排序一种）稳定的排序，与计数排序类似
    static void radix_sort(int[] arr){
        //求出数组中的最大值
        int max = 0;
        for (int item : arr) {
            if (max < item){
                max = item;
            }
        }
        // 求出最大数一共有几位
        int k = 0; //最大值共有多少位
        while (max !=0){
            k++;
            max = max / 10;
        }
        // 每个数字都是由0 - 9组成
        int[] count = new int[10];
        // 定义结果数组
        int[] ans = new int[arr.length];
        // 下面开始基数排序
        for (int i = 0; i < k; i++) {

            // 计算每次除以的值，即1， 10，100 ...
            // 10的0次方， 10的1次方
            int division = (int) Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                // 计算每一位的值
                int num = arr[i] / division % 10;
                count[num]++;
            }
            // 构造累加数组
            // 累加数组可以保证每个数字的相对位置不变，保证该排序算法的稳定性
            for (int j = 1; j < count.length; j++) {
                count[j] = count[j] + count[j - 1];
            }
            //求出每一次的结果数组
            for (int j = arr.length - 1; j >= 0; j--) {
                int index = arr[j] / division % 10 - 1;
                ans[index] = arr[j];
                // 因为可能有重复元素，需要减一
                count[ arr[j] / division % 10]--;
            }
            for (int j = 0; j < ans.length; j++) {
                arr[j] = ans[j];
            }
            // 清空count数组，为下一位做准备
            for (int j = 0; j < count.length; j++) {
                count[j] = 0;
            }
        }
    }

9、堆排序

    //堆排序
    // 先写堆调整heapify

    /**
     * @param arr 数组
     * @param len 数组长度
     * @param pos 需要调整的位置
     */
    static void heapify(int[] arr, int len, int pos) {
        if (pos >= len) {
            return;
        }
        // 找到需要调整结点的最后子节点
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int max = pos;
        if (left < len && arr[left] > arr[max]) {
            max = left;
        }
        if (right < len && arr[right] > arr[max]) {
            max = right;
        }
        // 判断是否需要调整
        if (max != pos) {
            int temp = arr[max];
            arr[max] = arr[pos];
            arr[pos] = temp;
            heapify(arr, len, max);
        }
    }

    // 构建堆
    static void build_heap(int[] arr) {
        // 最后一个元素下标
        int last_index = arr.length - 1;
        // 最后一个元素的父节点，即最后一个非叶结点
        int parent_index = (last_index - 1) / 2;
        for (int i = parent_index; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
    }

    // 堆排序
    static void heap_sort(int[] arr) {
        build_heap(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            // 每次交换最后一个元素与第一个元素
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 重新调整堆
            heapify(arr, i, 0);
        }
    }

二分查找

    // 二分法查找值（数组为有序数组）

    /**
     *
     * @param arr 目标数组
     * @param target 目标值
     * @return 返回目标值的数组下标，没有则返回-1
     */
    int binary_search(int[] arr, int target){
        if (arr.length == 0){
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right){
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == target){
                return mid;
            }else if (arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

完整代码及测试用例

package com.example.leetcode;

public class test_sort_algorithm {
    public static void main(String[] args) {
        int[] arr = {1, 3, 7, 5, 9, 8, 6, 4, 2};
//        bubble_sort(arr);
//        select_sort(arr);
//        insert_sort(arr);
//        shell_sort(arr);
//        merge_sort(arr, 0, arr.length - 1);
//        quick_sort(arr, 0, arr.length - 1);
//        heap_sort(arr);
//        count_sort(arr);
        radix_sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    // 冒泡排序
    static void bubble_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { // n-1趟
            for (int j = 0; j < arr.length - i - 1; j++) { // n-趟数-1
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 选择排序
    static void select_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 找最小值
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 判断当前值是否需要与最小值交换
            if (min != i) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }

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

    // 希尔排序（改进的插入排序）
    static void shell_sort(int[] arr) {
        // 先求出间隔h
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1; // Knuth
        }
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j > h - 1; j -= h) {
                if (arr[j] < arr[j - h]) {
                    int temp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = temp;
                }
            }
        }
    }

    // 快速排序
    // 先写出每一次划分的方法
    static int partition(int[] arr, int low, int high) {
        int mid = low + ((high - low) >> 2);
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
        int pivot = arr[low];
        while (low < high) {
            while (low < high && pivot <= arr[high]) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && pivot >= arr[low]) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 此时low == high
        arr[low] = pivot;
        return low;
    }

    // 接下来写快速排序的递归
    static void quick_sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quick_sort(arr, low, mid - 1);
            quick_sort(arr, mid + 1, high);
        }
    }

    // 归并排序
    // 首先写归并
    static void merge(int[] arr, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = 0;
        int[] temp = new int[high - low + 1];
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= high) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[low + m] = temp[m];
        }
    }

    // 下面写归并排序
    static void merge_sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = low + ((high - low) >> 1);
            merge_sort(arr, low, mid);
            merge_sort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    //堆排序
    // 先写堆调整heapify

    /**
     * @param arr 数组
     * @param len 数组长度
     * @param pos 需要调整的位置
     */
    static void heapify(int[] arr, int len, int pos) {
        if (pos >= len) {
            return;
        }
        // 找到需要调整结点的最后子节点
        int left = 2 * pos + 1;
        int right = 2 * pos + 2;
        int max = pos;
        if (left < len && arr[left] > arr[max]) {
            max = left;
        }
        if (right < len && arr[right] > arr[max]) {
            max = right;
        }
        // 判断是否需要调整
        if (max != pos) {
            int temp = arr[max];
            arr[max] = arr[pos];
            arr[pos] = temp;
            heapify(arr, len, max);
        }
    }

    // 构建堆
    static void build_heap(int[] arr) {
        // 最后一个元素下标
        int last_index = arr.length - 1;
        // 最后一个元素的父节点，即最后一个非叶结点
        int parent_index = (last_index - 1) / 2;
        for (int i = parent_index; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
    }

    // 堆排序
    static void heap_sort(int[] arr) {
        build_heap(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            // 每次交换最后一个元素与第一个元素
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            // 重新调整堆
            heapify(arr, i, 0);
        }
    }

    // 计数排序（桶排序的一种）稳定的排序算法
    static void count_sort(int[] arr){
        // 找出数组中的最大值, 方便我们创建计数数组
        int max = 0;
        for (int item : arr) {
            if (max < item){
                max = item;
            }
        }
        int[] count = new int[max + 1];
        // 下面开始计数
        for (int i = 0; i < arr.length; i++) {
            count[ arr[i] ] += 1;
        }
        //下面构造累加数组
        // 累加数组可以保证每个数字的相对位置不变，保证该排序算法的稳定性
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        //逆序遍历原数组，然后将原数组的值赋值给结果数组
        int[] ans = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = count[arr[i]] - 1; // 找出原数组数字 所对应的 结果数组 的下标
            ans[index] = arr[i];
            //因为可能有重复元素，此时count中的值可能不是1，故需要减一
            count[ arr[i] ]--;
        }
        // 最后将ans数组赋值给原arr数组, 此时ans数组已经为有序数组
        for (int i = 0; i < ans.length; i++) {
            arr[i] = ans[i];
        }
    }

    // 基数排序（桶排序一种）稳定的排序，与计数排序类似
    static void radix_sort(int[] arr){
        //求出数组中的最大值
        int max = 0;
        for (int item : arr) {
            if (max < item){
                max = item;
            }
        }
        // 求出最大数一共有几位
        int k = 0; //最大值共有多少位
        while (max !=0){
            k++;
            max = max / 10;
        }
        // 每个数字都是由0 - 9组成
        int[] count = new int[10];
        // 定义结果数组
        int[] ans = new int[arr.length];
        // 下面开始基数排序
        for (int i = 0; i < k; i++) {

            // 计算每次除以的值，即1， 10，100 ...
            // 10的0次方， 10的1次方
            int division = (int) Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                // 计算每一位的值
                int num = arr[i] / division % 10;
                count[num]++;
            }
            // 构造累加数组
            // 累加数组可以保证每个数字的相对位置不变，保证该排序算法的稳定性
            for (int j = 1; j < count.length; j++) {
                count[j] = count[j] + count[j - 1];
            }
            //求出每一次的结果数组
            for (int j = arr.length - 1; j >= 0; j--) {
                int index = arr[j] / division % 10 - 1;
                ans[index] = arr[j];
                // 因为可能有重复元素，需要减一
                count[ arr[j] / division % 10]--;
            }
            for (int j = 0; j < ans.length; j++) {
                arr[j] = ans[j];
            }
            // 清空count数组，为下一位做准备
            for (int j = 0; j < count.length; j++) {
                count[j] = 0;
            }
        }
    }

    // 二分法查找值（数组为有序数组）

    /**
     *
     * @param arr 目标数组
     * @param target 目标值
     * @return 返回目标值的数组下标，没有则返回-1
     */
    int binary_search(int[] arr, int target){
        if (arr.length == 0){
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right){
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == target){
                return mid;
            }else if (arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

其实，每次重新写排序算法，都对各个算法有新的理解和感悟，对各个算法的思想和边界问题更加清楚。
另外，本文没有桶排序的专门算法，因博主认为计数排序和基数排序是比较常见的桶排序算法，且一般桶排序中，还需要其他排序算法来对桶内进行排序，故并未写出。
最后，希望我们都可以进大厂，拿高薪！！！