精华内容
下载资源
问答
  • 希尔排序 时间复杂度 证明

    千次阅读 2016-04-24 10:52:44
    Shellsort   Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to ... implement....

    Shellsort

     German version  up

    Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.

    Idea

    The idea of Shellsort is the following:

    1. arrange the data sequence in a two-dimensional array
    2. sort the columns of the array

    The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

    Example:  Let  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):

    3790516
    8420615
    734982 
     
     right arrow 
     
    3320515
    7440616
    879982 

    Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:

    332
    051
    574
    406
    168
    799
    82 
     
     
     
     right arrow 
     
    001
    122
    334
    456
    568
    779
    89 

    Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.

    Implementation

    Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15 etc. would form the first column of an array with 5 columns. The "columns" obtained by indexing in this way are sorted with insertion sort, since this method has a good performance with presorted sequences.

    The following program sorts an array a from index position 0 through n-1. The number of columns used for arranging data in each step is in array cols. Thus, data are arranged in 1391376 columns in the first step and in one column in the last step. (Note that essentially nothing is done if the number of columns h is larger than the number of data elements n.) Each column is sorted byinsertion sort. First, data of the second row (beginning at i = h) are sorted to the correct position in their column, then data of the third row (when i reaches value 2h) etc.

     

    Algorithm Shellsort

    void shellsort (int[] a, int n)
    {
        int i, j, k, h, v;
        int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                        1968, 861, 336, 112, 48, 21, 7, 3, 1}
        for (k=0; k<16; k++)
        {
            h=cols[k];
            for (i=h; i<n; i++)
            {
                v=a[i];
                j=i;
                while (j>=h && a[j-h]>v)
                {
                    a[j]=a[j-h];
                    j=j-h;
                }
                a[j]=v;
            }
        }
    }
    

    Analysis

    The correctness of the algorithm follows from the fact that in the last step (with h = 1) an ordinary insertion sort is performed on the whole array. But since data are presorted by the preceding steps (h = 3, 7, 21, ...) only few insertion sort steps are sufficient. How many exactly will be the subject of the following analysis. The above sequence of h's (denoted as h-sequence in the following) is just one of several possible; actually, the performance of Shellsort depends on which h-sequence is used.

    Basics

    The postage for a letter is 16F, for a postcard it is 11F. But there are only stamps of 3F and 7F available. Is it possible to stamp the letter and the postcard exactly?

    Obviously, the problem is to represent the numbers 16 and 11 as linear combinations k·3 + l·7 with nonnegative integer coefficientsk and l. Which natural numbers can be combined from multiples of 3 and 7 and which cannot?

    Definition:  Let gh element natural numbers. We call a number f a combination of g and h, if f can be represented as a linear combination f = kg + lhwith coefficients kl element natural numbers0.

    The letter can be stamped exactly, since 16 is a combination of 3 and 7, namely 16 = 3·3 + 1·7.

    Definition:  Let gh element natural numbers be relatively prime. With N(gh) we denote the (finite) set of all natural numbers that are not combinations of g and h and with γ(gh) the largest of these numbers:

    N(gh)  =  { f element natural numbers  | ¬ there exists kl element natural numbers0 :  f = kg + lh }

    γ(gh)  =  max;(N(gh))

    Example:  Let g = 3, h = 7. Then

    N(gh)  =  {1, 2, 4, 5, 8, 11},   and   γ(gh)  =  11

    The postcard cannot be stamped exactly, since 11 is not a combination of 3 and 7.

    Proposition:  Let gh element natural numbers be relatively prime. Then

    γ(gh)  =  (g-1)·(h-1) – 1

    i.e. every number f with fgreater or equal(g-1)·(h-1) is a combination of g and h.

    Proof:  (Exercise)

    h-sortedness

    Definition:  Let h element natural numbers0. A sequence a1, ..., an is called h-sorted, if for all i element {1, ..., n-h} it holds that

    ailess or equalai+h

    h-sorted sequence is obtained by arranging the sequence in an array with h columns and then sorting the columns. A 1-sorted sequence is sorted.

    Proposition:  Let gh element natural numbers. A g-sorted sequence remains g-sorted after h-sorting it.

    Proof:  see [Knu 73]

    Definition:  A sequence that is g-sorted and h-sorted is called g,h-sorted.

    Proposition:  A g,h-sorted sequence is g+h-sorted.

    Proof:  We have to show that for all i element {1, ..., n-(g+h)} it holds that

    ailess or equalai+g+h

    But this is the case because ailess or equalai+g, since the sequence is g-sorted, and ai+gless or equalai+g+h, since the sequence is h-sorted.

    As an immediate consequence, we have the following

    Proposition:  If a sequence is g,h-sorted, then it is kg+lh-sorted for all kl element natural numbers0, i.e. the sequence is f-sorted for each f that is a combination of g and h.

    Proposition:  Let a be a g,h-sorted sequence, where g and h are relatively prime. Then for all elements ai and aj the following holds:

    j – i greater or equal (g-1)·(h-1) implies ailess or equalaj

    i.e. to the right of each ai only the next (g-1)·(h-1) – 1 elements can be smaller.

    Proof:  Let  j – i  =  f greater or equal (g-1)·(h-1), then f is a combination of g and h. Therefore the sequence is f-sorted, which means that

    ailess or equalai+f  =  aj

    Proposition:  Let a be a g,h-sorted sequence, where g and h are relatively prime, and let d be a variable. If both g and h are inO(d), then O(n·d) sorting steps are sufficient for d-sorting the sequence.

    Proof:  To the right of each element ai at most (g-1)·(h-1) – 1 elements are smaller. d-sorting the sequence means arranging it as a two-dimensional array with d columns and sorting the columns.

    In the column under ai only every d-th of these smaller elements can occur. This means that ai has to be exchanged with at most ((g-1)·(h-1) – 1) / d elements or, since g and h are in O(d), with O(d) elements.

    Since this holds for all ai (i = 1, ..., n), there are O(n·d) sorting steps needed for d-sorting the sequence.

    From this proposition upper bounds for the complexity of Shellsort can be derived.

    Upper bounds

    Theorem:  With the h-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2k – 1, ... Shellsort needs O(n·square rootn) steps for sorting a sequence of length n  (Papernov/Stasevic [PS 65]).

    Proof:  Let ht be the h closest to square rootn. We analyze the behavior of Shellsort separately for the elements hk with kless or equalt and with k > t.

    Let kless or equalt. Since hk = 2k – 1 we have the conditions mentioned above that hk+1 and hk+2 are relatively prime and in O(hk). Therefore, O(n·hk) sorting steps suffice for hk-sorting the data sequence. Since the hk form a geometric series, the sum of allhk with k = 1, ..., t is in O(ht) = O(square rootn). Thus O(n·square rootn) sorting steps are needed for this part where kless or equalt.

    Now let k > t. When the sequence is arranged as an array with hk columns there are n/hk elements in each column. Thus,O((n/hk)2) sorting steps are needed to sort each column, since insertion sort has quadratic complexity. There are hk columns, therefore the number of sorting steps for hk-sorting the entire data sequence is in O((n/hk)2·hk) = O(n·n/hk). Again, the n/hkform a geometric series whose sum is in O(n/ht) = O(square rootn). Therefore, again O(n·square rootn) steps are needed for this part wherek > t.

    It can be shown that for this h-sequence the upper bound is tight. But there is another h-sequence that leads to a more efficient behavior of Shellsort.

    Theorem:  With the h-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q, ... Shellsort needs O(n·log(n)2) steps for sorting a sequence of length n  (Pratt [Pra 79]).

    Proof:  If g = 2 and h = 3, then γ(gh)  =  (g-1)·(h-1) – 1  =  1, i.e. in a 2,3-sorted sequence to the right of each element only the next element can be smaller. Therefore, O(n) sorting steps suffice to sort the sequence with insertion sort. Considering elements with odd and with even index separately, it becomes clear that again O(n) sorting steps suffice to make a 4,6-sorted sequence 2-sorted. Similarly, O(n) sorting steps suffice to make a 6,9-sorted sequence 3-sorted and so on.

    The above h-sequence has the property that for each hk also 2hk and 3hk occurs, so O(n) sorting steps suffice for each hk. Altogether there are log(n)2 elements in the h-sequence; thus the complexity of Shellsort with this h-sequence is inO(n·log(n)2).

    The h-sequence of Pratt performs best asymptotically, but it consists of log(n)2 elements. Particularly, if the data sequence is presorted, a h-sequence with less elements is better, since the data sequence has to be scanned (by the for-i-loop in the program) for each hk, even if only a few sorting steps are performed.

    By combining the arguments of these two theorems h-sequences with O(log(n)) elements can be derived that lead to a very good performance in practice, as for instance the h-sequence of the program (Sedgewick [Sed 96]). But unfortunately, there seems to be no h-sequence that gives Shellsort a worst case performance of O(n·log(n)) (see [Sed 96]). It is an open question whether possibly the average complexity is in O(n·log(n)).

    Sorting network

    Shellsort can be implemented as a sorting network if the data-dependent insertion sort is replaced with bubble sort. With the h-sequence 2p3q the sorting network consists of O(n·log(n)2) comparators. This is the same number of comparators as in bitonic sort.

    The following figure shows the corresponding sorting network for n = 8.

    Figure 1: Shellsort network for n=8
    Figure 1: Shellsort network for n=8
     

    Simulation

    (Java applet for simulation of shellsort)

    References

    Shellsort was originally published by D.L. Shell [She 59].

       
    [Knu 73] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
    [Pra 79] V. Pratt: Shellsort and Sorting Networks. Garland, New York (1979)
    [PS 65] A. Papernov, G. Stasevic: A Method of Information Sorting in Computer Memories. Problems of Information Transmission 1, 63-75 (1965)
    [Sed 88] R. Sedgewick: Algorithms. 2nd edition, Addison-Wesley (1988)
    [Sed 96] R. Sedgewick: Analysis of Shellsort and Related Algorithms. In: Josep Díaz, Maria Serna (Eds.): Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Lecture Notes in Computer Science, Vol. 1136, Springer, 1-11 (1996)
    [She 59]

    D.L. Shell: A High-Speed Sorting Procedure. Communications of the ACM, 2, 7, 30-32 (1959)

     

    Next:   up

     

    homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 29.01.1998   Updated: 15.02.2016



    如果我有时间,就翻译一下吧
    展开全文
  • 希尔排序 算法思想:将整个待排序列分割成若干个子序列(由相隔增量个元素组成),分别进行直接插入排序,然后依次缩小增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。 希尔排序...
     
    

    希尔排序

    算法思想:将整个待排序列分割成若干个子序列(由相隔增量个元素组成),分别进行直接插入排序,然后依次缩小增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
    希尔排序的实现应该由三个循环完成
    (1)第一次循环,将增量d依次折半,直到增量d=1
    (2)第二三层循环,也就是直接插入排序所需要的两次循环。
    在这里插入图片描述

    算法实现

    #include <stdio.h>
    #define N 9
    
    int main(void)
    {
    	int arr[N] = {9,1,5,8,3,7,4,6,2};
    	int d = N / 2; //增量先取一半
    	int i,j,insertVal;
    	//希尔排序三层循环
    	while(d>=1) //当增量大于等于1,不断进行插入排序
    	{
    		//一下两层for循环是直接插入排序代码
    		for(i=d; i<N; i++)
    		{
    			insertVal = arr[i];
    			j = i - d;
    			while(j>=0 && arr[j]>insertVal)
    			{
    				arr[j+d] = arr[j];
    				j = j - d;
    			}
    			arr[j+d] = insertVal;
    		}
    		d = d / 2;
    	}
    	for(i=0; i<N; i++)
    	{
    		printf("%d ",arr[i]);
    	}
    	return 0;
    }
    

    由如上代码知,希尔排序的关键并不是随便分组后各自排序,而是将相隔某个增量的记录组成一个子序列,实现跳跃式移动,使得排序的效率高。

    时间复杂度

    时间复杂度为O(n^1.5),要好于直接排序的O(n ^ 2),需要注意的是增量序列的最后一个增量值必须是1.另外由于记录跳跃式的移动,希尔排序并不是一种稳定的排序方法。

    展开全文
  • 希尔排序最坏情况的时间复杂度是多少哇 。在网上看有O(N^2)的还有O(N^1.5)
  • 希尔排序(缩小增量排序): 1959年Shell发明,第⼀个突破O(n^2)的排序算法,是简单插⼊排序的改进版。 基本思想:设待排序元素序列有n个元素,首先取一个整数【temp=n/2】作为间隔将全部元素分为temp个子序列,...

    希尔排序(缩小增量排序):

    1959年Shell发明,第⼀个突破O(n^2)的排序算法,是简单插⼊排序的改进版。

    基本思想:设待排序元素序列有n个元素,首先取一个整数【temp=n/2】作为间隔将全部元素分为temp个子序列,所有距离为temp的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔temp,重复上述子序列划分和排序工作。直到最后取temp=1,将所有元素放在同一个子序列中排序为止。

    下面直接图示理解:

     

    给出原序列:

     

     

    注意:有两个7,对第一个加了*标注,排序后位置发生改变。


     

     

     

     

     最终序列:

     

    上代码实现: 

    class SortWork {
        public static void printArray(int[] array) {//工具方法
            for (int i : array) {
                System.out.print(i + " ");
            }
        }
    }
    
    public class Bubble {
    
        public static void main(String[] args) {
            int[] array = new int[]{5,8,12,7,10,3,7,9};    
            shellSort(array);
            SortWork.printArray(array);
        }
        
        public static void shellSort(int[] array) {        
            int n = array.length;
            if (n <= 1) {
                return;
            } else {
                int temp = n / 2;
                while (temp >= 1) {
                    for (int i = temp; i < n; i++) {
                        int val = array[i];
                        int j = i - temp;
                        for (; j >= 0; j -= temp) {
                            if (val < array[j]) {
                                array[j + temp] = array[j];
                            }else {
                                break;
                            }
                        }
                        array[j+temp] = val;
                    }
                    temp /=2;
                }
            }
        }
    }
    
    

    最后附上代码运行结果:

    复杂度进行分析: 

    时间复杂度:

    介于O( n ^2)和O(nlogn)之间,视它的最好最坏以及平均复杂度具体分析

    空间复杂度:

    在排序过程中,并没有新数组的产生,所以空间复杂度是 O( 1 )

    稳定性:

    在排序完成后,两个相同的元素位置(上面图示的7*和7)位置发生了改变,所以是不稳定的

     

     

    理解至此,结束!!!

    展开全文
  • 来源:H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © ...希尔排序是最古老的排序算法之一,以其发明者D.L.Shell(1959年)命名[She 59]。虽然该算法速度快,易于理解,易于实现。...

    来源:H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © Created: 29.01.1998 Updated: 04.06.2018
    希尔排序是最古老的排序算法之一,以其发明者D.L.Shell(1959年)命名[She 59]。虽然该算法速度快,易于理解,易于实现。然而,其复杂性分析却要复杂的多。 (୨୧•͈ᴗ•͈)◞︎♡粉色的字是我写的注释嗷。

    算法思想

    希尔排序的算法思想如下如下:

    1. 将数据序列存放在二维数组中
    2. 对数组的列进行排序

    其结果是对数据进行了部分排序。重复上述过程,但是每次都使用较窄的数组,即列数较少。在最后一步,数组仅有一列。在每一步中,需要进行排序的序列都会增加(列数逐渐变少,每列包含的数组逐渐增多),直到最后一步完全排序为止。但是,由于在前面的步骤中获得的序列已经基本有序,因此在每个步骤中进行的排序操作是有有限。

    例如:
    3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2进行排序。
    首先,将其排列成具有7列的数组(左),然后对这些列进行排序(右):

    3	7	9	0	5	1	6				3	3	2	0	5	1	5
    8	4	2	0	6	1	5		→		7	4	4	0	6	1	6
    7	3	4	9	8	2	  				8	7	9	9	8	2	
    

    依次排序之后较大的数据元素89已经到了所在列的末尾,但是一个较小的数字(如倒数第二列的2)也在该列末尾。 下一步将该序列分为3列,并再次对其进行排序:

    3	3	2				0	0	1
    0	5	1				1	2	2
    5	7	4				3	3	4
    4	0	6		→		4	5	6
    1	6	8				5	6	8
    7	9	9				7	7	9
    8	2					8	9	
    

    现在,序列已经基本有序。在最后一步将其排列成一列时,只需将6、8和9移到正确位置即可。

    算法实现

    实际上,数据序列不是存储在二维数组中,而是保存在一维数组中。 例如,位置0、5、10、15等处的数据元素想象为具有5列的数组的第一列。通过这种方式建立索引的“列”,对每列进行插入排序。这种方法具有良好的性能。
    以下程序从索引位置0n-1对数组a进行排序,数据存放在数组cols中。 因此,在第一步中将数据排列在1391376列中,在最后一步中将数据排列在一列中。 (请注意,如果列数h大于待排序数据元素的总数,则基本上不执行任何操作。也就是说,一开始第一步,数据最大值是多大就给他们分配多少列是没意义的,不进行任何操作)对每列插入排序。

    void shellsort (int[] a, int n)
    {
        int i, j, k, h, v;
        int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                        1968, 861, 336, 112, 48, 21, 7, 3, 1}
        for (k=0; k<16; k++)
        {
            h=cols[k];
            for (i=h; i<n; i++)
            {
                v=a[i];
                j=i;
                while (j>=h && a[j-h]>v)
                {
                    a[j]=a[j-h];
                    j=j-h;
                }
                a[j]=v;
            }
        }
    }
    

    算法分析

    该算法的正确性在于最后一步(h = 1)中,对整个数组进行普通插入排序。但是由于数据是通过前面的步骤(h = 3、7、21,…)进行预排序,因此最后一步只有很少的插入排序步骤即可。 上面的h序列(在下文中称为h序列)只是一种取增量的方法,实际上希尔排序的性能取决于增量到底怎么取。

    背景

    寄一封信需要16法郎,一张明信片需要11法郎。但是只能买到3法郎和7法郎的邮票。可以把信和明信片寄出去吗?(兄弟们寄过明信片吗?寄之前邮局已经按照距离规定好了邮费的,寄的时候需要贴上相应价钱的邮票才可以寄出,当没有相应面额的邮票的时候,你就要贴好几枚凑够价钱。比如我们邮政寄一封信1.2元,你可以贴3枚4毛钱的邮票。
    显然,问题是将数字 16 和 11 表示为线性组合 k ⋅ 3 + l ⋅ 7 k·3 + l·7 k3+l7,非负整数系数kl。哪些自然数能由3和7的整数倍组合而成的?哪些不能?

    定义:设 g , h ∈ I N g,h \in IN g,hIN。如果f可以表示为系数k的线性组合 f = k × g + l × h f=k \times g+l \times h f=k×g+l×h,我们则称fgh的线性组合,系数 k , l ∈ I N 0 k,l \in IN_0 k,lIN0
    因为16是3和7的线性组合,即 16 = 3 × 3 + 1 × 7 16=3 \times 3+1 \times 7 16=3×3+1×7,所以可以准确将信封寄出去。

    定义:令 g , h ∈ I N g,h \in IN g,hIN互为质数。 用 N ( g , h ) N(g,h) Ngh表示不是gh的组合的所有自然数的(有限)集合,而 γ ( g , h ) γ(g,h) γgh表示这些数中最大的自然数:
    N ( g , h ) = { f 元 素 自 然 数   ∣   ¬ ∃ k , l ∈ I N 0 : f = k g + l h } γ ( g , h ) = M a x ( N ( g , h ) ) N(g,h)=\{f元素自然数 |  ¬ \exists k,l \in IN_0:f = kg + lh \} \\ γ(g,h)=Max(N(g,h)) N(gh)={f  ¬klIN0f=kg+lh}γ(gh)=Max(N(gh))

    示例:令 g = 3 , h = 7 g = 3,h = 7 g=3h=7
    N ( g , h ) = { 1 , 2 , 4 , 5 , 8 , 11 } , γ ( g , h ) = 11 N(g,h) = \{1,2,4,5,8,11 \},γ(g,h) = 11 N(gh)={1,2,4,5,8,11}γ(gh)=11
    由于11不是3和7的组合,因此无法寄出明信片。

    命题:令 g , h ∈ I N g,h \in IN g,hIN互为质数。 然后 γ ( g , h ) = ( g − 1 ) ⋅ ( h − 1 ) – 1 γ(g, h) = (g-1)·(h-1) – 1 γ(g,h)=(g1)(h1)1
    即,每个大于或等于 ( g − 1 ) ⋅ ( h − 1 ) (g-1)·(h-1) (g1)(h1)的数f都是gh的组合。

    证明:自己做。

    h-排序

    定义: h ∈ I N 0 h \in IN_0 hIN0。如果序列 a 1 , . . . , a n a_1,...,a_n a1...an对于所有 i ∈ { 1 , . . . , n − h } i \in \{1,...,n-h \} i{1...nh}都满足 a i ≤ a i + h a_i \leq a_{i+h} aiai+h被称为h-排序(以增量h对数组进行排序
    数据存放在具有h列的数组中,然后进行列排序,可以获得h-排序的序列。1个排序的序列被排序。

    命题 g , h ∈ I N g,h \in IN g,hIN。一个g-排序的序列在h排序后仍然保持g-排序
    证明:详细见参考文献[Knu 73]

    定义:经过g-排序h-排序的序列称为g,h-排序

    命题:一个g,h排序的序列是g + h-排序的。
    证明:对于所有 i ∈ 1 , . . . , n − ( g + h ) i \in{1,...,n-(g + h)} i1...n(g+h),都满足 a i ≤ a i + g + h a_i \leq a_{i+g+h} aiai+g+h,因为 a i ≤ a i + g a_i \leq a_{i + g} aiai+g,序列是按g-排序的;而 a i + g ≤ a i + g + h a_{i + g} \leq a_{i + g + h} ai+gai+g+h序列是h-排序的。因此我们得出以下结论:

    命题:如果一个序列是g,h-排序的,那么对于所有 k , l ∈ I N 0 k,l \in IN_0 k,lIN0,它都是kg + lh-排序的,即该序列是以f为增量的有序序列,fg,h的线性组合。
    命题:设a为g,h-排序的序列,其中gh是互为质数。 对于所有元素 a i a_i ai a j a_j aj均成立:
    j – i ≥ ( g − 1 ) ⋅ ( h − 1 ) ⇒ a i ≤ a j j – i \geq (g-1)·(h-1) \Rightarrow a_i \leq a_j ji(g1)(h1)aiaj,即任意 a i a_i ai的右侧,仅有下 ( g − 1 ) ⋅ ( h − 1 ) – 1 (g-1)·(h-1) – 1 (g1)(h1)1 个元素比它小。
    证明:令 j – i = f ≥ ( g − 1 ) ⋅ ( h − 1 ) j – i = f \geq (g-1)·(h-1) ji=f(g1)(h1),则fgh的组合。 因此,该序列是f排序的, a i ≤ a i + f = a j a_i \leq a_{i+f} = a_j aiai+f=aj

    命题:设a为g,h-排序的序列,其中gh是互为质数,而d为变量。 如果g和h都在 O ( d ) O(d) O(d)中,则 O ( n ⋅ d ) O(n·d) O(nd)步排序就可以对序列进行d-排序
    证明:在 a i a_i ai的右侧最多 ( g − 1 ) ⋅ ( h − 1 ) – 1 (g-1)·(h-1) – 1 (g1)(h1)1 个元素比它小。 对序列进行d-排序意味着将其排列为有d列的二维数组,然后进行列排序。
    在一列中 a i a_i ai下的列中,较小元素的每隔d个可能出现一次。 这意味着 a i a_i ai最多只能与 ( ( g − 1 ) ⋅ ( h − 1 ) – 1 ) / d ((g-1)·(h-1) – 1) / d ((g1)(h1)1)/d 个元素交换,或者由于gh O ( d ) O(d) O(d)中,因此必须与 O ( d ) O(d) O(d)个元素交换。
    由于这适用于所有 a i ( i = 1 , . . . , n ) a_i(i = 1,...,n) aii=1...n,因此需要进行 O ( n ⋅ d ) O(n·d) O(nd)个排序步骤才能对序列进行d-排序
    从这个命题可以得出希尔排序复杂度的上限。

    上限

    定理1:对于序列h1,3,7,15,31,63,127,...,2k–1,...希尔排序对n个数据排序需要 O ( n ⋅ n ) O(n· \sqrt n) O(nn )个步骤 [ P S 65 ] ^{[PS 65]} [PS65]。(序列h是增量取法
    证明:令序列h中, h t h_t ht的值最接 n \sqrt n n 。我们分别对 k ≤ t k \leq t kt k > t k > t k>t两种情况进行分析。

    • k ≤ t k \leq t kt时,因为 h k = 2 k – 1 h_k = 2^k – 1 hk=2k1,因此可知 h k + 1 h_k + 1 hk+1 h k + 2 h_k + 2 hk+2是互为质数,且数量级为 O ( h k ) O(h_k) O(hk)。 因此, O ( n ⋅ h k ) O(n·h_k) O(nhk)步排序足以对数据进行排序。 由于 h k h_k hk是一个几何级数,当 k = 1 , . . . , t k = 1, ..., t k=1,...,t O ( h t ) = O ( n ) O(h_t) = O(\sqrt n) O(ht)=O(n )时候,所有 h k h_k hk的总和为 O ( n ⋅ n ) O(n· \sqrt n) O(nn )。 因此,当 k ≤ t k \leq t kt时,数量级为 O ( n ⋅ n ) O(n· \sqrt n) O(nn )
    • k > t k > t k>t时,当序列放置在包含 h k h_k hk 列的二维数组时,每列中都有 n / h k n/hk n/hk 元素。由于插入排序具有二次复杂性,因此需要 O ( ( n / h k ) 2 ) O((n/h_k)^2) O((n/hk)2) 步对每列进行排序。有 h k h_k hk 列,由于二维数组有 h k h_k hk列,因此对整个数据序列进行 h k h_k hk-排序 需要 O ( ( n / h k ) 2 ⋅ h k ) = O ( n ⋅ n / h k ) O((n/h_k)^2·h_k) = O(n·n/h_k) O((n/hk)2hk)=O(nn/hk) 步。同样, n / h k n/h_k n/hk也是一个几何级数, O ( n / h t ) = O ( n ) O(n/h_t) = O(\sqrt n) O(n/ht)=O(n )。因此,当 k > t k > t k>t时,同样数量级为 O ( n ⋅ n ) O(n· \sqrt n) O(nn )

    可以证明,对于这个h序列,上界是比较稳定的。但是还有另外的h序列可以使希尔排序更加高效。

    定理2:对于h序列1,2,3,4,6,8,9,12,16,...,2p3q,...,希尔排序对n个数据排序需要 O ( n ⋅ l o g n 2 ) O(n·logn^2) O(nlogn2)个步骤。 [ P r a 79 ] ^{[Pra 79]} [Pra79]序列h是增量取法
    证明:如果 g = 2 g = 2 g=2 h = 3 h = 3 h=3,则 γ ( g , h ) = ( g − 1 ) ⋅ ( h − 1 ) – 1 = 1 γ(g,h)=(g-1)·(h-1)– 1 = 1 γ(gh)=(g1)(h1)1=1,即在一个2,3-排序的序列中,每个元素右侧只有下一个元素可以更小。 O ( n ) O(n) O(n)个步骤足以用插入排序对序列进行排序。分别考虑索引为奇数和偶数的元素,很明显 O ( n ) O(n) O(n)个步骤足以使4,6-排序的序列2-排序。同理 O ( n ) O(n) O(n)个步骤足以使6,9-排序的序列3-排序,以此类推。
    上面的h序列具有以下属性:每个 h k h_k hk也会出现 2 h k 2h_k 2hk 3 h k 3h_k 3hk的性质,因此 O ( n ) O(n) O(n)个步骤足以满足每个 h k h_k hkh序列中总共有 l o g n 2 logn^2 logn2个元素;因此,这种h序列的复杂度为 O ( n ⋅ l o g n 2 ) O(n·logn^2) O(nlogn2)
    这个h序列在渐近性方面表现最佳,特别是,如果数据序列是基本有序的,则待排序序列中元素较少时该序列效果更好,因为即使只有几个排序步骤,也必须(通过for-i循环)对每个 h k h_k hk数据进行扫描。

    通过将这两个定理的结合,可以得到在实际中性能更好的h序列,例如Sedgewick的h序列 [ S e d 96 ] ^{[Sed 96]} [Sed96]。但不幸的是,似乎没有 h 序列能够让希尔排序在最差情况下表现达到 O ( n ⋅ l o g n ) O(n·logn) O(nlogn) [ S e d 96 ] ^{[Sed 96]} [Sed96]。 平均复杂度是否能达到 O ( n ⋅ l o g n ) O(n·logn) O(nlogn)也是一个尚未解决的问题。

    排序网络

    如果数据的插入排序替换为冒泡排序,则可以将希尔排序实现为排序网络。使用 2p3q 的h 序列时,排序网络由 O ( n ⋅ l o g n 2 ) O(n·logn^2) O(nlogn2)个比较器组成。这与双调排序的比较器个数相同。
    下图显示了n=8对应的排序网络。
    在这里插入图片描述

    模拟

    (用于模拟希尔排序的Java小程序)

    参考文献

    • Shellsort was originally published by D.L. Shell [She 59].
    • [Knu 73] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
    • [Pra 79] V. Pratt: Shellsort and Sorting Networks. Garland, New York (1979)
    • [PS 65] A. Papernov, G. Stasevic: A Method of Information Sorting in Computer Memories. Problems of Information Transmission 1, 63-75 (1965)
    • [Sed 88] R. Sedgewick: Algorithms. 2nd edition, Addison-Wesley (1988)
    • [Sed 96] R. Sedgewick: Analysis of Shellsort and Related Algorithms. In: Josep Díaz,
    • Maria Serna (Eds.): Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Lecture Notes in Computer Science, Vol. 1136, Springer, 1-11 (1996)
    • [She 59] D.L. Shell: A High-Speed Sorting Procedure. Communications of the ACM, 2, 7, 30-32 (1959)

    原作者信息

    汉斯·沃纳·朗
    在这里插入图片描述

    • 1980-1990年 基尔大学基督教-阿尔布雷希特斯大学计算机科学研究所 研究助理
    • 1990-1994年 ISATEC 软硬件有限公司 董事兼总经理
    • 1994-2017年 弗伦斯堡应用科学大学计算机科学教授
    • 2012-2014年 弗伦斯堡应用科学大学信息与通信学院 系主任
    • 2014-2016年 弗伦斯堡应用科学大学信息与通信学院 教务长

    碎碎念

    昨晚,啊应该是今天凌晨00:00的时候我给教授发了个邮件,想翻译这个文章,咱们凌晨2:30人家就回复我了。
    在这里插入图片描述
    不论是发邮件的时候还是今天翻译的时候,我深刻感受到了自己是个咸鱼在这里插入图片描述。写完邮件我就想哭,给德国教授写邮件用英语,说不定还有语法错误……然后今天翻译文章时候看到一些名词也是头大。好在我谷歌+必应+百度+查词典最后还是顽强地把它翻译完了。十分欢迎各位大佬批评指正,算了,( ๑ˊ•̥▵•)੭₎₎指正就好了,批评太多我会哭的。
    我是安安,萝莉永不服输 (ง •̀o•́)ง。

    展开全文
  • 可以用逆序数来理解,假设我们要从小到大排序,一个数组中取两个元素如果前面比后面大,则为一个逆序,容易看出排序的本质就是消除逆序数,可以证明对于随机数组,逆序数是O(N^2)的,而如果采用“交换相邻元素”的...
  • 希尔排序时间复杂度为O(n^(1.3—2)),平均时间复杂度为O(nlog2n)。 选择排序的时间复杂度为O(n^2)。 由表格可知,希尔排序速度快于选择排序,时间复杂度低于选择排序,而两者的空间复杂度相同。
  • 下面来分析原始的希尔排序时间复杂度,初始步长d=n/2,下一次步长d=d/2 第一次比较次数,每组2个元素:1*n/2 第二次比较次数,每组4个元素:最坏(1+2+3)*n/4 第三次比较次数,每组8个元素:...
  • 这个时候就要用到一种新的排序方法——插入排序插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序时间复杂度为O(n^2)。...
  • 希尔排序是冲破二次时间屏障的第一批算法之一。 希尔排序通过比较相距一定间隔的元素来工作;各躺比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。由于这个原因,希尔排序有时也叫做...
  • 时间avg 时间min 时间max 空间avg 稳定性 ... 就地快速排序使用的空间是O(1),而真正消耗空间的就是递归调用,每次递归就要保持一些数据; 最优的情况下空间复杂度为:O(logn)...
  • 插入排序包括直接插入排序和希尔排序;选择排序包括简单选择排序和堆排序;交换排序包括冒泡排序和快速排序。 2.算法的时间复杂度 由小到大为: 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O...
  • 排序:原地排序(In-place) 稳定排序:能保证排序过程中相等的数据的相对顺序不变 具有稳定性 1、插入排序:减治算法排序 每次从无序区间选择一个数,插入到有序区间的合适位置 1)查找(从后往前找) 2)...
  • 希尔排序:给定一个int数组A以及大小n,请返回排序后的数组;核心思想:1、先选择步长i,这里的步长是动态的,每次为之前步长的一半,还有一种方法是设置步长数组,但数组中步长为小于20的素数;2、每次更新步长后,...
  • 排序过程、时间复杂度及空间复杂度? 写出你所知道的排序算法及时空复杂度,稳定性? 快速排序 算法在数组中选择一个称为主元(pivot)的元素,将数组分为两部分,使得 第一部分中的所有元素都小于或等于主元,而第...
  • 希尔排序&选择排序&时间复杂度分析

    万次阅读 2013-10-04 00:44:52
    这里分析原始的希尔排序,初始步长d=n/2,下一次步长d=d/2 第一次比较次数:1*n/2 第二次比较次数:最坏(1+2+3)*n/4 第三次比较次数:最坏(1+2+3+……+7)*n/8 ...... 2.分治有一种主定理方法 ...
  • 【数据结构和算法12】希尔排序

    千次阅读 2016-04-16 16:31:43
    上一章我们学习了冒泡排序、选择排序和插入排序三种基础排序算法,这三种排序算法比较简单,时间复杂度均为O(N2),效率不高。这节我们讨论一个高级排序算法:希尔排序希尔排序是基于插入排序的,插入排序有个弊端...
  • 希尔排序,属于插入排序的一种,是直接插入排序的加强版。在希尔排序中引入了步长(gap)的概念,然而在插入排序中,步长默认为1。正如我们直接堆插入排序的分析,数据集合的排列顺序对插入排序的效率会由很大的影响,...
  • 希尔排序

    2018-09-23 21:41:42
    希尔排序 对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要 N-1 次移动。希尔...
  • 希尔排序: // 最优情况下 时间复杂度为 o(n^1.3) ; 最差的情况下为 o(n^2) ,增量序列的最后一个增量值必须等于1  Shell_sort(vector&lt;int&gt; &amp;v1){ int i, j , incre = v1.size() ; do{ ...
  • 12种排序时间复杂度稳定性: 计数排序 基数排序 冒泡 插入 折半插入 归并 锦标赛 快速 希尔排序 选择排序排序
  • 希尔排序与快速排序

    千次阅读 2016-07-15 16:50:03
     希尔排序希尔排序时间复杂度是O(N*(logN)^2)。希尔排序是基于插入排序的。希尔排序又叫缩小增量排序,它是基于插入排序的增强版。  基本思想:把记录按步长进行分组,对每组记录采用直接插入的方法进行排序...
  • 希尔排序简介 冒泡排序在1956年就已经被研究。但是排序速度是比较慢的,冒泡排序的时间复杂度是O(n2),然而在后面的很长的时间里,尽管人们发明各种排序算法(比如前面选择排序和插入排序),但时间复杂度都是0(n2),...
  • 八大排序算法一、直接插入1.基本思路在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。2.代码...
  • 排序算法-希尔排序(移位式)

    千次阅读 2020-06-27 08:22:32
    希尔排序是直接插入排序算法的一种更高效的改进版本,又称"缩小增量排序"。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,...
  • 7大排序时间复杂度对比、以及优化

    千次阅读 2019-03-13 18:07:56
    数据结构:计算机组织存储数据的方式 算法:作用于特定数据集上的算法流程 【排序算法很重要】 ...-原地排序:特指空间复杂度为O(1)的排序算法(就是给定有限个数的空间) 3.算法的稳定...
  • 希尔排序是简单插入排序的改进,直接插入排序的最坏情况时间复杂度达到O(n^2),比如从大到小的一串数字654321,使用插入排序从小到大进行排序,这就达到插入排序的最坏情况。 希尔排序是把记录按下标的一定增量分组...
  • 希尔排序算法是针对直接插入排序算法的改进。其算法描述为:从一个长度为N的无序数组中取一个小与N的整数d1作为第一次的增量,然后将数组按每相隔d1个元素进行全部记录分组(并不是真实分组)。分完组后现在各组中进行...
  • 常用的排序算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 O(n2) O(n*log2n) ...
  • 下列各排序法中,最坏情况下的时间复杂度最低的是(C ) ...希尔排序最坏情况时间下的时间复杂度为 O(n1.5) ;快速排序、冒泡排序最坏情况时间下的时间复杂度为 O(n2) 。故本题答案为 C 选项。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,222
精华内容 12,088
关键字:

希尔排序时间复杂度