Shell 排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. Shell 排序算法
  2. Shell 排序示例
  3. Shell 排序算法实现
  4. Shell 排序算法的复杂度
Shell 排序
注意
如果你不知道什么是插入排序,那么请先去看插入排序一文。

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

Shell 的原始序列 N/2,N/4,...,1
Papernov & Stasevich 增量 1, 3, 5, 9,...
Hibbard 的增量 1, 3, 7, 15, 31, 63,...
Knuth 的增量 1, 4, 13, ... , (3k – 1) / 2
Pratt 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, ....
Sedgewick 的增量 1, 8, 23, 77, 281, ... 4j+1+ 3-2j+ 1

Shell 排序算法

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

  • 按照序列计算 gap 的值。
  • 对每一个间隔等于 gap 的子数组进行如下操作。
  • 用插入排序法进行排序。
  • 重复上述过程,直到整个数组被排序。

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)2)。

  • 最坏情况

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

  • 最佳情况

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

空间复杂度

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

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