冒泡排序

思想： 冒泡排序，就是像气泡一样，将大的元素慢慢冒泡到最后的位置

比较思想是： 相邻的两个元素依次比较，如果前面的元素大于后面的元素，则进行交换

代码实现基本步骤：【两个for循环搞定】
1.确定比较的趟数【元素的数量-1】
2.两两进行判断比较，进行交换
3.比较迷惑的就是两个for循环的条件设置，i和j的起始值
4.对冒泡排序的改进，可以设置一个标志属性flag，判断当前排序趟数有没进行交换，若没有进行交换，说明后面的元素已经有序，可以结束排序了

代码实现

public static void bubbleSort(int[] arr) {
//      int[] arr={-3,9,8,1,3,5,2};
        for (int i = 1; i < arr.length; i++) {
            //flag用于对冒泡排序的优化
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
            System.out.println("第" + i + "次排序后的数组为：" + Arrays.toString(arr));
        }
    }

排序结果

选择排序

思想：选择排序，就是每趟选择最小的元素放在前面

比较思想是： 在每趟排序中，用一个临时变量min标记最小值元素的下标，若遇到更小的元素，就把该元素的下标赋值给min，每趟排序到最后元素时，进行交换

代码实现基本步骤：【两个for循环搞定】
1.确定比较的趟数【元素的数量-1】
2.先假定下标0就是最小值，即min=0
3.然后进行一个个比较，若遇到比下标值min更小的元素，就将该元素的下标赋值给min
4.然后在每趟的最后交换下标为min的元素，完成一趟的排序

代码实现

public static void selectionSort(int[] arr){
        //int[] arr = {-3, 9, 8, 1, 3, 5, 2}; 
        for (int i = 1; i < arr.length ; i++) {
            //每趟开始前，都假定第一个元素为最小;
            //第一趟的最小元素坐标为0，第二趟最小元素坐标为1...
            int min=i-1;
            for (int j = i-1; j < arr.length-1; j++) {

                if (arr[min]>arr[j+1]){
                    min=j+1;
                }
            }
            if (min!=i-1){
                //一定得用 arr[i-1]
                int temp=arr[i-1];
                arr[i-1]=arr[min];
                arr[min]=temp;
            }
            System.out.println("第" + i + "次排序后的数组为：" + Arrays.toString(arr));
        }
    }

排序结果

插入排序

思想： 插入排序，就是将未排好序的元素插入到已排好序的元素中

比较思想： 将要排序的元素分成两组，一组已排序，一组未排序，然后从未排序的元素中取出一个，插入到已排序的元素中

代码实现基本步骤：【两个for循环搞定】
1.将所有元素分为两组，刚开始默认第一个元素是排序的，为一组
2.找到未排序的组中的第一个元素，插入到已经排好序的元素中
3.倒序遍历已排序的元素，依次和待插入元素作比较，知道找到比待插入元素小的元素，然后插入，其他元素依次后移一位

代码实现

public static void insertionSort(int[] arr){
        //int[] arr = {-3, 9, 8, 1, 3, 5, 2};
        //从下标为1的开始选择插入，因为下标为0只有一个元素，默认有序
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
            System.out.println("第" + i + "次排序后的数组为：" + Arrays.toString(arr));
        }
    }

排序结果

希尔排序

思想： 是插入排序的一种改进，原本的插入排序的插入时只能一位一位的进行比较排序，而希尔排序先将待排序的元素分组，分组后再按照插入排序的算法进行各组排序

例子
排序前：{9,1,2,5,7,4,8,6,3,5}
排序后：{1,2,3,4,5,5,6,7,8,9}
排序步骤如下图：
在这里插入图片描述

代码实现基本步骤：
1.先确定一个增量h，h初始值一般是元素个数的一半，以h为跨度组成一组；各组间进行插入排序，以达到组内有序
2.改变增量h=h/2;在重复1的步骤，知道h=1为止

代码实现

public static void shellSort(int[] arr) {
        //int[] arr = {-3, 9, 8, 1, 3, 5, 2};
        int length = arr.length;
        int temp;
    	
        for (int step = length / 2; step >= 1; step /= 2) {
            //进行分组排序
            for (int i = step; i < length; i++) {
                temp = arr[i];
                //j类似插入排序中已排好序的第一个下标
                int j = i - step;
                //每一组进行排序[插入排序]
                while (j >= 0 && temp < arr[j]) {
                    //arr[j+step]不能换成arr[i],因为在while循环中，一直在改变
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
        System.out.println("排序之后的数组是："+Arrays.toString(arr));
    }

排序结果

归并排序

思想： 归并排序是先将数组进行分组，每次对半分，直到每个子数组的元素只有一个；然后每个子数组进行逐一归并，即两两将各自有序的数组合并为一个有序的数组，最终全部有序。

归并排序是一种典型的分而治之思想：自上而下的递归，自下而上的迭代；

例子：
排序前：{8,4,5,7,1,3,6,2}
排序后：{1,2,3,4,5,6,7,8}
排序步骤如下图：
在这里插入图片描述

实现步骤：
1.将待排序数组进行递归分组，直到子数组元素都为1；
2.比较左右子数组，将两个有序的子数组合并为一个大的有序数组；

代码实现

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {-3, 9, 8, 1, 3, 5, 2};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    //进行排序
    protected static int[] sort(int[] sourceArray) {
        //复制数组，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //若只有一个元素，直接返回
        if (arr.length < 2) {
            return arr;
        }
        //找到中间下标值
        int mid = arr.length / 2;
        //分成左右两组，分别递归处理
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        //当sort递归到最后，会反过来进行merge合并
        return merge(sort(left), sort(right));
    }

    //进行合并
    //注意left，right已经分别有序
    protected static int[] merge(int[] left, int[] right) {
        System.out.println("left=" + Arrays.toString(left));
        System.out.println("right=" + Arrays.toString(right));

        //创建辅助数组，存放合并后的有序的数组
        int[] result = new int[left.length + right.length];

        int i = 0;//标记left数组的下标
        int j = 0;//标记right数组的下标
        int k = 0;//标记result数组的下标

        //反复比较两个数组的组，小的先放，直到一个数组放完
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        //将未放完的数组继续放
        while (i < left.length) {
            result[k++] = left[i++];
        }
        //将未放完的数组继续放
        while (j < right.length) {
            result[k++] = right[j++];
        }
        System.out.println("排序后=" + Arrays.toString(result));
        System.out.println("------------------------");
        return result;
    }
}

排序结果

快速排序

思想： 快速排序的思想是在未排序的数组中，选定一个基准值，该基准值一般是该数组的第一个元素；然后以基准值为界限，把比基准值小的元素放在左边，把比基准值大的元素放在右边；然后再把基准值的左右两部分看作子数组，分别再进行递归上面的步骤；

例子
排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}
排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}
排序步骤如下图：
在这里插入图片描述

注意： 基准值左右两边的数组各自依旧无序，只是左边的数组值小于基准值，右边的数组值都大于基准值；

实现步骤：
1.在待排序数组中挑出一个基准值，默认就是数组的第一个元素
2.分别给定两个’哨兵’ i 和 j ，让 i 和 j 分别指向第一个元素和最后一个元素
3.进行比较，先从后面进行比较，遇到比基准值小的就让 j 停下来
4.进行比较，再从前面进行比较，遇到比基准值大的就让 i 停下来
5.检查 i 和 j 的位置，若无误，则两个停下来的元素进行交换，否则出错
6.当 i 和 j 相遇时，即i=j，则都停下来，再与基准值进行交换
7.将交换后的基准值的左右两边的数组再次递归排序，完成

代码实现

public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = {88, -44, -3, 9, 8, 1, 3,};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后："+Arrays.toString(arr));
    }
    //快速排序核心代码
    //start是待排序的第一个元素，end是待排序的最后一个元素
    public static void quickSort(int[] nums, int start, int end) {
        //进行校验
        if (start > end) {
            return;
        }
        //i,j是进行移动的坐标,base是设定的基准值，假设为第一个
        int i = start;
        int j = end;
        int base = nums[start];
        //循环比较
        while (i < j) {
            //先从后面比较，遇到比基准值小的就停下来
            //因为假设的基准是左边的，所以必须得先右边先比较
            while (i < j && nums[j] >= base) j--;
            //再从前面比较，遇到比基准值大的就停下来
            while (i < j && nums[i] <= base) i++;
            if (i < j) {
                //进行交换
                swap(nums, i, j);
            }
        }
        //当比较完之后，基准值和i或者j所在下标元素值交换，完成这一趟
        swap(nums, start, i);
        //对基准值左边的子数组进行递归快速排序
        quickSort(nums, start, j - 1);
        //对基准值右边的子数组进行递归快速排序
        quickSort(nums, j + 1, end);
    }

    //交换元素
    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}