首页 > 代码库 > 排序算法之希尔排序
排序算法之希尔排序
一、算法思想描述
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(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。