[数据结构与算法]数据结构之查找和排序

查找

在数据集合中寻找满足某种条件的元素

顺序查找法

又称线性查找，主要用于在线性表中进行查找。算法主要思想是：

1. 设线性表中有$n$个元素，给定一个待查找的值$target$；
2. 从表的一端开始，顺序扫描，依次将扫描到的关键码和目标值$target$进行比较，直到当前扫描的关键码与$target$相等，则查找成功，并获取该关键码在表中的位置；
3. 整个表扫描结束后，没有发现与$target$相等的关键码，则查找失败。

代码实现

int SeqSearch(int List[], int size, int target) {
  //数组作为参数进行传递时，该参数退化为指针，数组长度信息丢失，在函数参数中增加一个参数size
  if (size == 0) return -1;

  //普通顺序表上的顺序查找
  for (int i = 0; i < size; i++) {
    if (List[i] == target)
      return i;
  }

  //监视哨
  //将目标值加入到数组的尾部，对于数组要重新分配内存空间
  int* newList = (int*)malloc(sizeof(int) * (size + 1));
  for (int i = 0; i < size; i++) {
    newList[i] = List[i];
  }

  newList[size] = target;
  int j = 0;
  while (List[j] != target) {
    j++;
  }
  free(newList);
  return j >= size ? -1 : j;

  //有序顺序表上的顺序查找
  int k = 0;
  while (List[k] < target) {
    k++;
  }//此时List[k]>=target

  if (List[k] == target)
    return k;
  else
    return -1;
}

优化

1. 在普通顺序表上使用监视哨，将目标值插入在数组的尾部，在查找过程中一定会找到一个与目标值相等的元素，如果该元素的位置不在最后一位，则查找成功，否则说明查找失败；
2. 在有序顺序表进行顺序查找，找到第一个不小于目标值的元素与目标值进行比较，若相等则查找成功，否则查找失败，后续元素不需要进行比较。

折半查找

又称二分查找、对分查找，算法主要思想如下：
??设有$n$个元素存放在一个有序的顺序表中，采用折半查找时，首先将位于查找区间正中位置的元素$nums[mid]$与目标值$target$进行比较：
????若$nums[mid]==target$则查找成功，并返回元素下标；
????若$nums[mid]<target$，则将查找区间缩小至数组的前半部分，再继续进行折半查找；
????若$nums[mid]>target$，则将查找区间缩小至数组的前半部分，再继续进行折半查找；
??每比较一次，查找区间缩小一半，在最坏的情况下，查找成功所需的关键码比较次数为$O(lo{g}_{2}n)$。

代码实现

//使用STL库中的vector来存储数组元素
int BinSearch(vector<int> &nums, int target) {
  if (nums.size() == 0)return -1;
  
  int left = 0, right = nums.size() - 1, mid;
  while (left <= right) {
    //获取查找区间中间位置
    mid = (left + right) / 2;

    if (nums[mid] == target)
      return mid;
    //不等时缩小查找区间
    if (nums[mid] < target)
      right = mid - 1;
    if (nums[mid] > target)
      left = mid + 1;
  }
  return -1;
}

分块查找

又称索引顺序查找，主要思想是将一个大的线性表分解成若干块，每块中的结点可以任意存放（无序排列），但块与块之间必须进行排序，即对于任意$i$，第$i$块中的所有结点的关键码都必须小于（或大于）第$i+1$块中的所有结点的关键码。

此外，还要建立一个索引表，把每块中的最大关键码作为索引表的关键码，按块的顺序存放在一个数组中，这个数组是按关键码排序的。

查找时，先在索引表中进行查找，确定目标结点所在的块，然后在相应的块中进行顺序查找，即可找到相应的结点。

查找小结

内部排序

直接插入排序

??把数组$a[n]$中待排序的$n$个元素看成一个有序表($a[0]$)和一个无序表($a[1],a[2],...,a[n?1]$)。排序过程中每次将无序表中的第一个元素插入有序表的适当位置，使之成为新的有序表，经过$n?1$次插入后，无序表中的元素全部插入到有序表中，原数组$a[n]$排序完成。

代码实现

void InsertSort(int List[], int size) {
  int temp;
  int i, j;
  //有序表(a[0],...,a[i-1])
  //无序表(a[i],...,a[size-1])
  for (i = 1; i < size; i++) {
    //当无序表中的第一个元素a[i]小于有序表的最后一个元素时才需要插入
    if (List[i] < List[i - 1]) {
      temp = List[i];
      //在有序表中查找相应位置
      for (j = i - 1; List[j] > temp && j >= 0; j--) {
        List[j + 1] = List[j];
      }
      List[j + 1] = temp;
    }
  }
}

时间复杂度$O(n^2)$，空间复杂度$O(1)$，稳定排序。

折半插入

与直接插入的思想相同，只是在查找插入位置时，选择折半查找法寻找待插入位置。

代码实现

void BinaryInsertSort(int List[], int size) {
  int tmp;
  int i, j, left, right, mid;
  //有序表(a[0],...,a[i-1])
  //无序表(a[i],...,a[size-1])
  for (i = 1; i < size; i++) {
    //当无序表中的第一个元素a[i]小于有序表的最后一个元素时才需要插入
    if (List[i] < List[i - 1]) {
      //进行折半查找
      tmp = List[i];
      left = 0;
      right = i - 1;
      while (left <= right) {
        mid = (left + right) / 2;
        if (tmp < List[mid])
          right = mid - 1;
        else
          left = mid + 1;
      }
      //将[left,i-1]的元素后移
      for (j = i - 1; j >= left; j--) {
        List[j + 1] = List[j];
      }
      List[left] = tmp;
    }
  }
}

时间复杂度$O(n^2)$，空间复杂度$O(1)$，稳定排序。

折半插入排序过程中的比较次数与待排序元素的初始序列无关，但是元素移动次数与待排序元素的初始位置有关。

希尔排序

又称缩小增量排序，排序思想为：

1. 设待排序元素序列有$n$个元素，首先取一个整数$gap<n$作为间隔，将全部元素分为$gap$个子序列；
2. 所有距离为$gap$的元素放入同一个子序列中，对每个子序列分别进行直接插入排序；
3. 然后缩小$gap$，重复上述子序列的划分和排序，直到$gap=1$，将所有元素放在同一序列中为止。

代码实现

//对距离为gap的元素进行直接插入排序
void InsertSort_gap(vector<int>& nums, int start, int gap) {
  int tmp;
  int i, j;
  for (i = start + gap; i < nums.size(); i = i + gap) {
    if (nums[i - gap] > nums[i]) {
      tmp = nums[i];
      j = i;
      do {
        nums[j] = nums[j - gap];
        j -= gap;
      } while (j - gap > 0 && nums[j - gap] > tmp);
      nums[j] = tmp;
    }
  }
}
//希尔排序
void ShellSort(vector<int>& nums) {
  int  start, gap = nums.size();
  while (gap != 1) {
    gap = ceil((double)gap / 2);
    for (start = 0; start < gap; start++) {
      InsertSort_gap(nums, start, gap);
    }
  }
}

时间复杂度介于$O(n)$和$O(n^2)$之间，空间复杂度$O(1)$，不稳定排序。

简单选择排序

又称直接选择排序，主要思想为：

1. 设待排序序列有$n$个元素；
2. 第一趟排序从待排序序列中选取关键码最小的元素，若该元素不位于第一个位置，则与待排序序列的第一个元素交换，并将其从待排序序列中删除；
3. 第一趟排序从剩下的待排序序列中选择关键码最小的元素，重复上述过程，通过$n?1$趟排序后得到有序序列。

代码实现

void SelectSort(vector<int>& nums) {
  int tmp;
  int i, j, k;
  //待排序序列(a[i],...,a[size-1])
  for (i = 0; i < nums.size(); i++) {
    k = i;
    //遍历待排序序列，记录最小值的位置下标
    for (j = i + 1; j < nums.size(); j++) {
      if (nums[j] < nums[k]) {
        k = j;
      }
    }
    //最小元素不在待排序序列的首位置，则进行交换
    if (k != i) {
      tmp = nums[i];
      nums[i] = nums[k];
      nums[k] = tmp;
    }
  }
}

时间复杂度$O(n^2)$，空间复杂度$O(1)$，不稳定排序。

锦标赛排序

按照锦标赛的思想进行排序，其算法思想如下：

1. 首先对$n$个元素的排序码进行两两比较，得到$?n/2?$个优胜者；
2. 对优胜者再进行两两比较，如此重复，直到选择具有最小的排序码元素为止。

堆排序

1. 将一个无序序列调整为一个大根堆（或是小根堆），找出这个序列的最大（或最小）值，移动到有序序列的末尾位置；
2. 对剩下的无序序列重复调整为一个大根堆（或是小根堆），重复以上过程，直到无序序列中没有元素。

冒泡排序

又称起泡排序，主要思想为：

1. 对待待排序元素序列从后向前，一次比较相邻元素的排序码，若发现存在逆序则交换，使排序码较小的元素逐渐从下标较大的位置移向下标较小的位置。
2. 一趟排序下来，排序码最小的元素就被交换到了待排序元素序列的第一个位置；
3. 下一趟排序时，已确定位置的元素不再参与排序；

优化

??在冒泡排序过程中，各元素不断接近自己的最终位置，如果一趟比较下来没有进行过交换操作，则说明待排序序列有序，因此可以设置一个标志，记录元素是否进行过交换，从而减少不必要的比较。

代码实现

void BubbleSort(vector<int>& nums) {
  int exchange;
  int i, j;
  int tmp;
  //i控制冒泡趟数
  for (i = 0; i <= nums.size() - 2; i++) {
    exchange = 0;
    //从尾部开始遍历，每完成一趟冒泡之后确定一个元素
    //前i个元素已经有序，仅需要在[i+1,size-1]中排序
    for (j = nums.size() - 1; j >= i + 1; j--) {
      //排序码小的元素放在前面
      if (nums[j - 1] > nums[j]) {
        tmp = nums[j - 1];
        nums[j - 1] = nums[j];
        nums[j] = tmp;
        exchange = 1;
      }
    }
    if (!exchange) return;
  }
}

时间复杂度$O(n^2)$，空间复杂度$O(1)$，稳定排序

快速排序

1. 任意取待排序元素序列中的某个元素作为基准元素，一般取第一个元素，按照基准元素的排序码大小，将整个待排序元素序列分为左右两个子序列：左子序列中所有元素的排序码都小于基准元素的排序码，右子序列中所有元素的排序码都大于基准元素的排序码，基准元素处于最终位置。
2. 分别对两个子序列重复上述方法各自划分成两个更小的子序列，直到最后划分出的子序列最多只有一个元素为止。

序列的划分方法

1. 将基准元素存入临时单元 $pivot$；
2. 设置指针i指向待排序元素序列的首元素（不包括基准元素）；
3. 从左向右进行扫描，凡是比基准元素的排序码小的元素都交换到左边；
4. 最后将基准元素放入最终位置，得到划分结果。

单指针实现

int Partition(vector<int>& nums, int low, int high) {
  //从左向右进行扫描，凡是比基准元素的排序码小的元素都交换到左边
  int tmp;
  int i, k = low;
  int pivot = nums[low];
  for (i = low + 1; i <= high; i++) {
    //k记录的是从low位置开始往右所遇到的第一个大于pivot的元素的前一个元素，该元素小于pivot
    if (nums[i] < pivot) {
      k++;  //遇到小于pivot的元素，K+1
      if (k != i) {
        //k!=i说明此时的nums[k]大于pivot，而nums[i]小于pivot
        //交换两者的值
        tmp = nums[i];
        nums[i] = nums[k];
        nums[k] = tmp;
      }
    }
  }
  //遍历结束后，nums[k]小于pivot,nums[k+1]大于pivot
  //pivot的位置为k，交换nums[k]和pivot
  nums[low] = nums[k];
  nums[k] = pivot;
  return k;
}
void QuickSort(vector<int>& nums, int left, int right) {
  if (left < right) {
    int pivotpos = Partition(nums, left, right);
    QuickSort(nums, left, pivotpos - 1);
    QuickSort(nums, pivotpos + 1, right);
  }
}

使用双指针实现

1. 将待排序序列第一个元素取出，作为基准元素，此时待排序序列第一个位置为空；
2. 设置尾部指针$right$往前遍历，找到一个排序码小于基准元素的元素，将该元素移动到待排序序列的第一个位置；
3. 设置头部指针$left$往后遍历，找到一个排序码大于基准元素的元素，将该元素移动到待排序序列中指针$right$指向的位置；
4. 重复2，3步骤，直到不满足$left<right$，$left$指向的位置即基准元素$pivot$的最终位置。

void QuickSort2(vector<int>& nums, int low, int high) {
  if (low < high) {
    int left = low, right = high, pivot = nums[left];
    while (left < right) {
      while (left <right && nums[right]>pivot) {
        right--;
      }
      if (left < right) {
        nums[left] = nums[right];
        left++;
      }
      while (left < right && nums[left] < pivot)
        left++;
      if (left < right) {
        nums[right] = nums[left];
        right--;
      }
    }
    nums[left] = pivot;
    QuickSort2(nums, low, left - 1);
    QuickSort2(nums, left + 1, high);
  }
}

时间复杂度$O(nlo{g}_{2}n)$，空间复杂度介于$O(lo{g}_{2}n)$和$O(1)$之间，不稳定排序

归并排序

将两个或两个以上的有序序列合并成一个新的有序序列。二路归并排序的算法思想如下：

1. 设初始序列含有$n$个元素，可看成$n$个有序的子序列；
2. 对$n$个有序序列两两合并，得到$?n/2?$个长度为2或1的有序序列；
3. 继续两两合并，直到得到一个长度为$n$的有序序列为止。

排序小结