Shell 排序

1. Shell 排序算法
2. Shell 排序示例
3. Shell 排序算法实现
4. Shell 排序算法的复杂度

Shell 排序是一种高效的基于比较的排序算法。它被看作是冒泡排序算法的泛化，或者说是一种优化的插入排序算法。在插入排序算法中，我们将元素向前移动一个位置。但在 shell 排序的情况下，我们将元素 h 位置前移。它先对很远的元素进行排序，然后根据序列逐步缩小差距，对整个数组进行排序。使用的一些序列是：

Shell 排序算法

假设我们有一个未排序的数组 A[]，包含 n 元素。我们将使用 shell 的原始序列对数组进行排序。

Shell 排序示例

假设我们有一个数组：(9, 8, 3, 7, 5, 6, 4, 1)。我们将使用 shell 排序算法对其进行排序，并使用 shell 的原始序列来减少间隙间隔。

• 第一次迭代

n/2=4，位于区间 4 的元素进行比较和交换。

A[0] > A[4] →交换，(5,8,3,7,9,6,4,1)。

A[1] > A[5] →交换，(5,6,3,7,9,8,4,1)。

A[2] < A[6]。

A[3] > A[7] →交换，(5,6,3,1,9,8,4,7)。

数组变成：(5,6,3,1,9,8,4,7)。

• 第二次迭代

n/4=2，位于区间 2 的元素进行比较和交换。

A[0] > A[2] →交换，(3,6,5,1,9,8,4,7)。

A[1] > A[3] →交换，(3,1,5,6,9,8,4,7)。

A[0] < A[2] < A[4]。

A[1] < A[3] < A[5]。

A[2]>A[4] 和 A[4]>A[6]→交换，(3,1,4,6,5,8,9,7)。

A[1]<A[3]<A[5]，但 A[5]>A[7]→互换，(3,1,4,6,5,7,9,8)。

数组变成：(3,1,4,6,5,7,9,8)。

• 第三次迭代

n/8=1 , 位于区间 1 的元素进行比较和交换。

A[0] > A[1] →交换，(1,3,4,6,5,7,9,8)。

A[0] ... A[2]→排序

A[0] ... A[3] → 排序的。

A[0] ... A[3] → 排序，但 A[3] > A[4] →交换，(1,3,4,5,6,7,9,8)。

A[0] ... A[5] → 排序完毕

A[0] ... A[6] → 排序的。

A[0] ... A[6]→排序，但 A[6] > A[7] →交换，(1，3，4，5，6，7，8，9)。

Shell 排序算法实现

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Shell 排序算法的复杂度

时间复杂度

• 平均情况

复杂度取决于选择的排序序列。时间复杂度为 [Big Theta]：O(nlog(n)²)。

• 最坏情况

Shell 排序的最坏情况下时间复杂度总是小于等于 O(n²)。更准确的说根据 Poonen 定理，它由Θ(nlogn)²/(log log n)²)或Θ(nlog n)²/log log n)或Θ(n(log n)²)或介于两者之间。最坏情况下的时间复杂度是 [Big O]：<= O(n²)。

• 最佳情况

最好的情况是当数组已经排序，并且每个间隔所需的比较与数组的大小相同。最佳情况下的时间复杂度为 [Big Omega]：O(nlogn)。

空间复杂度

Shell 排序算法的空间复杂度为 O(n)，因为除了一个临时变量外，不需要额外的内存。