顺序查找(Sequential Search)

  1. 遍历elements直至找到target或到elements结尾。
  2. 找到target后,返回targetelements中的索引,找不到则返回-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. leftright分别为elements索引的最小值与最大值。
  2. 循环直至找到target,或确定target不在elements中:
    a. 设middleelements[left]elements[right]间的中点元素。
    b. 若targetelements[left]elements[middle - 1]间,设rightmiddle - 1
    c. 若targetelements[middle + 1]elements[right]间,设leftmiddle + 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 = 0j = 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 = 1j = 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];
 }
}

陈 欣

AADPS创始人

发表评论