排序算法

冒泡排序

思想：两两比较，冒出一个值继续比较，最终把最小或则最大值放到末尾或开头，剩下的循环比较
优化可加一个布尔值，可以省略最后一轮比较

public static void BubbleSort1(int [] arr){

   int temp;//临时变量
   boolean flag;//是否交换的标志
   for(int i=0; i<arr.length-1; i++){   //表示趟数，一共 arr.length-1 次

       // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
       flag = false;
       
       for(int j=arr.length-1; j>i; j--){ //选出该趟排序的最大值往后移动

           if(arr[j] < arr[j-1]){
               temp = arr[j];
               arr[j] = arr[j-1];
               arr[j-1] = temp;
               flag = true;    //只要有发生了交换，flag就置为true
           }
       }
       // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
       if(!flag) break;
   }
}

选择排序

思想：选取第一个值跟其余值比较，选择一个最大或则最小值放到开头，依次循环

public static void select_sort(int array[],int lenth){

   for(int i=0;i<lenth-1;i++){

       int minIndex = i;
       for(int j=i+1;j<lenth;j++){
          if(array[j]<array[minIndex]){
              minIndex = j;
          }
       }
       if(minIndex != i){
           int temp = array[i];
           array[i] = array[minIndex];
           array[minIndex] = temp;
       }
   }
}

插入排序

思想：先选择前面两个值比较，把最小值放前面，相当于把前面两个值的大小排列好，用把第三个值拿来跟前面排序好的比较，放到自己合适的位置，依次循环

public static void  insert_sort(int array[],int lenth){

   int temp;

   for(int i=0;i<lenth-1;i++){
       for(int j=i+1;j>0;j--){
           if(array[j] < array[j-1]){
               temp = array[j-1];
               array[j-1] = array[j];
               array[j] = temp;
           }else{         //不需要交换
               break;
           }
       }
   }
}

希尔排序(对插入排序的优化)

思想：在插入排序的基础上，根据某一增量对数组分成子序列，分别进行插入排序，跟随增长越来越小，最后到1时，即完成排序

public static void shell_sort(int array[],int lenth){

   int temp = 0;
   int incre = lenth;

   while(true){
       incre = incre/2;

       for(int k = 0;k<incre;k++){    //根据增量分为若干子序列

           for(int i=k+incre;i<lenth;i+=incre){

               for(int j=i;j>k;j-=incre){
                   if(array[j]<array[j-incre]){
                       temp = array[j-incre];
                       array[j-incre] = array[j];
                       array[j] = temp;
                   }else{
                       break;
                   }
               }
           }
       }

       if(incre == 1){
           break;
       }
   }
}

快速排序

思想：先把数组中的数值拿出一个当作key，然后把剩下的数值拿出来跟key比较，大于等于的放一边，小的放另一边，然后对于分开的两个部分重复上一个操作，到最后区间只剩一位为止。
**辅助理解：[挖坑填数]
例：【70，25，60，90，45】从小到大排序，
i=0,j=4,key=70
把70拿来当key,a[0]的位置空了，
先从j位置开始往前找小于70的: 发现a[4]小于70，a[0]=a[4]，i++,j--,a[4]空出来
再从i位置往后找大于等于70的: 发现a[3]大于70，a[4]=a[3]，i++,j--,a[3]空出来
此时i=2,j=2,【45，25，60，空，90】
因为i=j=3，a[3]又是空的，那把70放到a[3],即【45，25，60，70，90】
再把70左边三个进行循环，【45，25，60】
i=0,j=2,key=45
a[0]=a[1].i++,j--,a【1】空，因为i=1=j,a[1]=45

public static void quickSort(int a[],int l,int r){
     if(l>=r)
       return;

     int i = l; int j = r; int key = a[l];//选择第一个数为key

     while(i<j){

         while(i<j && a[j]>=key)//从右向左找第一个小于key的值
             j--;
         if(i<j){
             a[i] = a[j];
             i++;
         }

         while(i<j && a[i]<key)//从左向右找第一个大于key的值
             i++;

         if(i<j){
             a[j] = a[i];
             j--;
         }
     }
     //i == j
     a[i] = key;
     quickSort(a, l, i-1);//递归调用
     quickSort(a, i+1, r);//递归调用
 }