Shell 排序 Sort

外壳排序技术基于插入排序。在插入排序中，有时我们需要移动较大的块以将项目插入正确的位置。使用shell排序，我们可以避免大量的移位。排序以特定间隔完成。每次通过之后，间隔会减小以使间隔变小。

Shell Sort技术的复杂性

• 时间复杂度：最佳情况下的O（n log n），对于其他情况，它取决于间隔序列。

• 空间复杂度：O(1)

输入输出

Input:
The unsorted list: 23 56 97 21 35 689 854 12 47 66
Output:
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854

算法

shellSort(array, size)

输入- 数据数组，以及数组中的总数

输出-排序的数组

Begin
   for gap := size / 2, when gap > 0 and gap is updated with gap / 2 do
      for j:= gap to size– 1 do
         for k := j-gap to 0, decrease by gap value do
            if array[k+gap] >= array[k]
               break
            else
               swap array[k + gap] with array[k]
         done
      done
   done
End

示例

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { //swap the content of a and b
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void shellSort(int *arr, int n) {
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) {      //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else
               swapping(arr[k+gap], arr[k]);
         }
      }
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; //create an array with given number of elements
   cout << "输入元素：" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   shellSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

输出结果

Enter the number of elements: 10
输入元素：
23 56 97 21 35 689 854 12 47 66
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854