说明
插入排序法由未排序的后半部前端取出一个值,插入已排序前半部的适当位置,概念简单但速度不快。
排序要加快的基本原则之一,是让后一次的排序进行时,尽量利用前一次排序后的结果,以加
快排序的速度,Shell排序法即是基于此一概念来改良插入排序法。
解法
Shell排序法最初是D.LShell于1959所提出,假设要排序的元素有n个,则每次进行插入排序时
并不是所有的元素同时进行时,而是取一段间隔。
Shell首先将间隔设定为n/2,然后跳跃进行插入排序,再来将间隔n/4,跳跃进行排序动作,再来
间隔设定为n/8、n/16,直到间隔为1之后的最 后一次排序终止,由于上一次的排序动作都会将
固定间隔内的元素排序好,所以当间隔越来越小时,某些元素位于正确位置的机率越高,因此
最后几次的排序动作将 可以大幅减低。
举个例子来说,假设有一未排序的数字如右:89 12 65 97 61 81 27 2 61 98
数字的总数共有10个,所以第一次我们将间隔设定为10 / 2 = 5,此时我们对间隔为5的数字进行
排序,如下所示:
画线连结的部份表示 要一起进行排序的部份,再来将间隔设定为5 / 2的商,也就是2,则第二
次的插入排序对象如下所示:
再来间隔设定为2 / 2 = 1,此时就是单纯的插入排序了,由于大部份的元素都已大致排序过了,
所以最后一次的插入排序几乎没作什么排序动作了:
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void shellsort(int[]);
int main(void)
{
int number[MAX] = {0};
int i;
srand(time(NULL));
printf("排序前:");
for(i = 0; i < MAX; i++)
{
number[i] = rand() % 100;
printf("%d ", number[i]);
}
shellsort(number);
return 0;
}
void shellsort(int number[])
{
int i, j, k, gap, t;
gap = MAX / 2;
while(gap > 0)
{
for(k = 0; k < gap; k++)
{
for(i = k+gap; i < MAX; i+=gap)
{
for(j = i - gap; j >= k; j-=gap)
{
if(number[j] > number[j+gap])
{
SWAP(number[j], number[j+gap]);
}
else
break;
}
}
}
printf("\ngap = %d:", gap);
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
gap /= 2;
}
}
//测试结果
java实现
public class ShellTest {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
public static void main(String args[]) {
int i; // 循环计数变量
int index = a.length; // 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < index; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
shellSort(index); // 选择排序
System.out.print("排序后: "); // 排序后结果
for (i = 0; i < index; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
}
public static void shellSort(int index) {
int i, j, k; // 循环计数变量
int temp; // 暂存变量
boolean change; // 数据是否改变
int dataLength; // 分割集合的间隔长度
int pointer; // 进行处理的位置
dataLength = (int) index / 2; // 初始集合间隔长度
while (dataLength > 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = dataLength; j < index; j++) {
change = false;
temp = a[j]; // 暂存Data[j]的值,待交换值时用
pointer = j - dataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
//while (temp < a[pointer] && pointer >= 0 && pointer <= index) {
while (temp < a[pointer]) {
a[pointer + dataLength] = a[pointer];
// 计算下一个欲进行处理的位置
pointer = pointer - dataLength;
change = true;
if (pointer < 0 || pointer > index)
break;
}
// 与最后的数值交换
a[pointer + dataLength] = temp;
if (change) {
// 打印排序结果
System.out.print("排序中: ");
for (k = 0; k < index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
dataLength = dataLength / 2; // 计算下次分割的间隔长度
}
}
}
分享到:
相关推荐
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
binary sort,二分法查找,binary search, 二分法排序,merge sort 混合排序,shell sort 希尔排序,insertion sort 插入排序。数据结构 data structure
插入排序采用三种方法实现,希尔排序根据插入排序采用的方法不同,也有三种,但是又通过改进得到一种最为简介的实现方式。所有方法的实现在博客中:http://blog.csdn.net/ns_code/article/details/20043459中有详细...
插入排序法由未排序的后半部前端取出一个值,插入已排序前半部...排序要加快的基本原则之一,是让后一次的排序进行时,尽量利用前一次排序后的结果,以加快排序的速度,Shell排序法即是基于此一概念来改良插入排序法。
希尔排序,比较高效的排序算法之一。这是一个例子,一个关于希尔排序的例子。
用函数实现希尔(shell)排序,并输出每趟排序的结果,初始增量d=n/2,其后d=d/2 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个...
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,...
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
printf("\t7: 希尔排序\n"); printf("\t***************************\n"); scanf("%d",&i); //输入整数1-7,选择排序方式 switch (i){ case 1: InsertSort(R); break; //值为1,直接插入排序 case 2: ...
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
演示了直接插入排序和shell排序,多种软件可执行。采用了基础语言c语言。
]希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组...
希尔排序(Shell Sort)是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔...
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
数据结构排序算法中的希尔(shell)排序,可供初学者参考
希尔排序(Shell Sort)是插入排序的一种更高效的改进版本,也称为“缩小增量排序”。它的基本思想是:先将整个待排序的记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体...
希尔排序(Shell's Sort)是插入排序的一种,又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而...
shellsort希尔排序算法增加最佳组合1
Shell(希尔)排序算法C语言源程序,算法思路:比如对4个数进行排序,4个数分为两组,然后第1个数与第3个数进行比较,第2个数与第4个数进行比较,调整位置,然后将经过调整后的第2位与第3位再进行比较 。
基于python的排序算法-希尔排序Shell Sort