排序算法之希尔排序
2023-09-11 14:14:10 时间
一、算法思想描写叙述
1、设置一定的步长
2、将整个序列根绝步长分成若干个子序列。对每一个子序列运行直接插入排序
3、反复步骤2,直到步长为1(包括1)
二、算法分析
希尔排序。也叫缩小增量排序。是插入排序的一种。他对插入排序进行了一定的优化。
时间复杂度:一般觉得。在某些序列中能够达到O(n^1.3)
空间复杂度:O(1)
稳定性:不稳定
排序过程分析例如以下:
三、实现
/* * shellsort.cpp * * Created on: 2014年5月18日 * Author: pc */ #include <iostream> using namespace std; const int maxn = 10; int arr[maxn]; /** * 希尔排序中的插入的逻辑部分 */ void shellinsert(int arr[],int d , int n){ int i; for(i = d ; i < n ; ++i){//循环遍历依据步长分成的组.(步长为n,就分成了n个组) int temp = arr[i];//保存当前位置的值 int j; for(j = i-d ; j>= 0 && arr[j] > temp ; j -= d){//寻找合适的位置.从后往前找,找到那个比当前位置的数小的位置 arr[j+d] = arr[j];//将找到的位置后面的书都往后移 } if(j != i-d){//假设找到了合适的位置 arr[j+d] = temp;//将当前位置的数放到合适的位置 } } } /** * 希尔排序 */ void shellsort(int arr[],int n){ int d = n/2;//设置初始步长 while(d>=1){ shellinsert(arr,d,n);//将整个序列划分成若干个子序列,对子序列运行插入排序 d /= 2;//不断地缩小步长 } } /** * 产生一个逆序的数组 */ void createReverseArr(){ int i = 0; for(i = 0 ; i < maxn ; ++i){ arr[i] = maxn - i; } } /** * 打印数组 */ void printArr(){ int i; for(i = 0 ; i < maxn ; ++i){ printf("%d " , arr[i]); } printf("\n"); } int main(){ createReverseArr(); printArr(); shellsort(arr,maxn); printArr(); }
相关文章
- 经典排序算法 - 插入排序&希尔排序
- 经典算法题每日演练——第二十二题 奇偶排序
- PHP 中四大经典排序算法
- 希尔排序算法
- 常用Java排序算法
- Java实现 蓝桥杯VIP 算法提高 数字黑洞
- 10大经典排序算法动图演示,看这篇就够了!(配相应代码)
- Python实现的寻找前5个默尼森数算法示例
- 数据结构和算法-排序算法-希尔排序
- 算法入门--快速排序
- (算法)位图BitMap
- (算法)格雷码
- 排序算法大数据量测试代码
- 【数据结构笔记20】数据结构之排序算法(十大排序算法、败者树、最佳归并树、置换-选择排序、最佳归并树)
- 【堆排序】十大排序算法之堆排序
- 【冒泡排序】十大排序算法之冒泡排序
- Algorithm:【Algorithm算法进阶之路】之十大经典排序算法
- python基础算法-归并排序
- m分别使用meanshift和camshift两种算法实现人员跟踪并输出人员移动曲线matlab仿真
- Python排序算法之插入排序
- 杂文 - [1.1]使用库语言排序算法
- 数据结构与算法——插入类排序(直接插入排序,希尔排序)
- C语言经典排序算法实现(一):double与int数据类型的冒泡排序
- 选哪扇门得奖金的算法
- 算法 翻转二叉树 dfs
- ES 搜索结果expalain 可以类似数据库性能调优来看排序算法的选择
- 冒泡、选择、插入、希尔、归并、快速排序、排序的稳定性、测试算法时间消耗
- 数据结构与算法之希尔排序