Java实现面试常考的算法

 1//已经排好序的数组
 2public static int binarySearch(int[] nums, int key) {
 3    int start = 0;
 4    int end = nums.length - 1;
 5    int mid = -1;
 6    while (start <= end) {
 7        mid = (start + end) / 2;
 8        if (nums[mid] == key) {
 9            return mid;//已经查到返回！
10        } else if (nums[mid] > key) {
11            end = mid - 1;
12        } else if (nums[mid] < key) {
13            start = mid + 1;
14        }
15    }
16    return -1;
17}

1  //交换
2  private static void swap(int[] a, int i, int j) {
3      a[i] ^= a[j];
4      a[j] ^= a[i];
5      a[i] ^= a[j];
6  }

 1//插入排序
 2public static void insertSort(int[] a) {//a0为监视哨位置,不作为数据存储
 3    int len = a.length;
 4    for (int i = 2; i < len; i++) {
 5        if (a[i - 1] > a[i]) {
 6            a[0] = a[i];
 7            a[i] = a[i - 1];
 8            int j = 0;
 9            for (j = i - 2; a[j] > a[0]; j--) {
10                a[j + 1] = a[j];
11            }
12            a[j + 1] = a[0];
13        }
14    }
15}

 1//选择排序
 2 public static void selectSort(int[] a) {
 3     for (int i = 1; i < a.length; i++) {
 4         int j = selectMinKey(a, i); //从i开始a.length中找到最小的位置
 5         if (i != j) {
 6             swap(a, i, j);
 7         }
 8     }
 9 }
10
11 // 查找从i开始到a.length中最小的位置
12 private static int selectMinKey(int[] a, int i) {
13     int key = i;
14     for (int j = i + 1; j < a.length; j++) {
15         if (a[j] < a[key]) {
16             key = j;
17         }
18     }
19     return key;
20 }

 1 //冒泡排序
 2 public static void bubbleSort(int[] a) {
 3     int len = a.length;
 4     for (int i = 1; i < len - 1; i++) {
 5         for (int j = i; j < len - i; j++) {
 6             if (a[j + 1] < a[j]) {
 7                 swap(a, j + 1, j);
 8             }
 9         }
10     }
11 }

 1  //快速排序
 2  public static void quickSort(int[] a, int low, int high) {
 3      //递归快速排序
 4      int pivotLoc = 0;//中心点
 5      if (low < high) {
 6          pivotLoc = partitionLoc(a, low, high);
 7          quickSort(a, low, pivotLoc-1);
 8          quickSort(a, pivotLoc+1, high);
 9      }
10  }
11
12  //获取到a的下标 low ~ high 中, a[low]的应该放的位置, 即左边的数 < a[low] 右边的数 > a[low]
13  private static int partitionLoc(int[] a, int low, int high) {
14      a[0] = a[low];
15      while (low < high) {
16          while (low < high && a[high] >= a[0]) {
17              high--;
18          }
19          a[low] = a[high];
20          while (low < high && a[low] <= a[0]) {
21              low++;
22          }
23          a[high] = a[low];
24      }
25      a[low] = a[0];
26      return low;
27  }