冒泡排序

冒泡排序是我们能想到的一个最简单的排序方法，它的思想就是将一个数组内的数字和相邻的进行比较，把比较大的放在靠后位置，当从头到尾比较一遍，我们就可以拿到最大的那个数据了，这样循环，每次排除最大的那个，就可以完成排序。
上图：

代码实现：（写法不唯一，可以自己简化写出）

public class BubbleSort { 
    //冒泡，arr：需要排序的数组，n：需要排序的数组的长度
    public static void Bubble(int[] arr,int n){ 
        for (int i = 0; i < n-1; i++) { 
            if(arr[i]>arr[i+1]){ //如果前面的比后面的大，就交换位置
                int temp = arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
    }
    public static void bubbleSort(int[] arr){ 
        int n = arr.length;
        while (n>1){ //循环找出最大的，直到剩下一个数
            Bubble(arr, n);
            n--;
        }
    }
    public static void main(String[] args) { 
        int arr[] = { 1,4,7,10,8,3,6};
        bubbleSort(arr);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

选择排序

选择排序的思想就是，我们把我们的需要排序的数组看成一个已经排序好的数组和未排序的数组的组合，初始情况排序好的数组没有值，我们对未排序的数组进行筛选，挑出最大的那个数，然后与未排序最后的那个数进行交换，这个最大的数就放进了已经排好序的数组中了。
图解：

代码实现：

public class SelectSort { 
      //arr是需要排序的数组，n是需要排序的数组长度
     //这个方法就是获取当前需要排序的数组中最大的值得下标
    public static int getMaxIndex(int[] arr, int n) { 
        int max = arr[0];
        int index = 0;
        for (int i = 1; i < n; i++) { 
            if (arr[i] > max) { 
                max = arr[i];
                index = i;
            }
        }
        return index;
    }
    public static void selectSort(int[] arr) { 
        int n = arr.length - 1;
        
        while (n > 1) { 
        //交换未排序的数组中最大的值与最后一个数的位置
            int maxIndex = getMaxIndex(arr, n);
            int temp = arr[n];
            arr[n] = arr[maxIndex];
            arr[maxIndex] = temp;
            n--;//交换后，这个最大的数就已经在排好序的数组中
        }
    }

    public static void main(String[] args) { 
        int arr[] = { 1, 4, 7, 10, 8, 3, 6};
        selectSort(arr);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

插入排序

插入排序的思想就是我们把数组看成一个排好序(初始可能只有一个数)和未排序的数组的组合，我们在未排序的数组中取出一个A，在已经排好序的数组中找到arr[i]，如若arr[i]>A,那么我们就将他放在arr[i]和arr[i-1]这个位置。(如果没有理解，参考图片理解）

代码实例：

public class InsertSort { 
    public static void insert(int[] arr, int n) { 
        int key = arr[n];//记下当前需要排序的数
        int i = n;
        while (arr[i-1]>key){ //在找到可以放的位置（小于key）之前，我们就把所有的数往后面”挪“一位
            arr[i]=arr[i-1];
            i--;
            if(i==0){ //如果到开头的位置还没有出现小于的情况，那么我们就应该将其放在开头。
                break;
            }
        }
        arr[i]=key;
    }
    public static void insertSort(int arr[]){ 
        for (int i = 1; i < arr.length ; i++) { //默认从1开始，因为第一个数我们默认已经排好序
            insert(arr,i);
        }
    }
    public static void main(String[] args) { 
        int arr[] = { 1,4,7,10,8,3,6};
        insertSort(arr);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

希尔排序

我们会了插入排序，不妨看看插入排序有哪些缺点？假设一串数字的前面很多都已经是有序的，只有最后的几个是没有排序的，比如：{2，3，4，5，6，7，8，9，1}，我们可以看到，只需要把1放在开头就可以，但是使用插入排序很不理想。
希尔排序的基本思想就是：我们把数组按照一定增量分成组，每次比较组内的值大小进行插入排序，然后增量逐渐缩小，继续排序，当我们的增量变为1的时候，所有的数就已经排好序（还是看图解比较好理解），这样的好处是，在分组的几次排序后，我们就将一些较小的数放在了最前面，就不会出现上述例子的情况

代码实现：

public class ShellSort { 
    //同样是插入排序，但是每次排序的都是当前组内的成员
    //arr:需要排序的数组，n：开始排序的位置，gap增量
    public static void shellInsert(int[] arr, int n, int gap) { 
        int key = arr[n];//记下当前需要排序的数
        while ( n-gap>=0 && key < arr[n - gap]) { 
            arr[n] = arr[n - gap];
            n -= gap;//寻找下一个组内成员
        }
        arr[n] = key;
    }

    public static void shellSort(int[] arr) { 
        for (int gap = arr.length / 2; gap >0; gap /= 2) { 
            for (int i = gap; i < arr.length; i++) { 
                shellInsert(arr,i,gap);
            }
            System.out.println();
        }
    }
    public static void main(String[] args) { 
        int arr[] = { 2,3,4,5,6,7,8,1};
        shellSort(arr);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

快速排序

快速排序是我们最常用并且最快的一种排序算法，实现起来也很简单，但有点难理解，其主要思想就是我们在数组中找到一个基准数，然后对数组的左右两边进行遍历，找到一个比基准数大的数和一个比基准数小的数，将两个数换位，这样一轮循环下来，当左右两个指针相遇的时候，左边都是比基准数小的数，右边的都是比基准数大的数，然后我们对左右两边再递归运算，最后将所有的数都进行了排序。（话不多说，看图理解）

步骤简述：
我们的中心思想就是把比基准数大的放在基准数右边，比基准数小的放在基准数左边
1、定义left，right，基准数base=arr[left]
2、先从right开始找，找到一个比base小的树，在开始从left开始找比base大的(如果我们从左边先开始找，那么我们的基准数就得是arr[right]，否则我们进行第3步的时候，交换后可能会把一个比基准数大的交换到left位置，这样就无法继续操作)
3、当指针相遇的时候，我们交换指针位置和基准数的位置
4、此时新的基准数产生(指针相遇位置的数）
5、调整left和right，递归执行上述步骤

public class QuickSort { 
    public static void quickSort(int[] arr, int left, int right) { 
        //如果左边边界大于右边，就return
        if (left >= right) { 
            return;
        }

        int l = left;//用于标识左边指针
        int r = right;// 用于标识右边指针
        int base = arr[left];//记录基准数
        //判断指针有没有相遇
        while (l != r) { 
            while (arr[r] >= base && r > l) { //先从右往左找出比基准数小的数
                r--;
            }
            while (arr[l] <= base && l < r) { //再从左向右找出比基准数大的数
                l++;
            }
            //交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //当指针相遇时，交换基准数和指针的位置，此时指针位置就是基准数，指针左边的都不大于基准数，右边的都不小于基准数
        arr[left] = arr[l];
        arr[l] = base;

        //递归调用，将左边所有的数的进行排序
        quickSort(arr, left, l - 1);
        //右边的排序
        quickSort(arr, r + 1, right);
    }

    public static void main(String[] args) { 
        int[] arr ={ 4, 1, 7, 6, 8, 3, 10};
        int left = 0;
        int right = arr.length - 1;
        quickSort(arr, left, right);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

归并排序：

在学习归并排序之前，我们先看一个例子，如果一个数组{2，5，8，9，1，3，4，7}，这个数组的特点是前半部分和后半部分都是有序的，我们对他进行排序，那么我们就把它分成两个有序的数组，然后通过对比，将较小的放进数组中，最终就得到了一个有序的数组。这个思想就是归并
那么我们就先把这个例子用图解的形式分析一下，然后代码实现。当我们完成下面的例子后，就可以着手去实现任意情况的数组的归并排序。

实现代码：

public class MergeSort { 
    
    public static void Merge(int[] arr, int l, int r, int m) { 
        int LEFT_SIZE = m - l;
        int RIGHT_SIZE = r - m + 1;
        //创建两个数组存
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        for (int i = l; i < m; i++) { 
            left[i-l] = arr[i];
        }
        for (int i = m; i <= r; i++) { 
            right[i-m] = arr[i];
        }
        //通过上述步骤，我们就可以把数组分成两个有序的数组，分别存放在两个不同的数组中
        int i=0,j=0,k=l;//定义三个指针，分别代表left数组、right数组、arr数组的初始指针
        while(i<LEFT_SIZE && j<RIGHT_SIZE ){ //如果两边都没有到数组边界
            if(left[i]<right[j]){ //我们比较两个位置，将较小的放在数组的位置
                arr[k]=left[i];
                k++;i++;
            }
            else { 
                arr[k]=right[j];
                k++;j++;
            }
        }
        //出了上述循环，但是仍然存在可能有数组中的数没有放完的情况，我们直接按照顺序放入即可。
        while (i<LEFT_SIZE){ 
            arr[k]=left[i];
            k++;i++;
        }while (j<RIGHT_SIZE){ 
            arr[k]=right[j];
            k++;j++;
        }

    }
    public static void main(String[] args) { 
        int[] arr = { 2, 5, 8, 9, 1, 3, 4, 7};
        int l = 0;
        int r =arr.length-1;
        int mid =arr.length/2;
        Merge(arr, l, r,mid);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

这样我们就把这个数组排好序了。
这个时候就有人问了：你这刚好两边都是有序的，现实中可不是这样。
那我们想想，其他混乱一点的数组可以使用归并吗？
答案当然是可以
如果有一定经验的小伙伴，肯定已经想到了分治，在上述案例中，我们是把数据砍成两段，每段都是有序的，那么给出一个混乱的数据，我们递归的去砍，到最后砍的两边各剩一个数，那么它不就是上述情况了？就好比{5，3}，我们砍一下{3}、{5}，使用归并，自然就是{3，5}了。如果还不明白，我们接着看图

用代码实现它：

  public static void Merge(int[] arr, int l, int r, int m) { 
        int LEFT_SIZE = m - l;
        int RIGHT_SIZE = r - m + 1;
        //创建两个数组存
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        for (int i = l; i < m; i++) { 
            left[i-l] = arr[i];//注意 此时的left[i-l]不能写arr[i],因为在递归中l的动态变化的，如果写死的话，可能出现角标异常的情况
        }
        for (int i = m; i <= r; i++) { 
            right[i-m] = arr[i];
        }
        //通过上述步骤，我们就可以把数组分成两个有序的数组，分别存放在两个不同的数组中
        int i=0,j=0,k=l;//定义三个指针，分别代表left数组、right数组、arr数组的初始指针
        while(i<LEFT_SIZE && j<RIGHT_SIZE ){ //如果两边都没有到数组边界
            if(left[i]<right[j]){ //我们比较两个位置，将较小的放在数组的位置
                arr[k]=left[i];
                k++;i++;
            }
            else { 
                arr[k]=right[j];
                k++;j++;
            }
        }
        //出了上述循环，但是仍然存在可能有数组中的数没有放完的情况，我们直接按照顺序放入即可。
        while (i<LEFT_SIZE){ 
            arr[k]=left[i];
            k++;i++;
        }while (j<RIGHT_SIZE){ 
            arr[k]=right[j];
            k++;j++;
        }
    }
    public static  void mergeSort(int[] arr,int l,int r){ 
        if(l==r){ 
            return;
        }else { 
        int m=(l+r)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        Merge(arr,l,r,m+1);
        }
    }
    public static void main(String[] args) { 
       int[] arr = { 1, 4, 7, 10, 8, 3, 6, 5};
        int l = 0;
        int r =arr.length-1;
        mergeSort(arr, l, r);
        for (int i : arr) { 
            System.out.println(i);
        }
    }
}

成功！