首页 > 代码库 > 希尔排序算法的实现
希尔排序算法的实现
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
#include<iostream>using namespace std;void shellsort(int arr[],int n){ int i,j,gap,k,key; for(gap = n / 2;gap > 0;gap /= 2) { for(i = 0;i < gap;i ++) { for(j = i + gap;j < n;j += gap) { k = j; key = arr[k]; while(k - gap >= 0 && arr[k] < arr[k-gap]) { arr[k] = arr[k-gap]; k -= gap; } arr[k] = key; } } }}int main(){ int a[10] = {3,6,1,9,4,5,2,7,0,8}; shellsort(a,10); for(int i = 0;i < 10;i ++) cout<<a[i]<<" "; cout<<endl; return 0;} 运行结果截图：
希尔排序算法的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。