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

希尔排序

阅读更多
/*
希尔排序

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。

希尔排序是不稳定的,其时间复杂度为O(n ^2)。
*/

public class ShellSort{
	
	 public static void main(String[] args){
//		 int[] array = {49,38,65,97,76,13,27};
		 int[] array = {49,38,65,97,76,13,27,49,55,04};
		 shellSort(array);
		 for(int i=0;i<array.length;i++){
			 System.out.print(array[i]+" ");
		 }
	 }
          
           public static void shellSort(int[] data) {  
	        int j = 0;  
	        int temp = 0;  
	        for (int increment = data.length / 2; increment > 0; increment /= 2) {  
	            for (int i = increment; i < data.length; i++) {  
	                temp = data[i];  
	                for (j = i; j >= increment; j -= increment) {  
	                    if(temp < data[j - increment]){  
	                        data[j] = data[j - increment];  
	                    }else{  
	                        break;  
	                    }  
	                }   
	                data[j] = temp;  
	            }  
	        }  
	    } 
	 /*
	public static void shellSort(int[] arr,int length){
		int h;
		
		while(arr.length/3>h){
			h = h*3+1;
		}
		
		while(h>0){
			for(int i=h;i>0;i++){
				int temp = arr[i];
				int j =i;
				while(j >h-1 && arr[j-h]>temp ){
					arr[j] = arr[j-h];
					j -=h;
				}
				arr[j] = temp;
			}
			h=(h-1)/3;
		}
	}
	*/
	 /*
	 public static void  shellSort(int[] array,int length){
	    int increment=length/2; //增量初值,不妨设n>0
	    do {
	    	shellPass(array,increment,length);//一趟增量为increment的Shell插入排序
	          increment=increment/3+1;//求下一增量
	       }while(increment>1);
	 } //ShellSort

	 public static void shellPass(int[] array,int d,int length){//希尔排序中的一趟排序,d为当前增量
	     for(int i=d+1;i<length;i++) //将R[d+1..n]分别插入各组当前的有序区
	       if(array[i]<array[i-d]){
	         array[0]=array[i];
	         int j=i-d;//R[0]只是暂存单元,不是哨兵
	         do {//查找R[i]的插入位置
	            array[j+d]=array[j];//后移记录
	            j=j-d;//查找前一记录
	         }while(j>0&&array[0]<array[j]);
	         array[j+d]=array[0]; //插入R[i]到正确的位置上
	       } //endif
	   } //ShellPass
	*/
	 /*
	 //希尔排序, array要排序的数据, len数据的个数
	 public static void shellSort(int[] array, int len){
	     //以step分组,step每次减为原来的一半。
	     for (int step = len / 2; step > 0; step /= 2){
	         //对每个组进行排序
	         for (int i = 0 ;i < step; i++){
	             sortGroup(array, len, i, step);
	         }
	     }

	 }
	 
	 public static void sortGroup(int[] array, int len, int start,int step){
	     for (int i = start + step; i < len; i += step){
	         //寻找i元素的位置,
	         for (int j = start; j < i; j+= step){
	             //如果比他小,则这里就是他的位置了
	             if (array[j]>array[i]){
	                 int nTemp = array[i];
	                 for (int k = i; k > j; k -= step){
	                     array[k] = array[k - step];
	                 }
	                 array[j] = nTemp;
	             }
	         }
	     }
	 }
	

	 
	 
	 public static void shellSort2(int arr[], int n){  
	     int i, j;  
	     int key;  
	     int h;  
	   
	     for (h = 1; h <= (n-1)/9; h = 3*h + 1)   
	    	 for (; h > 0; h /= 3)  
	    		 for (i = h; i < n; i++){  
		             key = arr[i];  
		             j = i;  
		             while ((j >= h) && (arr[j-h] > key)){  
		                 arr[j] = arr[j-h];  
		                 j -= h;  
		             }  
		             arr[j] = key;  
	    		 }  
	 }
	 */
}

分享到:
评论

相关推荐

    希尔排序算法源代码

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

    C语言_希尔排序希尔排序

    希尔排序(Shell Sort)是由Donald Shell在1959年提出的一种基于插入排序的改进算法。它的主要思想是通过设置一系列的增量序列,逐步减少这些增量,将待排序的元素进行分组,然后在每个小组内进行直接插入排序。这个...

    合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现

    本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...

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

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

    《快速排序 直接插入排序 堆排序 希尔排序 选择排序:五种排序》

    (1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...

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

    ### 希尔排序法(希尔插入排序,希尔交换排序) #### 一、希尔排序法简介 希尔排序法是计算机科学领域中一种重要的排序算法,它由美国计算机科学家Donald Shell于1959年提出,因此得名希尔排序。希尔排序是一种...

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

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

    内部排序 希尔排序和直接插入排序的比较

    ### 直接插入排序与希尔排序的比较 #### 一、概述 本篇文章将通过一组具体的数据集(8个整数)对直接插入排序(Direct Insertion Sort)和希尔排序(Shell Sort)这两种排序方法进行深入分析和比较。这两种排序...

    希尔排序java代码

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的增量分组,对每组使用直接插入排序,然后逐渐减小增量,继续进行分组排序,直到增量...

    数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序等等

    根据提供的文件信息,我们可以深入探讨几种经典的排序算法:冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. ...

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

    下面将详细讲解这7种排序算法:快速排序、归并排序、插入排序、选择排序、冒泡排序、堆排序以及希尔排序。 1. **快速排序**:由C.A.R. Hoare提出的,采用分治策略。基本思想是选取一个基准元素,通过一趟排序将待...

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

    本主题将详细探讨希尔排序、冒泡排序、堆排序等经典的排序算法,这些都是数据结构与算法学习中的核心内容,尤其对于北邮数据结构课程来说,理解并掌握这些排序方法至关重要。 1. **插入排序**: 插入排序是一种...

    基数排序、堆排序、希尔排序、直接插入排序

    这里我们将深入探讨四种常见的排序算法:基数排序、堆排序、希尔排序和直接插入排序。 首先,基数排序是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序...

    希尔排序C语言实现

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

    希尔排序(程序).txt

    ### 希尔排序原理与实现 #### 一、希尔排序简介 希尔排序(Shell Sort)是一种基于插入排序的高效算法。它通过将原始数组分割成多个子序列来进行排序,从而提高了插入排序的效率。希尔排序的核心思想是通过将相隔...

    7大排序算法实现程序(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)

    本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...

    数据结构——希尔排序

    希尔排序,又称希尔斯排序,是由美国计算机科学家Donald Shell于1959年提出的一种基于插入排序的快速排序算法。这种排序方法通过设置一个增量序列,将待排序数组分割成若干个子序列,然后对每个子序列进行插入排序。...

    希尔排序基本思想

    希尔排序是一种基于插入排序的快速排序算法,由Donald Shell在1959年提出。它的主要特点是通过将待排序的数组元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,直到间隔为1时,整个数组成为一个...

    希尔排序的代码

    ### 希尔排序算法详解 #### 算法概述 希尔排序(Shell Sort),又称为缩小增量排序,是插入排序的一种更高效的改进版本。它由Donald Shell在1959年提出。希尔排序的基本思想是:将待排序列分割成若干子序列分别...

    希尔排序(C语言程序)

    希尔排序是一种基于插入排序的快速排序算法,由Donald Shell在1959年提出。它通过设置一个间隔序列,将待排序的数组分为若干个子序列,然后对每个子序列进行插入排序,随着间隔序列逐渐减小,最终完成整个数组的排序...

Global site tag (gtag.js) - Google Analytics