示例查找与排序算法

顺序查找(Sequential Search)

1. 遍历elements直至找到target或到elements结尾。
2. 找到target后，返回target在elements中的索引，找不到则返回-1。

/**
 * 在整数数组中寻找给定值。
 *
 * @param elements 待查找的数组。
 * @param target 待查找的元素。
 * @return 返回待查找元素的位置，找不到则返回-1。
 */
public static int sequentialSearch(int[] elements, int target) {
 for (int j = 0; j < elements.length; j++) {
  if (elements[j] == target) {
   return j;
  }
 }
 return -1;
}

折半查找(Binary Search)

1. 设left与right分别为elements索引的最小值与最大值。
2. 循环直至找到target，或确定target不在elements中：
   a. 设middle为elements[left]与elements[right]间的中点元素。
   b. 若target在elements[left]与elements[middle - 1]间，设right为middle - 1。
   c. 若target在elements[middle + 1]与elements[right]间，设left为middle + 1。
   d. 如target == elements[middle]，返回middle。
3. 如target不在elements中，返回-1。

/**
 * 在升序排列的整数数组中寻找给定值
 *
 * @param elements 待查找的数组。先决条件：数组中元素已按升序排列。
 * @param target 待查找的元素。
 * @return 返回待查找元素的位置，找不到则返回-1。
 */
public static int binarySearch(int[] elements, int target) {
 int left = 0;
 int right = elements.length - 1;
 while (left <= right) {
  int middle = (left + right) / 2;
  if (target < elements[middle]) {
   right = middle - 1;
  } else if (target > elements[middle]) {
   left = middle + 1;
  } else {
   return middle;
  }
 }
 return - 1;
}

选择排序(Selection Sort)

1. 在j = 0与j = elements.length - 2间循环elements.length - 1次。
2. 每次循环将位于索引j的元素与剩下数组的最小值交换位置。

/**
 * 让数组升序排列。
 *
 * @param elements 待排序的数组。后置条件：元素值不变，数组按升序排列。
 */
public static void selectionSort(int[] elements) {
 for (int j = 0; j < elements.length - 1; j++) {
  int minIndex = j;
  for (int k = j + 1; k < elements.length; k++) {
   if (elements[k] < elements[minIndex]) {
    minIndex = k;
   }
  }
  int temp = elements[j];
  elements[j] = elements[minIndex];
  elements[minIndex] = temp;
 }
}

插入排序(Insertion Sort)

1. 在j = 1与j = elements.length - 1间循环elements.length - 1次。
2. 每次循环将位于索引j的元素移至其在elements[0]与elements[j]间的恰当位置：
   a. 将位于索引j的元素移至temp，空出该位置。
   b. 递减possibleIndex，寻找temp的适当位置。
   c. 每次内侧循环，将空位往索引递减的方向移一位。
3. 将temp复制到位于possibleIndex的恰当位置。

/**
 * 让数组升序排列。
 *
 * @param elements 待排序的数组。后置条件：元素值不变，数组按升序排列。
 */
public static void insertionSort(int[] elements) {
 for (int j = 1; j < elements.length; j++) {
  int temp = elements[j];
  int possibleIndex = j;
  while (possibleIndex > 0 && temp < elements[possibleIndex - 1]) {
   elements[possibleIndex] = elements[possibleIndex - 1];
   possibleIndex--;
  }
  elements[possibleIndex] = temp;
 }
}

归并排序(Merge Sort)

mergeSort

建立供排序用的临时数组，调用mergeSortHelper。

mergeSortHelper

1. 若elements[from]与elements[to]之间有多余一个元素：
   a. 将元素分为两部分。
   b. 递归调用mergeSortHelper将各部分排序。
   c. 调用merge合并排序结果。
2. 若仅有一个元素，退出。

merge

1. 只要两个数组部分还有至少一项未被复制，比较两部分未被复制的第一项，将较小者复制到temp的下一个位置。
2. 复制第一部分的剩余项到temp。
3. 复制第二部分的剩余项到temp。
4. 复制temp[from]到temp[to]的范围到elements的对应位置。

/**
 * 让数组升序排列。
 *
 * @param elements 待排序的数组。后置条件：元素值不变，数组按升序排列。
 */
public static void mergeSort(int[] elements) {
  int n = elements.length;
  int[] temp = new int[n];
  mergeSortHelper(elements, 0, n - 1, temp);

 }
/**
 * 让elements[from] ... elements[to]升序排列。
 *
 * @param elements 待排序的数组。
 * @param from 起始索引。
 * @param to 终止索引。
 * @param temp 排序过程中用到的临时数组。
 *
 * 先决条件：
 *    (elements.length == 0 或
 *     0 <= from <= to <= elements.length) 与
 *    elements.length == temp.length
 * 后置条件：元素值不变，elements[from] ... <= elements[to]按升序排列。
 */
private static void mergeSortHelper(int[] elements, int from, int to, int[] temp) {
  if (from < to) {
   int middle = (from + to) / 2;
   mergeSortHelper(elements, from, middle, temp);
   mergeSortHelper(elements, middle + 1, to, temp);
   merge(elements, from, middle, to, temp);
  }
 }
/**
 * 将两个升序排列的数组部分合并成一个升序排列的数组部分。
 *
 * @param elements 待合并的数组。
 * @param from 第一部分起始索引。
 * @param mid 第一部分终止索引。
 *       mid+1 第二部分起始索引。
 * @param to 第二部分终止索引。
 * @param temp 排序过程中用到的临时数组。
 *
 * 先决条件：0 <= from <= mid <= to <= elements.length 与
 *   elements[from] ...<= elements[mid]按升序排列 与
 *   elements[mid + 1] ...<= elements[to]按升序排列 与
 *   elements.length == temp.length
 * 后置条件：元素值不变 与
 *   elements[from] ...<= elements[to]按升序排列 与
 *   elements[0] ... elements[from - 1]顺序不变 与
 *   elements[to + 1] ... elements[elements.length - 1]顺序不变 与
 */
private static void merge(int[] elements, int from, int mid, int to, int[] temp) {
 int i = from;
 int j = mid + 1;
 int k = from;
 while (i <= mid && j <= to) {
  if (elements[i] < elements[j]) {
   temp[k] = elements[i];
   i++;
  } else {
   temp[k] = elements[j];
   j++;
  }
  k++;
 }
 while (i <= mid) {
  temp[k] = elements[i];
  i++;
  k++;
 }
 while (j <= to) {
  temp[k] = elements[j];
  j++;
  k++;
 }
 for (k = from; k <= to; k++) {
  elements[k] = temp[k];
 }
}