温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++ 中怎么实现希尔排序

发布时间:2021-08-12 15:15:40 来源:亿速云 阅读:134 作者:Leah 栏目:编程语言

这篇文章给大家介绍C++ 中怎么实现希尔排序,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

希尔排序算法

定义:

          希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。

算法思想:

          希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止。  

时间复杂度:

         O(N)

空间复杂度:

         O(1)

性能:

         希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的插入排序中移动,会打乱其稳定性)

优势:

        希尔排序不需要大量的辅助空间,比直接插入排序时间要快,并且代码很好实现。

缺点:

        虽然希尔排序相对于直接插入排序要优化很多,但是O(N)的算法依旧效率不是很高,并且希尔排序不稳定。

代码实现:

#include <iostream> 
#include <Windows.h> 
#include <assert.h> 
 
using namespace std; 
 
//希尔排序,从小到大排 
void ShellSort(int* arr, int len)  
{ 
  assert(arr); 
  int gap = 3;   //先给一个初始组间距,gap为1时即为直接插入排序 
  for (gap = 3; gap > 0; --gap)  //不断缩小组间距,直到gap=1 
  { 
    for (int i = 0; i < len; ++i)    
    { 
      for (int j = i + gap; j < len; j = j + gap) 
      { 
        if (arr[j-gap] > arr[j]) 
        { 
          int temp = arr[j];  //将arr[j]处的值先保存起来 
          arr[j] = arr[j-gap]; 
          arr[j-gap] = temp; 
        } 
      } 
    } 
  } 
}
#include "ShellSort.h" 
 
void TestShellSort() 
{ 
  int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 }; 
  int len = sizeof(arr) / sizeof(arr[0]); 
  cout << "未排序序列:" << ""; 
  for (int i = 0; i < len; ++i) 
  { 
    cout << arr[i] << "->"; 
  } 
  cout << endl; 
  ShellSort(arr, len); 
  cout << "已排序序列:" << ""; 
  for (int j = 0; j < len; ++j) 
  { 
    cout << arr[j] << "->"; 
  } 
  cout << endl; 
} 
 
int main() 
{ 
  TestShellSort(); 
  system("pause"); 
  return 0; 
}

C++ 中怎么实现希尔排序

关于C++ 中怎么实现希尔排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++
AI