C++ 算法之希尔排序详解及实例

概述C++算法之希尔排序算法详解及实例希尔排序算法定义：         希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

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++ 算法之希尔排序详解及实例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。