| 四种基础排序算法 | 您所在的位置：网站首页 › 四大排序算法 › 四种基础排序算法 |
四种基础排序算法
|
希尔排序归并排序
递归版本非递归版本 堆排序快速排序
希尔排序
希尔排序(ShellSort) 的思路有点奇特, 或许是书上表述的不清或许是我理解歪了, 真正了解希尔排序是怎样一种排序方法花了了差不多一个小时. 现在理解透了, 觉得真是很妙. 按照所规定的步长, 覆盖全部元素, 跳跃着进行插入排序, 暂时忽略中间的元素. 这也许就是希尔排序的内涵. 大概分为两个过程 根据所给数据设定步长. (我用的是n不断除2向下取整的策略, 这个策略不是最优的)对每个步长, 从开始到数据尾部进行跳跃式的插入排序. (每个元素都会参与)维基百科-希尔排序 演示 注意: 步长的最后一个一定是1, 也就是说, 最后进行的是一个完整的常规的插入排序, 但是因为前面所做的工作, 在这一步中, 所需的操作已经很少了. 这对理解希尔排序有一定帮助. 算法的复杂度在O(n^2)和O(nlog₂n)之间. 占用空间大概就是存储序列的空间+1. C++代码 #include using namespace std; const int maxn = 1005; int n; void ShellInsert(int *arr, int dk) { for (int i = dk + 1; i 0 && arr[0] < arr[j]; j -= dk) { arr[j + dk] = arr[j]; } arr[j + dk] = arr[0]; } } void ShellSort(int *arr, int *dlta, int size) { for (int i = 0; i < size; ++i) { ShellInsert(arr, dlta[i]); cout |
【本文地址】
公司简介
联系我们