Java面试---排序算法总结

Java笔试一般会碰到排序或查找的问题，问题类型可能是直接问写出排序算法或以解决实际问题。但是万变不离其宗，只有理解了每个排序才能在实际中运用。

• 最重要的三个排序，也是经常问到的

  • 冒泡排序

  对要排序的数据，从上到下依次比较两个相邻的数并加以调整，将最大的数向下移动，较小的数向上冒起。即：每一趟依次比较相邻的两个数据元素，将较小的数放在左边，循环进行同样的操作，直到全部待排序的数据元素排完.

  第一趟排序

  第一趟排序

  第二趟排序

  第二趟排序

  第三趟。。。。

/**
* 冒泡排序bubble sort
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array == null || array.length == 0) {
throw new NullPointerException("array is not null");
}
for (int i = array.length - 1; i > 0; i--) {
//比较length-1趟
for (int j = 0; j < i; j++) {
//比较相邻数字大小
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}

  - 选择排序
  
  > 每次循环找出最小数然后依次排序。第一次循环找到最小数，第二次循环找到第二小数，第三次循环找到第三小数。。。。
  
  ```
  /**
   * 选择排序
   *
   * @param array
   * @return
   */
  public static int[] selectSort(int[] array) {
      if (array == null || array.length == 0) {
          throw new NullPointerException("array is not null");
      }
      for (int i = 0, length = array.length; i < length - 1; i++) {
          for (int j = i + 1; j < length; j++) {
              if (array[i] > array[j]) {
                  int temp = array[i];
                  array[i] = array[j];
                  array[j] = temp;
              }
          }
      }
      return array;
  }
  ```
  - 插入排序
  
  > 每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
  
  ```
  /**
   * 插入排序
   *
   * @param array
   * @return
   */
  public static int[] insertSort(int[] array) {
      if (array == null || array.length == 0) {
          throw new NullPointerException("array is not null");
      }
      for (int i = 1; i < array.length; i++) {
          int temp = array[i];
          int j;
          for (j = i - 1; j >= 0; j--) {
              if (temp < array[j]) {
                  array[j + 1] = array[j];
              }
          }
          array[j + 1] = temp;
      }
      return array;
  }
  ```
- 其他排序
  - [归并排序](https://github.com/anAngryAnt/LearningNotes/blob/master/Part3/Algorithm/Sort/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.md)
  - [堆排序](http://www.cnblogs.com/0201zcr/p/4764705.html)
  - [希尔排序](http://www.cnblogs.com/0201zcr/p/4764427.html)
  - [快速排序](http://www.jianshu.com/p/8c915179fd02)
  - [基数排序](http://www.cnblogs.com/developerY/p/3172379.html)
![排序复杂度](http:https://img.haomeiwen.com/i1534431/5711df0aadfb32e7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
- 经常用到查找方法
  - [折半查找](https://github.com/GeniusVJR/LearningNotes/blob/master/Part3/Algorithm/Lookup/%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE.md)
  
  > 折半查找，要求数据源是一个有序的
  
  ```
    /**
   * half search key
   *
   * @param array     must is sequence array
   * @param searchKey
   * @return
   */
  public static int halfSearch(int[] array, int searchKey) {
      int low = 0;
      int high = array.length - 1;
      while (low <= high) {
          int middle = (high + low) / 2;
          if (array[middle] == searchKey) {
              return middle;
          } else if (array[middle] > searchKey) {
              high = middle;
          } else {
              low = middle;
          }
      }
      return -1;
  }
  ```
  
  - [排序查找](https://github.com/GeniusVJR/LearningNotes/blob/master/Part3/Algorithm/Lookup/%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE.md)
  
  > 按从头到尾的查找
  
  ```
  /**
   * sequence search key
   *
   * @param array     
   * @param searchKey
   * @return
   */
  public static int sequenceSearch(int[] array, int searchKey) {
      for (int i = 0, length = array.length; i < length; i++) {
          if (array[i] == searchKey) {
              return i;
          }
      }
      return -1;
  }
  ```
-  参考资料
- [常用排序算法稳定性、时间复杂度分析（转，有改动）](http://www.cnblogs.com/nannanITeye/archive/2013/04/11/3013737.html)