二分查找排序

Harshit Jindal 2023年10月12日
  1. 二分查找排序算法
  2. 二分查找排序示例
  3. 二分查找排序算法的实现
  4. 二分查找排序算法的复杂度
二分查找排序

二分查找排序是一种比较型排序算法。它是插入排序算法的修改版。在这个算法中,我们同样维护了一个已排序和一个未排序的子数组。唯一不同的是,我们使用二进制查找而不是线性搜索来寻找元素的正确位置。它通过减少所需的比较次数来帮助快速排序算法。

二分查找排序算法

假设我们有一个未排序的数组 A[],包含 n 个元素。第一个元素,A[0],已经被排序并在排序子数组中。

  • 将未排序子数组 A[1] 中的第一个元素标记为键。
  • 使用二进制查找找到排序子数组中 A[1] 的正确位置 p
  • p 的元素向右移动 1 步,并将 A[1] 插入其正确位置。
  • 对未排序子数组中的所有元素重复上述步骤。

二分查找排序示例

假设我们有一个数组:(5,3,4,2,1,6). 我们将使用插入排序算法对其进行排序。

排序后的子数组 未排序子数组 数组
( 5 ) ( 3, 4, 2, 1, 6) (5, 3, 4, 2, 1, 6)
  • 第一次迭代

键:A[1]=3。

二进制查找:将 3 的位置作为索引 0 返回。右移排序数组中的其余元素。

排序子数组 未排序子数组 数组
( 3 , 5) (4, 2, 1, 6) (3, 5, 4, 2, 1, 6)
  • 第二次迭代

键:A[2]=4。

二进制查找:返回 4 的位置作为索引 1。右移排序数组中的其余元素。

排序子数组 未排序子数组 数组
( 3, 4, 5) (2, 1, 6) (3, 4, 5, 2, 1,6)
  • 第三次迭代

键:A[3]=2。

二进制查找:将 2 的位置作为索引 0 返回。对排序数组中其余元素进行右移。

排序子数组 未排序子数组 数组
( 2, 3, 4, 5) (1, 6) (2, 3, 4, 5, 1,6)
  • 第四次迭代

键:A[4]=1。

二进制查找:将 1 的位置作为索引 0 返回。右移排序数组中的其余元素。

排序子数组 未排序子数组 数组
( 1, 2, 3, 4, 5) (6) (1, 2, 3, 4, 5, 6)
  • 第五次迭代

键:A[5]=6。

二进制查找:将 6 的位置返回为索引 5。右边没有元素。

排序子数组 未排序子数组 数组
( 1, 2, 3, 4, 5, 6) () (1, 2, 3, 4, 5, 6)

我们在第四次迭代后得到排序数组–(1 2 3 4 5 6)

二分查找排序算法的实现

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  binarySort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

二分查找排序算法的复杂度

时间复杂度

  • 平均情况

二进制查找与插入排序中使用的线性搜索的线性复杂度 n 相比,具有对数复杂度 logn。我们对 n 元素使用二分查找排序,使我们的时间复杂度 nlogn。因此,时间复杂度约为 [O Theta]:O(nlogn)

  • 最坏情况

最坏的情况发生在数组反向排序时,并且需要最大的移位次数。最坏情况下的时间复杂度是 [Big O]:O(nlogn)

  • 最佳情况

最好的情况是数组已经排序,不需要移动元素。最佳情况下的时间复杂度是 [Big Omega]:O(n)

空间复杂度

二分查找排序算法的空间复杂度为 O(1),因为除了一个临时变量外,不需要额外的内存。

作者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Sort Algorithm