实现 Shell 排序的 C++ 程序

2023-06-20 13:22:04 175

壳排序技术的复杂性

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

空间复杂度：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
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 0; gap = gap / 2) {        //初始间隙=n/2，
      decreasing by gap /2
      for(j = gap; j=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> 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

实现 Shell 排序的 C++ 程序

壳排序技术的复杂性

算法

shellSort(array,size)

示例代码

热门推荐

随机推荐