【Java系列】八大排序算法

‍

今日立春，一年之计从码字开始吧~

今年一定要更加努力呀

目录

一、前言

二、八大排序算法

三、历史文章指路

一、前言

时隔4年，我终于把八大排序算法梳理了一遍，比起大学时零零散散的学习，现在就是一个大规范，当然代码是从优秀小伙伴那里Ctrl+C过来的，就是当我复习了一遍好多年没考过的题吧，哈哈哈。

笔记里还有2018年学习的痕迹，当时还在maopao。

当然要是现杀的话，估计只能现杀maopao，菜…

二、八大排序算法

一、交换排序

1、冒泡排序

2、快速排序

二、插入排序

1、直接插入排序

2、希尔排序

三、选择排序

1、简单选择排序

2、堆排序

四、归并排序

五、基数排序

1、冒泡排序（交换排序）

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        bubbleSort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

2、快速排序（交换排序）

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        quickSort(arr, 0, arr.length - 1);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = arr[low];

        while (i < j) {
            //从右往左扫描，找到第一个比基准值小的元素
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //从左往右扫描，找到第一个比基准值大的元素
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j - 1);
        //递归调用右半数组
        quickSort(arr, j + 1, high);
    }
}

3、直接插入排序（插入排序）

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        insertSort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                int j; //插入的位置
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    arr[j + 1] = arr[j]; //移动数据
                }
                arr[j + 1] = temp; //插入数据
            }
        }
    }
}

4、希尔排序（插入排序）

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        shellSort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    public static void shellSort(int[] arr) {
        //step:步长
        for (int step = arr.length / 2; step > 0; step /= 2) {
            System.out.printf("step：" + step + "n");
            //对一个步长区间进行比较 [step,arr.length)
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;

                //对步长区间中具体的元素进行比较
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    //j为左区间的取值，j+step为右区间与左区间的对应值
                    arr[j + step] = arr[j];
                }
                //此时step为一个负数，[j + step]为左区间上的初始交换值
                arr[j + step] = value;
            }
        }
    }
}

5、简单选择排序（选择排序）

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        selectsort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    public static void selectsort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i; //最小元素的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j; //找最小值
                }
            }
            //交换位置
            if (i != min) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
}

6、堆排序（选择排序）

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        heapSort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    
    public static void maxHeap(int[] arr, int size, int index) {
        //左子结点
        int leftNode = 2 * index + 1;
        //右子结点
        int rightNode = 2 * index + 2;
        int max = index;
        //和两个子结点分别对比，找出最大的结点
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }
        //交换位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //因为交换位置后有可能使子树不满足大顶堆条件，所以要对子树进行调整
            maxHeap(arr, size, max);
        }
    }


    public static void heapSort(int[] arr) {
        //开始位置是最后一个非叶子结点，即最后一个结点的父结点
        int start = (arr.length - 1) / 2;
        //调整为大顶堆
        for (int i = start; i >= 0; i--) {
            HeapSort.maxHeap(arr, arr.length, i);
        }
        //先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeap(arr, i, 0);
        }
    }
}

7、归并排序

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        mergeSort(arr, 0, arr.length - 1);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    
    public static void merge(int[] arr, int low, int middle, int high) {
        // 用于存储归并后的临时数组
        int[] temp = new int[high - low + 1];
        // 记录第一个数组中需要遍历的下标
        int i = low;
        // 记录第二个数组中需要遍历的下标
        int j = middle + 1;
        // 记录在临时数组中存放的下标
        int index = 0;
        // 遍历两个数组，取出小的数字，放入临时数组中
        while (i <= middle && j <= high) {
            // 第一个数组的数据更小
            if (arr[i] <= arr[j]) {
                // 把更小的数据放入临时数组中
                temp[index] = arr[i];
                // 下标向后移动一位
                i++;
            } else {
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        // 处理剩余未比较的数据
        while (i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        while (j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        // 把临时数组中的数据重新放入原数组
        for (int k = 0; k < temp.length; k++) {
            arr[k + low] = temp[k];
        }
    }


    
    public static void mergeSort(int[] arr, int low, int high) {
        int middle = (high + low) / 2;
        if (low < high) {
            // 处理左边数组
            mergeSort(arr, low, middle);
            // 处理右边数组
            mergeSort(arr, middle + 1, high);
            // 归并
            merge(arr, low, middle, high);
        }
    }
}

8、基数排序

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 5, 7, 1, 2, 0, 3, 6, 8};
        System.out.printf("排序前：" + Arrays.toString(arr) + "n");
        radixSort(arr);
        System.out.printf("排序后：" + Arrays.toString(arr));
    }


    
    public static void radixSort(int[] arr) {
        // 存放数组中的最大数字
        int max = Integer.MIN_VALUE;
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        // 计算最大数字是几位数
        int maxLength = (max + "").length();
        // 用于临时存储数据
        int[][] temp = new int[10][arr.length];
        // 用于记录在 temp 中相应的下标存放数字的数量
        int[] counts = new int[10];
        // 根据最大长度的数决定比较次数
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 每一个数字分别计算余数
            for (int j = 0; j < arr.length; j++) {
                // 计算余数
                int remainder = arr[j] / n % 10;
                // 把当前遍历的数据放到指定的数组中
                temp[remainder][counts[remainder]] = arr[j];
                // 记录数量
                counts[remainder]++;
            }
            // 记录取的元素需要放的位置
            int index = 0;
            // 把数字取出来
            for (int k = 0; k < counts.length; k++) {
                // 记录数量的数组中当前余数记录的数量不为 0
                if (counts[k] != 0) {
                    // 循环取出元素
                    for (int l = 0; l < counts[k]; l++) {
                        arr[index] = temp[k][l];
                        // 记录下一个位置
                        index++;
                    }
                    // 把数量置空
                    counts[k] = 0;
                }
            }
        }
    }
}

相关代码都在Learn-Java，请阅。

https://gitee.com/weimenghua/Learn-Java.git

三、历史文章指路

关注【嘎嘎软件测试】

搞测试，不迷路

呱呱大王本呱带你飞！

嘎嘎软件测试

本账号将分享个人成长、团队管理、软件测试技能知识等内容，更新频率一周两篇，做到有思想、有观点、有深度，欢迎订阅。