二分查詢排序

Harshit Jindal 2023年1月30日 2021年2月7日
  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 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