多种排序算法的思路和简单代码的实现（一）

kingbosster

　　就自己简单的理解了一些排序算法（JAVA）思路和代码分享给大家：欢迎大家进行交流。
　　直接插入排序，折半插入排序，冒泡排序，快速排序



public class Sort {
     /*
      * 直接插入排序： 先确定一个有序数组，然后把插入的数与有序数组从最后依次进行比较， 直到插入的数比有序数组的数大，此数换为插入的数字，从此位置以后
      * 的数依次向后移动一位。
      */
     public static void insert(int[] a) {
         for (int i = 1; i < a.length; i++) {
             int b = a, j;
             for (j = i - 1; j >= 0 && b < a[j]; j--) {
                 a[j + 1] = a[j];
             }
             a[j + 1] = b;

         }
     }

     /*
      * 折半插入排序法： 对有序数组确定最小下标，最大下标， 然后将插入的值与中间值进行比较，
      * 如果小于中间值，则最大下标为中间下标-1，否则最小下标为中间下标+1; 循环确定插入位置为最小下标，然后把插入的数字赋值给最小下标对应
      * 的数，后面的数依次往后移动一位。
      */
     public static void halfInsert(int[] a) {
         for (int i = 1; i < a.length; i++) {
             int b = a, low = 0, high = i - 1;
             while (low <= high) {
                 int mid = (low + high) / 2;
                 if (b > a[mid]) {
                     low = mid + 1;
                 } else {
                     high = mid - 1;
                 }
             }
              //此时，high+1=low
             for (int j = i; j >=low+1; j--) {//注意；这个循环是把下标为low到i-1的所有数向后移动一位。
                 a[j] = a[j-1];
             }
             a[low] = b;
         }

     }

     /*
      * 冒泡排序： 双重循环，最多进行n-1趟排序，每相邻两个数进行比较，如果前面的大，则进行交换，
      * 用exchange判断两数是否变换了，如果没有变换，则不必再进行上述步骤进行排序，直接输出结果。
      */
     public static void bubblseSort(int[] a) {
         boolean exchange = true;// 是否交换的标志
         for (int i = 1; i < a.length && exchange; i++) {
             exchange = false;
             for (int j = 0; j < a.length - 1; j++) {
                 if (a[j + 1] < a[j]) {
                     int b = a[j + 1];
                     a[j + 1] = a[j];
                     a[j] = b;
                     exchange = true;
                 }
             }

         }
     }
/*
  * 快速排序算法：
  * 找第一个数做基准量，从后往前找，比基准量大的数放到后边，小的就把数往前移动，
  * 从前往后找，比基准量小的放到前面，大的就往后移动，
  * 循环执行上述步骤，直到前后端序列都变为1个数为止，用递归算法实现。
  */
     public static void quickSort(int[] a, int b, int e) {
         int i = b, j = e, x = a;
         while (i < j) {
             while (i < j && x < a[j])
                 j--;
             if (i < j)
                 a[i++] = a[j]; // 后端小的数向前移动
             while (i < j && x > a)
                 i++;
             if (i < j)
                 a[j--] = a; // 前端大的数向后移动
         }
         ;
         // 此时，i=j;
         a = x;
         if (b < i)
             quickSort(a, b, i - 1);
         if (i < e)
             quickSort(a, i + 1, e);
     }
}