精华内容
下载资源
问答
  • 希尔排序(缩小增量排序): 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)位置发生了改变,所以是不稳定的

     

     

    理解至此,结束!!!

    展开全文
  • 希尔排序 时间复杂度 证明

    千次阅读 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



    如果我有时间,就翻译一下吧
    展开全文
  • 时间avg 时间min 时间max 空间avg 稳定性 O(nlog(n)) ... O(nlogn)(每次划分都是对半分) ... O(n²)(每次划分都是n-1和1两部分(元素基本有序... 最优的情况下空间复杂度为:O(logn)...
    时间avg时间min时间max空间avg稳定性

    插入:O(n²)

    希尔:O(n√n)(O(n^(1.3—2)))(与序列有关)

    希尔:O(n^(1.3))

    插入:o(n)序列已经是期望顺序了,在这种情况下,需要进行的比较操作需(n-1)次即可

    希尔:O(n²)

    插入:O(n²)序列是期望顺序的相反序列,那么此时需要进行的比较共有n(n-1)/2次

    希尔、插入排序

    使用的空间是O(1)

    稳定性:

    希尔:不稳定

    插入:稳定

     

    插入排序:

    算法优点:稳定,快。
    算法缺点:比较次数不一定,比较次数越多,插入点后的数据移动越多(特别是当数据总量庞大的时候)。但用链表可以解决这个问题

    适用:当元素数量小分布有序要求稳定直接插入排序将大大减少比较次数和移动记录的次数

    希尔排序

    优缺:

     时间复杂度取决于所用序列:

    在这里插入图片描述

    不稳定;取决于增量序列选择的好坏

    插入排序改进措施

    1. 优化为希尔排序:希尔排序法是对直接插入排序法的优化,通过设置一个增量,对原始序列进行分组,对每组用直接插入排序法排序再整合,再缩小增量,周而复始直至增量为1,完成排序,因此又叫“缩小增量排序法”。
              其实到希尔算法进行到最后,n的值变为1(即增量或者称跳跃数变为1)的时候,它就是直接插入排序,只不过这时候,整个序列基本上是有序的,需要交换的数据已经非常少了,提高效率。
    package main.Test;
    
    import java.util.Arrays;
    
    public class XiErSort {
    
    //    非递归
        private static void sort(int arr[]) {
             for(int d = arr.length/2; d >= 1; d/=2) {
                 for(int i = d; i < arr.length; i++) {
                     int j = i;
                     while (j - d >= 0 && arr[j - d] > arr[j]) {
                         swap(arr, j, j - d);
                         j -= d;
                     }
                 }
             }
        }
    
    //    递归
        private static void sort(int arr[], int d) {
            for(int i = d; i < arr.length; i++) {
                int j = i;
                while (j - d >= 0 && arr[j - d] > arr[j]) {
                    swap(arr, j, j - d);
                    j -= d;
                }
            }
            if (d/2 >= 1)
                sort(arr, d/2);
        }
    
        private static void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    
        public static void main(String[] args) {
            int[] a = new int[]{1, 2, 4, 5, 3, 1, 2, 3};
            sort(a, a.length);
            System.out.println(Arrays.toString(a));
        }
    }
    

     

     

     

    展开全文
  • 排序算法之 冒泡排序及性能优化(时间复杂度+空间复杂度分析) 排序算法之 简单选择排序及时间复杂度分析 排序算法之 直接插入排序及时间复杂度分析 希尔排序 算法思想:将整个待排序列分割成若干个子序列(由相隔...
     
    

    希尔排序

    算法思想:将整个待排序列分割成若干个子序列(由相隔增量个元素组成),分别进行直接插入排序,然后依次缩小增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
    希尔排序的实现应该由三个循环完成
    (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.另外由于记录跳跃式的移动,希尔排序并不是一种稳定的排序方法。

    展开全文
  • 来源:H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © ...希尔排序是最古老的排序算法之一,以其发明者D.L.Shell(1959年)命名[She 59]。虽然该算法速度快,易于理解,易于实现。...
  • 希尔排序,属于插入排序的一种,是直接插入排序的加强版。在希尔排序中引入了步长(gap)的概念,然而在插入排序中,步长默认为1。正如我们直接堆插入排序的分析,数据集合的排列顺序对插入排序的效率会由很大的影响,...
  • 希尔排序是由插入排序延伸而来的,因为插入排序的最后一个数要是最小数就要把它一步一步的插入到最前面,太浪费时间,所以希尔排序是对他进行分组,让它们每次隔一半进行交换(即每次相邻数组长度一半的两个数进行...
  • 下面来分析原始的希尔排序的时间复杂度,初始步长d=n/2,下一次步长d=d/2 第一次比较次数,每组2个元素:1*n/2 第二次比较次数,每组4个元素:最坏(1+2+3)*n/4 第三次比较次数,每组8个元素:...
  • 1、希尔排序——定义 希尔排序按其设计者希尔(Donald Shell)的名字命名,...4、希尔排序——复杂度、稳定性分析 由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序, 但在不同的插入排
  • 排序过程、时间复杂度及空间复杂度? 写出你所知道的排序算法及时空复杂度,稳定性? 快速排序 算法在数组中选择一个称为主元(pivot)的元素,将数组分为两部分,使得 第一部分中的所有元素都小于或等于主元,而第...
  • 【数据结构和算法12】希尔排序

    千次阅读 2016-04-16 16:31:43
    这节我们讨论一个高级排序算法:希尔排序希尔排序是基于插入排序的,插入排序有个弊端,假设一个很小的数据项在很靠近右端的位置上,那么所有的中间数据项都必须向右移动一位,这个步骤对每一个数据项都执行了将近...
  • 这个时候就要用到一种新的排序方法——插入排序插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。...
  • 排序:原地排序(In-place) 稳定排序:能保证排序过程中相等的数据的相对顺序不变 具有稳定性 1、插入排序:减治算法排序 每次从无序区间选择一个数,插入到有序区间的合适位置 1)查找(从后往前找) 2)...
  • 随机生成数组 #include #include ...shell sort 希尔排序 ...gap/=2)//希尔排序的排序步长依次是n/2 n/4 n/8…… ...由表格可知,希尔排序速度快于选择排序,时间复杂度低于选择排序,而两者的空间复杂度相同。
  • 内部排序算法可分为:插入排序(直接插入排序,希尔排序),选择排序(简单选择排序,堆排序),交换排序(冒泡排序,快速排序),归并排序,基数排序等 2,时间复杂度 时间频度:一个算法花费的时间与算法中语句...
  • 算法-希尔排序

    2021-05-13 22:52:51
    空间复杂度 O(1) 稳定性 不稳定 在详细学习快排和希尔排序后,不得不感叹算法的精妙之处,也让我感受到了算法的乐趣 希尔排序是由一个计算机科学家Donald Shell 发明的 实际上是一个插入排序的优化-- 分组插入排序 ...
  • 插入排序包括直接插入排序和希尔排序;选择排序包括简单选择排序和堆排序;交换排序包括冒泡排序和快速排序。 2.算法的时间复杂度 由小到大为: 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O...
  • (1)插入排序:直接插入排序、二分法插入排序、希尔排序 (2)选择排序:直接选择排序、堆排序 (3)交换排序:冒泡排序、快速排序 (4)归并排序 (5)基数排序 排序方法 时间复杂度(平均) 时间...
  • 常见排序算法及其对应的时间复杂度、空间复杂度排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序,本文...
  • 希尔排序&选择排序&时间复杂度分析

    万次阅读 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.分治有一种主定理方法 ...
  • 插入排序又可分为直接插入排序和希尔排序、选择排序又可分为简单选择排序和堆排序、交换排序又可分为冒泡排序和快速排序。 具体关系可有下图表示: 它们的时间复杂度空间复杂幅度分别是: 在基数排序中,r...
  • 排序算法时间复杂度、空间复杂度、稳定性比较

    万次阅读 多人点赞 2017-07-30 21:33:22
    空间复杂度 是否稳定 冒泡排序 :————-: :—–: :—–: :—–: 选择排序 :————-: :—–: :—–: :—–: 直接插入排序 :————-: :—–: :—–: :—–: 归并排序 :————-: :—–: :
  • 三,希尔排序 四,简单选择排序 堆排序 冒泡排序 快速排序 归并排序 基数排序 #include&amp;amp;amp;lt;stdio.h&amp;amp;amp;gt; #include&amp;amp;amp;lt;stdlib.h&amp;amp;amp;gt; #...
  • 希尔排序算法是针对直接插入排序算法的改进。其算法描述为:从一个长度为N的无序数组中取一个小与N的整数d1作为第一次的增量,然后将数组按每相隔d1个元素进行全部记录分组(并不是真实分组)。分完组后现在各组中进行...
  •   希尔排序也叫递减增量排序,是第一批冲破O(n2)的算法之一,他的算法思想很简单,首先拟定一个增量gap,一般是从len(nums)//3或者len(nums)//2开始,然后对序列nums[i,i+gap,i+gap*k…]进行插入排序,一轮迭代完成...
  • 戳蓝字“CSDN云计算”关注我们哦!作者 |奎哥责编 | 阿秃之前的文章...排序算法有很多,如:「冒泡排序」、「插入排序」、「选择排序」、「希尔排序」、「堆排序」、「归并排序」、「快速排序」、「桶排序」、「计数...
  • 空间复杂度 稳定性 选择排序 Selection n2 n2 n2 1 不稳 冒泡排序 Bubble ...
  • 常见排序算法的时间空间复杂度、稳定性比较 一、排序算法比较 注: 1、归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。 2、 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数...
  • 排序算法分类 排序算法比较表格 排序算法 平均时间复杂度 ... 空间复杂度 是否稳定 冒泡排序 O(n2) O(n2) O(1) 是 选择排序 O(n2) O(n2) O(1) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,704
精华内容 9,081
关键字:

希尔排序空间复杂度