排序算法

/**
 * 冒泡排序
 * @param arr int[]
 * @return int[]
 */
public static int[] bubbleSort(int[] arr) {
   //连续相邻两个数比较后面的数比前面的数小就交换位置
   for (int i = 0; i < arr.length; i++) {
      for (int j = 0; j < arr.length-1-i; j++) {
         if (arr[j+1] < arr[j]) {
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }

   }
   return arr;
}

/**
 * 选择排序
 *
 * @param arr int[]
 * @return int[]
 */
public static int[] chooseSort(int[] arr) {
   //假设第一个为最小的，在后面只要找出最小的和他交换位置，即:找到一个比他小就交换
   for (int i = 0; i < arr.length - 1; i++) {
      for (int j = i + 1; j < arr.length; j++) {
         if (arr[i] > arr[j]) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
      }
   }
   return arr;
}

/**
 * 快速排序
 *
 * @param arr int[]
 * @param start int
 * @param end int
 * @return int[]
 */
public static int[] quickSort(int[] arr, int start, int end) {
   //判断数组元素是否只有一个
   if (start < end) {
      int temp = arr[start];
      int i = start;
      int j = end;
      //一次快速排序
      while (i < j) {
         //从右边找出一个比temp小的数
         while (i < j && arr[j] > temp) {
            j--;
         }
         //把右边比temp小的数交换到前面去
         arr[i] = arr[j];
         //再从交换过后的数右边开始找比temp大的数
         while (i < j && arr[i] <= temp) {
            i++;
         }
         //把左边比temp大的数交换后面去
         arr[j] = arr[i];
      }
      //最后第一次快速排序结束,确定temp位置
      arr[i] = temp;
      //利用递归排序temp左边的数
      quickSort(arr, start, i - 1);
      //利用递归排序temp右边的数
      quickSort(arr, i + 1, end);
   } else {//如果只有一个就只返回一个
      return arr;
   }
   return arr;
}

/**
 * 插入排序
 *
 * @param arr int[]
 * @param length int
 * @return int[]
 */
public static int[] insertSort(int[] arr, int length) {
   //简单点说:假设第一个数已经排好了，从第二个数开始，让他和之前的比较，把它放在一个合适位置，
   //即:放在一个前面比temp小，后面比temp大的位置
   int temp, i, j;
   for (i = 1; i < length; i++) {
      temp = arr[i];
      //发现前面的数比temp大，交换到后面去，最后把temp值放到j的位置,也就是空出来的位置
      for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
         arr[j + 1] = arr[j];
      }
      arr[j + 1] = temp;
   }
   return arr;
}

/**
 * 希尔排序
 *
 * @param arr int[]
 * @return int[]
 */
public static int[] shellSort(int[] arr) {
   //增量每次都/2
   for (int step = arr.length / 2; step > 0; step /= 2) {
      //从增量那组开始进行插入排序，直至完毕
      for (int i = step; i < arr.length; i++) {

         int j = i;
         int temp = arr[j];

         // j - step 就是代表与它同组隔壁的元素
         while (j - step >= 0 && arr[j - step] > temp) {
            arr[j] = arr[j - step];
            j = j - step;
         }
         arr[j] = temp;
      }
   }
   return arr;
}

/**
 * 折半查找
 * @param arr int
 * @param value int
 * @return int
 */
public static int binarySearch(int[] arr,int value) {
      //左孩
      int low = 0;
      int len = arr.length;
      //右孩
      int high = len - 1;

      while (low <= high) {
         int mid = (low + high) / 2;
         if (arr[mid] == value)
            return mid;
         else if (arr[mid] < value)
            low = mid + 1;
         else
            high = mid - 1;
      }
      return -1;

}