面试常见算法排序查找算法

算法是程序员必被的一个技能，在面试中常常出现，下面总结了面试中出现的常见算法，这些算法程序员应该牢记在心中，要非常熟练。

插入排序算法

原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。

要点：设立哨兵，作为临时存储和判断数组边界之用。

public class InsertSort {
private static void insertSort(int[] a) {
int j;
int tmp;
for (int i = 1; i tmp = a[i];
for (j = i; j > 0 && tmp a[j] = a[j - 1];
}
a[j] = tmp;
}
}
}

希尔排序算法

原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。

要点：增量的选择以及排序最终以1为增量进行排序结束。

public class ShellSort {
private static void shellSort(int[] a) {
int j;
int tmp;
for (int gap = a.length / 2; gap >0; gap /= 2) {
for (int i = gap; i tmp = a[i];
for (j = i; j >= gap && tmp a[j] = a[j - gap];
}
a[j] = tmp;
}
}
}
}

冒泡排序算法

原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。

要点：设计交换判断条件，提前结束以排好序的序列循环。

public class BubbleSort {
private static void bubbleSort(int[] a) {
for (int i = 0; i for (int j = 0; j if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
private static void swap(int[] a, int x, int y) {
int tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}
}

快速排序算法

原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。

要点：递归、分治

public class QuickSort {
private static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private static void quickSort(int[] a, int left, int right) {
if (left int pivot = a[left];
int lo = left;
int hi = right;
while (lo while (lo = pivot) {
hi--;
}
a[lo] = a[hi];
while (lo lo++;
}
a[hi] = a[lo];
}
a[lo] = pivot;
quickSort(a, left, lo - 1);
quickSort(a, lo + 1, right);
}
}
}

简单选择排序算法

原理：将序列划分为无序和有序区，寻找无序区中的最小&＃20540;和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序

public class SelectSort {
private static void selectSort(int[] a) {
int idx;
for (int i = 0; i idx = i;
for (int j = i + 1; j if (a[idx] > a[j]) {
idx = j;
}
}
swap(a, idx, i);
}
}
private static void swap(int[] a, int x, int y) {
int tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}
}

堆排序算法

原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首与堆尾交换，堆尾之后为有序区。

要点：建堆、交换、调整堆

public class HeapSort {
private static void heapSort(int[] a) {
// 先创建大堆，从第一个非叶子结点开始调整，然后调整第二个非叶子结点...
for (int i = a.length / 2; i >= 0 ; i--) {
shiftDown(a, i, a.length);
}
// 调整大堆，将最大的元素调整到未排好序的部分的末尾
for (int i = a.length - 1; i > 0 ; i--) {
swap(a, 0, i);
shiftDown(a, 0, i);
}
}
private static void shiftDown(int[] a, int i, int n) {
int child;
int tmp;
for (tmp = a[i]; i * 2 + 1 child = i * 2 + 1;
if (child != n - 1 && a[child] child++;
}
if (tmp a[i] = a[child];
} else {
break;
}
}
a[i] = tmp;
}
private static void swap(int[] a, int x, int y) {
int tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}
}

归并排序算法

原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。

要点：归并、分治

public class MergeSort {
private static void mergeSort(int[] a) {
int[] b = new int[a.length];
mergeSort(a, b, 0, a.length - 1);
}
private static void mergeSort(int[] a, int[] b, int left, int right) {
if (left int center = left + (right - left) / 2;
mergeSort(a, b, left, center);
mergeSort(a, b, center + 1, right);
merge(a, b, left, center + 1, right);
}
}
private static void merge(int[] a, int[] b, int leftPos, int rightPos, intrightEnd) {
int leftEnd = rightPos - 1;
int tempPos = leftPos;
int numElements = rightEnd - leftPos + 1;
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos] <= a[rightPos]) {
b[tempPos] = a[leftPos];
tempPos++;
leftPos++;
} else {
b[tempPos] = a[rightPos];
tempPos++;
rightPos++;
}
}
while (leftPos <= leftEnd) {
b[tempPos] = a[leftPos];
tempPos++;
leftPos++;
}
while (rightPos <= rightEnd) {
b[tempPos] = a[rightPos];
tempPos++;
rightPos++;
}
for (int i = 0; i a[rightEnd] = b[rightEnd];
}
}
}

二分查找算法

public class BinarySearch {
public static int binarySearch(int[] a, int v) {
int mid;
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
mid = lo + ((hi - lo) >>> 1); // 移位运算的优先级比较低，要用括号
if (a[mid] == v) { // 已经找到
return mid;
} else if (a[mid] lo = mid + 1;
} else { // 可能在左边
hi = mid - 1;
}
}
return -1; // 未找到
}
}