排序算法总结

冒泡排序(稳定)
冒泡排序的思想：冒泡排序的核心思想是数组内两个数来回比较，比如下面数组中先是第一个数与第二个数相比，即5和7比，5小于7则位置不变。然后再是第二个数字与第三个数字比即7和2比，7比2大，则7与2互换位置后继续，让第三个数与第四个数相比，即7和9比，7小于9则不做交换。就这样依次比较，总共比较arr.length-1次。第一次循环比较找出最大值在数组最后之后，然后再找出第二大的值，和之前的方法一样，但由于最后一位最大已知所以只需比较arr.length-1-i次。
代码如下

package suanfa;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by Enzo Cotter on 2020/6/20.
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr =new int[] {5, 7,2, 9, 4, 1, 0, 5, 7};
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    private static void bubbleSort(int[] arr){
        /*1.首先遍历整个数组*/
       for (int i=0;i<arr.length-1;i++){
           /*2.第一个数比第二个大，则交换位置，反之则保持不变，然后
           第二个数与第三个数比较，从此往复。
          */
           for (int j=0;j<arr.length-1-i;j++){
               /*相邻的两个数进行比较*/
               if (arr[j]>arr[j+1]){
                   int tmp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=tmp;
               }
           }
       }
    }
}

插入排序(稳定)
插入排序思想：
从数组的第二个数开始遍历如数列[5 3 4 7 1 2 8]从3开始遍历，
因为第一个数已经有序了。此时将遍历的第一个数与数组的第一个数相比，这里就是5和3进行比较，由于5比3大，所以就先复制一份3存起来，然后将5赋值给3对应的位置，再把存起来的3赋值给5的位置，其实就是互换位置，这时候数组变为[3 5 4 7 1 2 8]交换位置后这两个数就有序了，然后指针后移到4这个位置，此时4小于5，我们以同样的方式让4和5互换位置，然后再比较3和4，这时4大于3，已经有序无需做变换，我们发现此时数组变为[3 4 5 7 1 2 8],接下来指针后移发现7比5大，已经有序不做变换，指针直接+1，接下来是1明显小于7，将1存入，并将1的值用7替换，然后再比较之前7的前一个数字与存入的1的值若还是小于，则同理操作，直到出现大于或等于时，遍历结束，然后将等于或大于的指针的下一位赋值存入的数。
代码如下：

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,4,5,7,1,2,8};
        insertSort(arr);
        System.out.println(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];
               }
               //把临时变量（外层for循环的当前元素）赋值给不满足条件的后一个元素
              arr[j+1]=temp;
           }
       }
    }
}

快速排序(不稳定)
快速排序思想：假设这么一个数组需要快速排序int[] arr=new int[]{3, 5,2,4,6,8,2,7,0,9};
原理是先取数组中的第一个数为标准数standard,然后分别标注低位Low和高位high,假如高位high对应的值大于标准数standard,则将高位数位次减一，即high--,假如高位high对应的值小于标准值，则将此high对应的值赋值给low,当赋值完的low值小于标准数时，则让low++,当low++之后的low对应的值大于标准值时，则将此值赋值给high对应的值，由此遍历下去，遍历结束的标志是low值大于high值，即此时low值与high值重合，此时需要把标准值赋值给这个重合的位置。这样就实现在标准值的左边的数都小于标准值，在标准值右边的值都大于标准值。这样我们就将数组分为两部分，所以只需分别递归左边数列和右边数列，就可以实现快速排序了。
代码如下：

public class QuickSort(){
   public static void main(String[] args){
   int[] arr=new int[]{3, 5, 2, 4, 6, 8, 2, 7, 0, 9};
   quickSort(arr,0,arr.length-1);
   system.out.println(Arrays.toString(arr));
   }
   public static void quickSort(int[] arr,int start,int end){
    //递归结束的条件
    if(start<end){
    //设置标准数
   int stand=start;
   //设置低位和高位
    int low=start;
    int high=end;
    //当低位高于高位时循环结束
    while(low<high){
    //若标准数小于high对应的值，则令high++
        while(low<high&&stand<=arr[high]){
        high--;
        }
        //若标准数高于high对应的值，则将high的值赋给low
        arr[low]=arr[high];
        //赋完值后，如果标准值比赋值后的low对应的值大，则将low的位次加一
        while(low<high&&stand>=arr[low]){
        low++;
        }
        //当low对应的值大于标准值时，将此low对应的值赋值给high对应的值
        arr[high]=arr[low];
    }
    //while循环结束，表示此时low值与high值相同，此时将标准值赋值给low或者high对应的值。
    arr[low]=stand;
    //自此，数组被分为两部分，在标准值左边的数列的值都比标准值小，在标准值右边的数列的值都比标准值大，这样就实现了算法，接下来只需对左右两边的数列进行递归即可
    quickSort(arr,0,low);
    //数列右边递归
    quickSort(arr,low+1,end);
    }
   }
}

选择排序(不稳定)
选择排序思想：假设数组为int[] arr=new int[]{3, 5,2,4,6,8,2,7,0,9};，此时我们遍历数组找到最小的元素放在数组的第一个位置，然后再剩余还没有排序元素中继续寻找最小的元素放在第二个位置，以此类推从而使元素获得排序。
代码如下：
初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

import java.util.Arrays;

/**
 * Created by Enzo Cotter on 2020/8/14.
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr=new int[]{11,4,5,7,2,1,2,8,0};
        int[] newarr=selectSort(arr,arr.length);
        System.out.println(Arrays.toString(newarr));
    }
    private static int[] selectSort(int arr[],int length){
         //定义两个数分别作为无序数列中最小数所在的索引和作为有序数组的需替换的数的临时变量
        int minIndex,temp;
        //遍历数组，-1的原因是，遍历到最后已经知道了倒数前一个数列都是小于最后一个数的，所以无需再比较进入下一次循环
        for (int i=0;i<length-1;i++){
           设置有序数组的需替换的数的位置
            minIndex=i;
             //从第二个数开始遍历查看
            for (int j=i+1;j<length;j++){
                  如果遍历的数值小于要比较的数，则将j所在索引赋值给minIndex
                if (arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            //将在有序数组中需要替换的数存入临时变量temp;
            temp=arr[i];
            //内循环结束后已经知道了在无序数组中最小值所在的索引minIndex;
            arr[i]=arr[minIndex];
            此时已将无序数组中最小值赋给有序数组，之后再将有序数组中替换的值赋给原来无序数组中最小值所在的索引位置。
            arr[minIndex]=temp;
        }
        //外循环结束后即获得了有序数组。
        return arr;
    }
}