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