常用排序算法

分类
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（基数排序）

直接插入排序（正序）

从数组arr第二位开始循环 用变量 value 记录当前循环的值，然后和数组中当前循环位置前面的每一个值去对比，如果大于当前循环值 value 就右移一位，直到数值小于当前循环值 value ，记录下小于循环值 value 的数值的索引加一值count，然后将变量 i 的值放到索引count的位置 循环结束 排序完成 一共循环两次。

简单理解：把最小值往前移

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

冒泡排序

从左边第一位开始循环到最后对比相邻的两个数值的大小，大的右移，小的左移，第一遍完成后，最后一位已经是最大值。第二遍还是从第一位开始循环，循环到length-1，以此类推，一直循环，直到第一位为最小值。

简单理解：把最大值往后移

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

3、快速排序

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
快速排序首先要选定一个基准值，然后有两个指针一起从头和尾切换扫描，对比指针上的值和基准值的大小，前部分扫描如果基准值小于指针值，则将lo位置的值和hi位置的值对换，然后切换到后半部分扫描，以此类推。

简单理解：找一个基准数，然后根据基准数的大小将数组分为大于基准数和小于基准数两个子数组进行排序，然后以此类推，直到所有的排好

public static void fastSort(int[] array){
       fastSort(array,0,array.length - 1);
}

public static void fastSort(int[] array,int lo,int hi) {
    if(lo>=hi){
        return ;
    }
    int index=sort1(array,lo,hi);
    fastSort(array,lo,index-1);
    fastSort(array,index+1,hi);
}

public static Integer sort1(int[] array, int lo, int hi) {
       int key=array[lo];
       while (lo < hi) {
              while (array[hi] >= key && hi > lo) {//从后半部分
                     hi--;
              }
              array[lo] = array[hi];
              while (array[lo] <= key && hi > lo) {//从前半部分
                     lo++;
              }
              array[hi] = array[lo];
       }
       array[hi]=key;
       return hi;
}