希尔排序算法原理及具体实例分析是怎样的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计759个文字，预计阅读时间需要4分钟。
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;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
本文共计759个文字，预计阅读时间需要4分钟。
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;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！