二分查詢排序

1. 二分查詢排序演算法
2. 二分查詢排序示例
3. 二分查詢排序演算法的實現
4. 二分查詢排序演算法的複雜度

二分查詢排序是一種比較型排序演算法。它是插入排序演算法的修改版。在這個演算法中，我們同樣維護了一個已排序和一個未排序的子陣列。唯一不同的是，我們使用二進位制查詢而不是線性搜尋來尋找元素的正確位置。它通過減少所需的比較次數來幫助快速排序演算法。

二分查詢排序演算法

假設我們有一個未排序的陣列 A[]，包含 n 個元素。第一個元素，A[0]，已經被排序並在排序子陣列中。

二分查詢排序示例

假設我們有一個陣列：(5,3,4,2,1,6). 我們將使用插入排序演算法對其進行排序。

• 第一次迭代

鍵：A[1]=3。

二進位制查詢：將 3 的位置作為索引 0 返回。右移排序陣列中的其餘元素。

• 第二次迭代

鍵：A[2]=4。

二進位制查詢：返回 4 的位置作為索引 1。右移排序陣列中的其餘元素。

• 第三次迭代

鍵：A[3]=2。

二進位制查詢：將 2 的位置作為索引 0 返回。對排序陣列中其餘元素進行右移。

• 第四次迭代

鍵：A[4]=1。

二進位制查詢：將 1 的位置作為索引 0 返回。右移排序陣列中的其餘元素。

• 第五次迭代

鍵：A[5]=6。

二進位制查詢：將 6 的位置返回為索引 5。右邊沒有元素。

我們在第四次迭代後得到排序陣列–(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)，因為除了一個臨時變數外，不需要額外的記憶體。