Java面试---排序算法总结
2017-03-29 本文已影响178人
WilsonMing
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)
- 经常用到查找方法
- [折半查找](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)
