插入排序 订阅
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。 展开全文
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2]  。
信息
外文名
Insertion sort
空间复杂度
O(1)
别    称
直接插入排序
分    类
排序方法
中文名
插入排序
时间复杂度
O(N^(1-2))
稳定性
稳定
插入排序基本思想
插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌 [1]  。插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序 [3]  。
收起全文
精华内容
参与话题
问答
  • 三种简单排序(冒泡、插入、选择)的比较和图解

    万次阅读 多人点赞 2018-01-20 16:09:43
    冒泡排序 这种排序方式是最容易理解的,主体思想就是: 指针重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列...

    冒泡排序

    这种排序方式是最容易理解的,主体思想就是:

    指针重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

    接下来我们来看看冒泡排序的图解,这里一个推荐网站:https://visualgo.net/ ,里面有很多算法实现的动画,可以对运行过程有一个更直观的了解):
    这里写图片描述

    冒泡排序一次只比较两个数字,并且这两个数字是相邻的。
    从图上我们可以看到,原数组为【30,8,15,18,12】。
    第一次比较首先比较第0位和第一位,并且将结果大的数字往后移动,也就是交换。第0位是40, 第1 位是8,40>8,所以我们将大的数字往后移动。
    同理,如果第0位<第1 位,我们就不进行交换。

    之后我们在比较第1位和第2位的数字。将结果大的往后移动。

    就这样,通过n-1次比较后(n为数组长度),我们就将最大的数字移到了数组的最末端。然后再继续进行第二轮比较,找出第二大的数字,往后以此类推。

    一共需要比较的次数为: (n-1)+(n-2)+(n-3)+·····+1;

    以下是JAVA代码实现:

    public class BubbleSort {
        public static void sort(int[] a) {
            for(int i=a.length-1;i>=0;i--){ //i控制比较的轮数
                for(int j=0;j<i;j++){ //j每一轮比较的次数
                    if(a[j]>a[j+1]){
                        a[j]=a[j]^a[j+1];
                        a[j+1]=a[j]^a[j+1];
                        a[j] = a[j]^a[j+1];
                    }
                }
            }
        }
    }

    选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

    我们来看一下图解:

    这里写图片描述

    选择排序就是对数组中的元素进行比较选择,然后直接放置在排序后的位置。
    首先指针K先指向数组0号位置,K相当于指明一个目标位置。然后另一个指针min从K开始,往后一次比较,找到最小的值,并存储在min中,比较了一轮后,min中存储的数就是整个数组中最小的数字。这是直接将min中的数字和K指向的数字交换即可。然后找到数组中第二小的数,让他跟数组中第二个元素交换一下值,以此类推。

    JAVA代码实现:

    public class StraightSelectionSort {
        public static void sort(int a[]) {  
            int k=0;
            for(int i=0;i<a.length-1;i++){
                k=i;
                for(int j=i+1;j<a.length;j++){
                    if(a[j]<a[k]){
                        k=j;
                    }
                }
                if(k!=i){
                    a[k] = a[k]^a[i];
                    a[i] = a[k]^a[i];
                    a[k] = a[k]^a[i];
                }
            }
        }
    }
    

    插入排序

    要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。

    • 直接插入排序

    直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

    我们来看一下图解:
    这里写图片描述

    这张图虽然只有一步,但是很好的表现了插入排序的运行过程。
    例如,已知待排序的一组记录是:
    1,3,5,8,2,1
    加入之前的1,3,5,8已经按照直接插入排序排序好了,现在我们需要对2进行排序。 首先将2存在一个临时变量temp中, 然后指针从2的前一位开始判断,如果前一位比2大,则将前一位往后移,以此类推,直到找到比2小的元素。这时将2插入进去。

    JAVA代码实现:

    public static void StraightInsertSort(int[] a) {
            int temp = 0,j = 0;
            for(int i = 1;i < a.length;i++){
                temp = a[i];
                j = i;
                while(j > 0 && a[j-1] >= temp){
                    a[j] = a[j-1];
                    j--;
                }
                a[j] = temp;
            }
        }
    • 二分插入排序

    将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理A[i]时,A[0]……A[i-1]已经按关键码值排好序。所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较;否则只能插入A[i-1/2]到A[i-1]之间,故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负,直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半,其中间结点为A[k+r/2],经过一次比较即可排除一半记录,把可能插入的区间减小了一半,故称为折半。执行折半插入排序的前提是文件记录必须按顺序存储。

    JAVA代码实现:

    public static void binaryInsertSort(int array[],int size)  
        {  
            int i,j,k,temp;  
            for(i=1;i<size;i++)  
            {  
                temp=array[i];  
                if(array[i]<array[0])  
                    k=0;  
                else  
                    k = binarySearch(array,0,i,temp);  
    
                for(j=i;j>k;j--)  
                {  
                    array[j]=array[j-1];  
                }  
                array[k]=temp;  
                System.out.println(Arrays.toString(array));  
            }  
        }
    • 希尔排序

    希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    下面我们来看图解:

    希尔排序

    希尔排序意在减少直接排序中的数字移动次数,通过设置一个间隔,每次进行比较的都是间隔的数字。
    比如说如图:
    第一次的间隔是5,则可以将数字分为5组,每一组两个数字,将这两个数字进行比较,逆序就交换。这样我们第一次排序就完成了。
    这时候的数组肯定还是存在许多的逆序对,所以我们需要将间隔缩小,在进行比较。如图,这时候间隔变成了3,也就是可以将4个数字分为一组比较,这时候可以使用直接插入排序的思想,在组内进行直接插入排序比较。只是跨度为间隔数而不是1了。
    之后以此类推,直到间隔为1的时候,这时候就直接是直接选择排序了。

    关于间隔的选择

    这个间隔怎么确定,是个数学难题,至今没有解答。但是通过大量的实验,还是有个经验值。

    减小间隔

    上面已经演示了以5为初始间隔对包含10个数据项的数组进行排序的情况。对于更大的数组开始的间隔也应该更大。然后间隔不断减小,直到间隔变成1。

    举例来说,含有1000个数据项的数组可能先以364为增量,然后以121为增量,以40为增量,以13为增量,以4为增量,最后以 1为增量进行希尔排序。用来形成间隔的数列被称为间隔序列。这里所表示的间隔序列由Knuth提出,此序列是很常用的。数列以逆向形式从1开始,通过递归表达式

    h=3*b+1

    来产生,初始值为1。

    在排序算法中,首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初被赋为1,然后应用公式h=3*h+1生成序列1,4,13,40,121,364,等等。当间隔大于数组大小的时候,这个过程停止。对于一个含有1000个数据项的数组,序列的第七个数字,1093就太大了。因此,使用序列的第六个数字作为最大的数字来开始这个排序过程,作364-增量排序。然后,每完成一次排序全程的外部循环,用前面提供的此公式倒推式来减小间隔:

    h=(h-1)/3

    这个倒推的公式生成逆置的序列364,121,40,13,4,1。从364开始,以每一个数字作为增量进行排序。当数组用1-增量排序后,算法结束。

    希尔排序比插入排序快很多,它是基于什么原因呢?当h值大的时候,数据项每一趟排序需要移动元素的个数很少,但数据项移动的距离很长。这是非常有效率的。当h减小时,每一趟排序需要移动的元素的个数增多,但是此时数据项已经接近于它们排序后最终的位置,这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。

    注意后期的排序过程不撤销前期排序所做的工作。例如,已经完成了以40-增量的排序的数组,在经过以13-增量的排序后仍然保持了以40-增量的排序的结果。如果不是这样的话,希尔排序就无法实现排序的目的。

    选择间隔序列可以称得上是一种魔法。至此只讨论了用公式h=h*3+1生成间隔序列,但是应用其他间隔序列也取得了不同程序的成功,只是一个绝对的条件,就是逐渐减小的间隔最后一定要等于1,因此最后一趟排序是一次普通的插入排序。

    在希尔的原稿中,他建议初始的间距为N/2,简单地把每一趟排序分成了两半。因此,对于N=100的数组逐渐减小的间隔序列为50,25,12,6,3,1。这个方法的好处是不需要在不开始排序前为找到初始的间隔而计算序列;而只需要用2整除N。但是,这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好,但是这种方法有时会使运行时间降到O(N2),这并不比插入排序的效率更高。

    这个方法的一个变形是用2.2而非2来整除每一个间隔。对于N=100的数组来说,会产生序列45,20,9,4,1。这比用2整除显著改善了效果,因为这样避免了某些导致时间复杂度为O(N2)的最坏情况的发生。不论N为何值,都需要一些额外的代码来保证序列的最后取值为1。

    JAVA代码实现:

    public static void sort(int[] a) {
            int h = 1;
            while (h < a.length / 3) {
                h = h * 3 + 1;
            }
            int temp = 0, j = 0;
            while (h >= 1) {
                for (int i = h; i < a.length; i++) {
                    temp = a[i];
                    for (j = i; j >= h && a[j - h] >= temp; j -= h) {
                        a[j] = a[j - h];
                    }
                    a[j] = temp;
                }
                h = (h - 1) / 3;
            }
        }

    几种排序算法的时间比较

    这里写图片描述

    这里的稳定性意思是,拿选择排序举例子。选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法。

    展开全文
  • 插入排序

    万次阅读 多人点赞 2018-10-24 17:05:13
    插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在...

    算法思想

    插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,如下图所示:
    图片来源于算法导论
    那插曲排序是如何借助上面提到的思想来实现排序的呢?首先我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素,然后在未排序区间中依次取出元素并插入到已排序区间的合适位置,并保证已排序区间一直是有序。重复这个步骤直到未排序区间元素为空,算法结束。

    插入算法步骤

    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5

    可以用一张图来理解一下上面的算法步骤:

    图片来源于捎的饭捎的饭图片来源于GeeksForGeeks
    图片来源于GeeksForGeeks

    代码实现

    
    // Java实现插入排序
    class InsertionSort 
    { 
        /*Function to sort array using insertion sort*/
        void sort(int arr[]) 
        { 
            int n = arr.length; 
            for (int i=1; i<n; ++i) 
            { 
                int key = arr[i]; 
                int j = i-1; 
      
                /* Move elements of arr[0..i-1], that are 
                   greater than key, to one position ahead 
                   of their current position */
                while (j>=0 && arr[j] > key) 
                { 
                    arr[j+1] = arr[j]; 
                    j = j-1; 
                } 
                arr[j+1] = key; 
            } 
        } 
      
        /* A utility function to print array of size n*/
        static void printArray(int arr[]) 
        { 
            int n = arr.length; 
            for (int i=0; i<n; ++i) 
                System.out.print(arr[i] + " "); 
      
            System.out.println(); 
        } 
      
        // Driver method 
        public static void main(String args[]) 
        {         
            int arr[] = {12, 11, 13, 5, 6}; 
      
            InsertionSort ob = new InsertionSort();         
            ob.sort(arr); 
              
            printArray(arr); 
        } 
    }
    

    性能分析

    最坏时间复杂度—Θ(n2)

    如果数组是倒序的,每次插入就相当于在数组的第一个位置插入数据。比如将 0 插入到数组[2, 3, 5, 7, 11]中,因为数组中的元素都大于 0 ,所以
    需要需要与数组中的所有元素进行比较并以此将元素向右移动,最终将0 插入到数组第一个位置。通常来讲,假设数组的length为n,将元素插入到数组的操作称为insert,被插入元素Key需要与数组元素进行比较的此时称为K。 那么在这种情况下,将某一个元素插入到数组时 k = n - 1。
    综上所述,在插入排序的流程中,第一次进行insert时K = 1,第二次K = 2, 第三次K = 3…最后一次K = n - 1.因此插入排序所用的总的时间为:
    1 + 2 + 3 + ⋯ (n−1) = (1+2+3+⋯+(n−1)) = n2 / 2 - n / 2 用big-Θ表示法表示就是 Θ(n2)

    最好时间复杂度—Θ(n)

    那么插入排序可以使用少于Θ(n2) 的时间吗 ? 答案是肯定的。如果要排序的数据已经是有序的,我们并不需要搬移任何数据。从尾到头在有序数据组里查找插入位置每次只需要比较一个数据就能确定插入的位置,所以这种情况下,最好时间复杂度是Θ(n)

    平均时间复杂度

    试想一下,如果被插入数组的排序是随机的,那感觉概率学,平均情况下此数组中的每一个元素都会比其它一半的元素小。
    基于这样的一个概念下,调用insert往数组中插入元素时就需要进行 K/2 次比较。同事插入排序会固定执行 N - 1 此insert操作,所以插入排序的平均时间复杂度也是 Θ(n2)

    展开全文
  • 插入排序法(详细介绍)

    万次阅读 多人点赞 2019-05-13 21:26:22
    前面我的博文中详细介绍了冒泡排序法、选择排序法,今天我们继续学习另一种排序方法—插入排序,分为前插排序和后插排序。 插入排序的基本思想是:将数组的第一个数认为是有序数组,从后往前(从前往后)扫描该有序...

    前面我的博文中详细介绍了冒泡排序法选择排序法,今天我们继续学习另一种排序方法—插入排序,分为前插排序和后插排序。

    插入排序的基本思想是:将数组的第一个数认为是有序数组,从后往前(从前往后)扫描该有序数组,把数组中其余n-1个数,根据数值的大小,插入到有序数组中,直至数组中的所有数有序排列为止。这样的话,n个元素需要进行n-1趟排序!!!

    举个例子:4个数字4,6,7,5进行从大到小的排序。前插排序法具体过程如下:
    把第一个数4插入到空的有序数组中的第一个位置上,得到新数字序列4;

    第一趟:从后往前扫描有序数组,将第二个数字6和有序数组中的4进行比较,6大于4,此时将4后移一个位置。此时已经扫描完有序数组中的数,将6插入到4的前面(有序数组的第一个位置),得到新数字序列6,4;

    第二趟:从后往前扫描有序数组,先将第三个数字7和有序数组中的4进行比较,7大于4,此时将4后移一个位置;再将7和有序数组中的6进行比较,7大于6,此时将6后移一个位置。此时已经扫描完有序数组中的数,将7插入到6的前面(有序数组的第一个位置),得到新数字序列7,6,4;

    第三趟:从后往前扫描有序数组,先将第四个数字5和有序数组中的4进行比较,5大于4,此时将4后移一个位置;再将5和有序数组中的6进行比较,5小于6,由于有序数组就按照从大到小排列的,此时直接把5插入到4的前面即可!不需要再和7进行比较!最后,得到新数字序列7,6,5,4;

    插入排序的关键点:
    1、采用双层循环:时间复杂度也是O(n的平方)
    (1)外层循环表示的是排序的趟数,n个数字需要n-1趟,因此,外层循环的次数是n-1次;同时也代表数的位置。
    (2)内层循环表示的是每一趟排序的数字。根据插入排序的思想,第i趟排序时,有序数组中的数字就有i个,就需要进行i次比较,因此循环i次。注意采用的是从后往前进行比较。
    2、从后往前扫描的时候,如果必须插入的数大于有序数组中当前位置的数,则有序数组中的数和它之后的数均往后移一个位置,否则,把插入的数插入到有序数组中。(稳定排序)

    为了便于道友们向我咨询问题,特意开设了一个免费的知识星球——CaptianXue,星球提供学习、理财、生活、职场等各类文章和免费答疑!!
    在这里插入图片描述

    附上完整的插入排序的C++代码和相关注释;:

       #include<iostream>
        #include<cstdio>
        using namespace std;
        #define N 5
        int a[N];//有序数组
        int main ( ) {
        	int i, k, x;
        	printf("Please input %d numbers:\n",N);   
        	for (i=0; i<N; i++) {
        		scanf ("%d", &x);
        		for ( k=i; k>0; k-- ) {	        /* 从后向前比较 */
        			if ( a[k-1] > x )    //x前面的数比它大
        				a[k]=a[k-1];         /* 将大数向后移动*/
        			else      break; /* 找到插入的位置,退出 */
        		}
        		a[k] = x;  /* 完成插入操作 */
        	}
        
        	for (i=0; i<N; i++)
        		printf("%d ", a[i]);
        	return 0;
        }
    

    更多的排序算法:
    sort函数排序 https://blog.csdn.net/weixin_43956598/article/details/90241551
    冒泡排序 https://blog.csdn.net/weixin_43956598/article/details/90176251
    选择排序 https://blog.csdn.net/weixin_43956598/article/details/90178197
    插入排序 https://blog.csdn.net/weixin_43956598/article/details/90181567
    快速排序 https://blog.csdn.net/weixin_43956598/article/details/90215135
    希尔排序 https://blog.csdn.net/weixin_43956598/articledetails/90234480
    堆排序 https://blog.csdn.net/weixin_43956598/article/details/90343547

    展开全文
  • 插入排序(图解)

    万次阅读 多人点赞 2019-05-20 10:58:28
    插入排序 1、直接插入排序 基本思想:每一步将一个待排序的数据插入到前面已经排好序的有序序列中,直到插完所有元素为止。 算法实现:直接插入排序是将无序序列中的数据插入到有序的序列中,在遍历无序序列时,...

    插入排序

    1、直接插入排序

    基本思想:每一步将一个待排序的数据插入到前面已经排好序的有序序列中,直到插完所有元素为止。

    算法实现:直接插入排序是将无序序列中的数据插入到有序的序列中,在遍历无序序列时,首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置,一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4,6,8,5,9}来说,我们首先先确定首元素4是有序的,然后在无序序列中向右遍历,6大于4则它插入到4的后面,再继续遍历到8,8大于6则插入到6的后面,这样继续直到得到有序序列{4,5,6,8,9}。

    (1)我们用一个变量tmp存放关键字,因为我们先确定第一个元素是暂时有序的,所以tmp存放无序序列的第二个元素,然后i开始也为第二个元素的下标,j则为i-1,因为j要用有序的区域元素来与无序的区域元素比较。那么一开始i=1,tmp=6,j=0,因为6>4,所以6就不用进行插入;然后i向右走,i=2,tmp=arr[2]=8,j=i-1=1,8>6>4也不用插入。

    (2)i继续向右走,i=3,tmp=arr[3]=5,j=i-1=2,5<8则要将8给5所在的元素数据,j向左走继续遍历有序区域。

    (3)当j向右走到6时发现6>tmp=5,所以将6给它右边的第一个值(j+1的位置),再继续遍历有序区域,j=0时发现4<5则j+1的位置就是5该在的位置那么就将tmp的值5给j+1的位置的元素的值。

    (4)再继续上面的操作,i最后到9发现比前面有序区域的元素都大,则不用再插入了,这样就得到了一个有序序列{4,5,6,8,9}。

    代码实现:

    void StraightSort(int *arr,int len)
    {
    	int tmp;
    	int i;
    	int j;
    	for (i = 1;i < len;i++)
    	{
    		tmp = arr[i];
    		for (j = i - 1;j >= 0 && arr[j] > tmp;j--)
    		{
    			arr[j + 1] = arr[j];
    		}
    		arr[j + 1] = tmp;
    	}
    }

    2、希尔排序(shell排序)

    基本思想:希尔排序是把序列按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量的逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰好被分为一组,算法便终止。

    算法实现:希尔排序需要定义一个增量,这里选择增量为gap=length/2,缩小增量以gap=gap/2的方式,这个增量可以用一个序列来表示,{n/2,(n/2)/2....1},称为增量序列,这个增量是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。

    (1)对于一个无序序列{8,9,1,7,2,3,5,4,6,0}来说,我们初始增量为gap=length/2=5,所以这个序列要被分为5组,分别是{8,3},{9,5},{1,4},{7,6},{2,0},对这5组分别进行直接插入排序,则小的元素就被调换到了前面,然后再缩小增量gap=gap/2=2。

    (2)上面缩小完增量后,序列再次被分为2组,分别是{3,1,0,9,7}和{5,6,8,4,2},再对这两组进行直接插入排序,那么序列就更加有序了。

    (3)然后再缩小增量gap=gap/2=1,这时整个序列就被分为一组即{0,2,1,4,3,5,7,6,9,8},最后再进行调整,就得到了有序序列{0,1,2,3,4,5,6,7,8,9}。

    代码实现:

    void ShellSort(int *arr,int len)
    {
    	for (int gap = len/2;gap > 0;gap = gap/2)
    	{
    		for (int i = gap;i < len;i++)
    		{
    			int j = i;
    			while (j - gap >= 0 && arr[j] < arr[j - gap])
    			{
    				Swap(arr,j,j - gap);
    				j = j - gap;
    			}
    		}
    	}
    }

     

    展开全文
  • 图解插入排序

    千次阅读 多人点赞 2017-11-23 22:34:59
    插入排序时一种常见的排序算法,其原来有点类似于我们打扑克摸牌的过程,每摸一张牌,我们便通过对比手上已有的牌,将刚拿到的牌放入合适的位置。其实现实现思路(假设按正序排序)假设请j个已经排好序, 将第j个...
  • 漫画:什么是插入排序

    千次阅读 多人点赞 2019-08-12 08:48:00
    ————— 第二天 —————————————————人们如何进行扑克牌的排序呢?举个例子,比如我手中有红桃6,7,9,10这四张牌,已经处于升序排列:这时候,我又抓...
  • 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。 各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图:   一、插入排序: 思想:每步将...
  • 插入排序算法详解及实现

    万次阅读 多人点赞 2016-06-10 20:30:37
    插入排序相对冒泡排序而言是一种较为快捷方便的排序算法。 冒泡排序:http://blog.csdn.net/llzk_/article/details/51547923 插入排序原理很简单,讲一组数据分成两组,我分别将其称为有序组与待插入组。...
  • 算法排序----插入排序法

    万次阅读 多人点赞 2018-06-02 18:59:50
    接下来我来讲述一下插入排序法。首先来解释一下插入排序法的原理,它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序,也就是要找到新插入的数对应原序列中的位置。那么也就是说,每次插入一个...
  • 插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据。 直接插入排序是插入排序算法中的一种,采用的方法是:...
  • 插入排序法(Java实现)

    万次阅读 多人点赞 2018-08-12 11:54:28
    插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量插入排序与打扑克时整理手上的...
  • Java语言实现的直接插入排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流!
  • C语言算法--直接插入排序法

    千次阅读 多人点赞 2018-07-09 23:53:47
    直接插入排序法的思想是:  对于一个数组,检查其中第i个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数...
  • “深入理解”—插入排序算法

    万次阅读 2016-06-21 17:57:33
    插入排序算法思想:每趟将一个元素,按照其关键字的大小插入到它前面已经排序的子序列中,依此重复,直到插入全部元素。 插入排序包括:直接插入排序、二分插入排序以及希尔排序。 1、直接插入排序...
  • 插入排序算法(动态数组实现) printf("--------插入排序算法的实现--------\n"); printf("输入数组的大小length:\n"); int length=0; scanf("%d",&length); /****动态分配内存初始化数组*********************...
  • 直接插入排序是是一种稳定的排序,其算法简便,适用于顺序结构和链式结构,更适合于基本有序(正序)的情况。其空间复杂度为O(1),时间复杂度为O(n2)。下面是实现算法: 先是预定义和类型定义: typedef int ...
  • 经典排序算法(4)——折半插入排序算法详解

    万次阅读 多人点赞 2016-03-16 13:12:51
    折半插入排序(Binary Insertion Sort)是一种插入排序算法,通过不断地将数据元素插入到合适的位置进行排序,在寻找插入点时采用了折半查找。 一、算法基本思想 (1)基本思想 折半插入排序的基本思想是:...
  • 直接插入排序算法

    千次阅读 2018-07-10 12:53:07
    算法思想: 每一步将待排序的对象,按其关键码大小,插入到前面已经排好的一组对象的合适位置,直到对象全部插入为止.即边插入排序.给出实现代码: #include &lt;iostream&gt; using namespace std; int ...
  • 直接插入,平均情况O(n2),最好情况O(n),最坏情况O(n2),辅助空间O(1),稳定。
  • 简单插入排序算法

    2019-06-27 15:31:18
    简单插入排序算法 时间复杂度:O(N^2) 原理:每一趟将带排序中的元素,按其关键字大小,插入到已排序的表中的适合的位置,直到所有待排序元素全部插入为止。插入排序每次排序完成,从而得到一个新的、记录数量增1...

空空如也

1 2 3 4 5 ... 20
收藏数 580,269
精华内容 232,107
关键字:

插入排序