开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之查找和排序 -> 正文阅读

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

查找

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

顺序查找法

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

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

代码实现

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;
}

优化

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

折半查找

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

代码实现

//使用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$ 块中的所有结点的关键码。

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

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

查找小结

查找方法	基本思想	时间复杂度
顺序查找/线性查找	从头开始依次遍历所有元素	$O (n)$
折半查找/二分查找	针对有序表，率先比较中间位置元素，进而缩小搜索空间	$O (l o g n)$
分块查找/索引顺序查找	块内无序、块间有序	$O (l o g (b + 1) + (s + 1) /2)$

内部排序

直接插入排序

??把数组 $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)$ ，稳定排序。

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

希尔排序

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

设待排序元素序列有 $n$ 个元素，首先取一个整数 $g a p < n$ 作为间隔，将全部元素分为 $g a p$ 个子序列；
所有距离为 $g a p$ 的元素放入同一个子序列中，对每个子序列分别进行直接插入排序；
然后缩小 $g a p$ ，重复上述子序列的划分和排序，直到 $g a p = 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)$ ，不稳定排序。

简单选择排序

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

设待排序序列有 $n$ 个元素；
第一趟排序从待排序序列中选取关键码最小的元素，若该元素不位于第一个位置，则与待排序序列的第一个元素交换，并将其从待排序序列中删除；
第一趟排序从剩下的待排序序列中选择关键码最小的元素，重复上述过程，通过 $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)$ ，不稳定排序。

锦标赛排序

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

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

堆排序

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

冒泡排序

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

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

优化

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

代码实现

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)$ ，稳定排序

快速排序

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

序列的划分方法

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

单指针实现

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);
  }
}

使用双指针实现

将待排序序列第一个元素取出，作为基准元素，此时待排序序列第一个位置为空；
设置尾部指针 $r i g h t$ 往前遍历，找到一个排序码小于基准元素的元素，将该元素移动到待排序序列的第一个位置；
设置头部指针 $l e f t$ 往后遍历，找到一个排序码大于基准元素的元素，将该元素移动到待排序序列中指针 $r i g h t$ 指向的位置；
重复2，3步骤，直到不满足 $l e f t < r i g h t$ ， $l e f t$ 指向的位置即基准元素 $p i v o t$ 的最终位置。

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(nlog_2n)$ ，空间复杂度介于 $O(log_2n)$ 和 $O (1)$ 之间，不稳定排序

归并排序

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

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

排序小结

排序方法	时间复杂度	空间复杂度	稳定性	适用性	性质
直接插入排序	$O(n^2)$	$O (1)$	稳定	顺序、链式存储	比较次数和移动次数均取决于待排序表的初始状态
折半插入排序	$O(n^2)$	$O (1)$	稳定	顺序存储	比较次数与初始状态无关，约O(nlogn)，移动次数与初始状态相关
希尔排序	$O (n)$ ～ $O(n^2)$	$O (1)$	不稳定	顺序存储
冒泡排序	$O(n^2)$	$O (1)$	稳定	顺序、链式存储	有序子序列是全局有序的，一趟排序定位一个元素
快速排序	$O(nlog_2n)$	$O(log_2n)$ ～ $O (1)$	不稳定	顺序存储	平均性能最优，运行时间与划分是否对称有关，一趟排序定位一个元素
简单选择排序	$O(n^2)$	$O (1)$	不稳定	顺序存储	比较次数与初始状态无关，n(n-1)/2
堆排序	$O(nlog_2n)$	$O (1)$	不稳定	顺序存储	一趟排序定位一个元素
归并排序	$O(nlog_2n)$	$O (n)$	稳定
基数排序	$O (d (n + r))$	$O (r)$	稳定		时间复杂度与初始状态无关，d为趟数，r为基数，n为元素个数