实现 Shell 排序的 C++ 程序

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

壳排序技术的复杂性

• 时间复杂度：O(n log n)对于最好的情况，对于其他情况，它取决于间隙序列。

• 空间复杂度：O(1)

Input − The unsorted list: 23 56 97 21 35 689 854 12 47 66
Output − 排序后的数组： 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) {        //交换 a 和 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) {        //初始间隙 = 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 << "输入元素数量： ";
   cin >> n;
   int arr[n];     //创建具有给定元素数量的数组
   cout << "输入元素：" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "排序前的数组： ";
   display(arr, n);
   shellSort(arr, n);
   cout << "排序后的数组： ";
   display(arr, n);
}

输入元素数量： 10
输入元素：
23 56 97 21 35 689 854 12 47 66
排序前的数组： 23 56 97 21 35 689 854 12 47 66
排序后的数组： 12 21 23 35 47 56 66 97 689 854