`
leichenlei
  • 浏览: 129469 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

排序(3)希尔(Donald L. Shell)排序

 
阅读更多

最近学到希尔排序,感觉理解非常费劲。下面是自己总结的希尔排序,希望自己以后不要忘了。嘿嘿。希尔排序其实是高级插入排序,所以学习希尔排序之前需要了解插入排序。

 

一、希尔排序过程:

1,首先根据公式h = h*3 + 1,递归求出h的值;即让h=1,一直递归到h < length结束,得到h。

例如:长度是10的数组,h = 4。

2,公式递减地进行插入排序

for(按公式递减间隔){

//开始插入排序过程

 for(从第二个间隔位置;到末尾;+1){
   for(从第二个间隔位置;>=0; -=间隔)

 }

}

例如:3,7,8,0,9,5,4,1,6,2

方括号:代表(第二个间隔位置)

圆括号:代表与方括号一起进行插入排序的元素

h=4

1,[(3), 7, 8, 0, [9], 5, 4, 1, 6, 2] => [(3), 7, 8, 0, [9], 5, 4, 1, 6, 2]
2,[3, (7), 8, 0, 9, [5], 4, 1, 6, 2] => [3, [5], 8, 0, 9, (7), 4, 1, 6, 2]
3,[3, 5, (8), 0, 9, 7, [4], 1, 6, 2] => [3, 5, [4], 0, 9, 7, (8), 1, 6, 2]
4,[3, 5, 4, (0), 9, 7, 8, [1], 6, 2] => [3, 5, 4, (0), 9, 7, 8, [1], 6, 2]
5,[(3), 5, 4, 0, (9), 7, 8, 1, [6], 2] => [(3), 5, 4, 0, [6], 7, 8, 1, (9), 2]
6,[3, (5), 4, 0, 6, (7), 8, 1, 9, [2]] => [3, [2], 4, 0, 6, (5), 8, 1, 9, (7)]

h=1
7,[(3), [2], 4, 0, 6, 5, 8, 1, 9, 7] => [[2], (3), 4, 0, 6, 5, 8, 1, 9, 7]
8,[(2), (3), [4], 0, 6, 5, 8, 1, 9, 7] => [(2), (3), [4], 0, 6, 5, 8, 1, 9, 7]
9,[(2), (3), (4), [0], 6, 5, 8, 1, 9, 7] => [[0], (2), (3), (4), 6, 5, 8, 1, 9, 7]
10,[(0), (2), (3), (4), [6], 5, 8, 1, 9, 7] => [(0), (2), (3), (4), [6], 5, 8, 1, 9, 7]
11,[(0), (2), (3), (4), (6), [5], 8, 1, 9, 7] => [(0), (2), (3), (4), [5], (6), 8, 1, 9, 7]
12,[(0), (2), (3), (4), (5), (6), [8], 1, 9, 7] => [(0), (2), (3), (4), (5), (6), [8], 1, 9, 7]
13,[(0), (2), (3), (4), (5), (6), (8), [1], 9, 7] => [(0), [1], (2), (3), (4), (5), (6), (8), 9, 7]
14,[(0), (1), (2), (3), (4), (5), (6), (8), [9], 7] => [(0), (1), (2), (3), (4), (5), (6), (8), [9], 7]
15,[(0), (1), (2), (3), (4), (5), (6), (8), (9), [7]] => [(0), (1), (2), (3), (4), (5), (6), [7], (8), (9)]

其中

步骤1,5为对索引0,4,8的一个完整的插入排序

步骤2,6为对索引1,5     的一个完整的插入排序

步骤3......

步骤4.....

以此类推。

二、看下面的程序

while(h > 0) 是过程1公式递减

for(int i = h; i < data.length; i++) 和while(k >= 0) 完成了过程2,过程2实际穿插地合并了若干个插入排序。

 

上程序:

 

 

public static int[] data = {3,7,8,0,9,5,4,1,6,2};
	
	public static void main(String[] args) {
		System.out.println(Arrays.toString(data));
		int h = 1;
		//求间隔公式
		while(h <= data.length / 3){
			h = h*3 + 1;
		}
		while(h > 0){ //减小间隔
			//插入排序
			for(int i = h; i < data.length; i++){//合并了两个循环过程
				int temp = data[i];
				int j = i;
				while(j > h-1 && data[j - h] >= temp){
					data[j] = data[j - h];
					j -= h;
				}
				data[j] = temp;
			}
			h = (h - 1) / 3;
		}
		System.out.println(Arrays.toString(data));

 

 

 

分享到:
评论

相关推荐

    希尔排序.pdf

    希尔排序是一种基于插入排序的算法,由计算机科学家唐纳德·希尔(Donald Shell)在1959年提出。它的基本思想是将待排序的数组分割成若干个子序列,分别进行插入排序,待整个序列中的元素“基本有序”时,再对全体...

    排序算法(希尔排序, 快速排序...) C语言

    **希尔排序**是基于插入排序的,由美国计算机科学家Donald Shell于1959年提出。它通过设定一个增量序列,逐步减少增量,将数据分组进行插入排序,从而提高效率。希尔排序的时间复杂度在最坏情况下为O(n^1.3),在最好...

    希尔排序 又称shell排序

    希尔排序是一种基于插入排序的高效排序算法,由计算机科学家Donald Shell在1959年提出。该算法通过将原始序列分割成多个子序列,分别进行插入排序来提高排序效率。随着分割间隔逐步减小至1,整个数组最终被完全排序...

    C#实现希尔排序算法.

    希尔排序(Shell Sort)是一种基于插入排序的快速排序方法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干子序列,然后对每个子序列进行插入排序,最后逐步减少增量,直到增量...

    希尔排序java.zip

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列,然后分别对子序列进行插入排序,最后再进行一次整体的插入...

    c++ 7 种排序.快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序

    7. **希尔排序**:由Donald Shell提出的改进版本的插入排序,通过设置不同的增量将待排序的序列分割成若干子序列,分别进行直接插入排序,然后逐步减小增量,直至增量为1,完成整个序列的排序。希尔排序的时间复杂度...

    希尔排序法python版源码.txt

    希尔排序是一种基于插入排序的算法,由计算机科学家唐纳德·L·希尔(Donald L. Shell)在1959年提出。希尔排序通过将原始数据集分割成若干子序列进行分别插入排序,达到降序排列的目的。与传统的插入排序相比,希尔...

    六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。

    希尔排序是插入排序的一种更高效的改进版本,由Donald Shell提出。它通过比较距离较远的元素来减少排序过程中的交换次数。希尔排序使用一个增量序列,逐步缩小间隔,使得元素可以更快地达到最终位置,从而提高了...

    数据结构之希尔排序算法程序

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列,然后对每个子序列进行插入排序,最后再进行一次全局的插入...

    希尔排序法(希尔插入排序,希尔交换排序)

    希尔排序法是计算机科学领域中一种重要的排序算法,它由美国计算机科学家Donald Shell于1959年提出,因此得名希尔排序。希尔排序是一种基于插入排序的改进算法,通过将待排序序列分为若干个子序列进行独立排序来提高...

    8640 希尔(shell)排序.txt

    希尔排序是由Donald Shell在1959年提出的一种排序算法,它是一种基于插入排序的改进版本。与传统的插入排序相比,希尔排序通过引入“增量”(也称为“间隔”或“步长”)的概念来提高排序效率。该算法首先选择一个较...

    快速排序、堆排序、归并排序、希尔排序实现

    希尔排序是由Donald Shell于1959年提出的,它是插入排序的一种更高效的改进版本。希尔排序的基本思想是通过设定间隔序列,将待排序的元素按照间隔进行排序,随着间隔逐渐减小,直到间隔为1,此时数组基本有序,再...

    希尔排序,冒泡排序,堆排序等各种排序算法

    希尔排序是插入排序的一种改进版本,由Donald Shell提出。它通过将待排序的数据分割成若干个子序列,然后对每个子序列进行插入排序,最后再对整个序列进行一次插入排序。这种方法减少了元素之间的比较次数,提高了...

    希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序

    1. **希尔排序**:希尔排序是由Donald Shell提出的,它是插入排序的一种更高效的改进版本。希尔排序通过将待排序的元素按照一定的间隔分组,然后对每个组进行插入排序,随着间隔逐渐减小,最终实现整个序列的排序。...

    C#算法 -- (三)希尔排序.doc

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的元素按照一定的间隔分组,对每组进行插入排序,然后逐渐减小间隔,直至间隔为1,完成整个序列的...

    希尔排序算法源代码

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的元素按照一定的间隔分组,对每组进行插入排序,然后逐渐减小间隔,直到间隔为1,此时整个序列视为...

    数据结构-3期(KC002) 希尔排序算法.docx

    希尔排序是一种基于插入排序的快速排序算法,由Donald Shell在1959年提出。它的主要思想是将待排序的元素按照一定的增量分组,然后对每一组进行直接插入排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减...

    希尔排序

    希尔排序(Shell Sort)是一种基于插入排序的算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据分成若干个子序列,然后对每个子序列进行插入排序,随着子序列的范围逐渐减小,最终整个序列完成排序。...

    算法可视化系列——排序算法——希尔排序

    希尔排序(Shell Sort)是一种基于插入排序的快速排序方法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的间隔进行分组,然后对每组进行插入排序,随着间隔逐渐缩小,最后进行一次全排列,...

    算法-数据结构之希尔排序(谢尔排序).rar

    由Donald Shell于1959年提出,它的基本思想是将待排序的元素按照一定的增量分组,对每组进行直接插入排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。希尔...

Global site tag (gtag.js) - Google Analytics