精华内容
下载资源
问答
  • 插入排序

    2020-12-22 03:46:21
    插入排序算法 插入排序的思想分析及图解… 插入排序:(时间复杂度)(稳定性) 算法思想: 从数组中第二个元素开始,与前面的有序数列元素依次比较, 当满足大于前者小于后者时插入其中(若到有序树列首部,则插入...

    插入排序算法

    插入排序的思想分析及图解…
    其属于:非线性时间比较类排序 中的插入排序

    插入排序:(时间复杂度)(稳定性)在这里插入图片描述

    算法思想:

    从数组中第二个元素开始,与前面的有序数列元素依次比较,

    当满足大于前者小于后者时插入其中(若到有序树列首部,则插入队首)

    重复上述直至遍历到数组末尾

    插入排序动态演示:

    在这里插入图片描述
    代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    //插入函数定义
    void insert_sort(vector<int> &arr)
    {
    	//计算元素个数
    	int len = arr.size();
    	//遍历范围 arr[1] -arr[len-1]
    	for (int i = 1; i < len; ++i)
    	{
    		int j = i;
    		//提出待插值
    		int k = arr[i];
    		//找寻待插位置
    		while (j > 0 && arr[(j - 1)] > k)
    		{
    			arr[j] = arr[j - 1];
    			--j;
    		}
    		//插入
    		arr[j] = k;
    	}
    }
    int main()
    {
    	//简单测试
    	vector<int> arr = { 8,5,9,6,4,5 };
    	cout << "排序前:";
    	for (auto a : arr)
    		cout << a << " ";
    	insert_sort( arr);
    	cout << "排序后:";
    	for (auto a:arr)
    		cout << a << " ";
    	return 0;
    }
    

    点个赞吧!


    展开全文
  • 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的...


    下列所有排序都默认是升序,从小到大。

    插入排序

    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

    直接插入排序


    插入排序的过程


    插入排序就像有的人打扑克一样,每次摸起来一张牌后,在手中已经排序好的扑克中插入当前摸起的这张牌。问题的关键点就是:如何在已经排好序的序列中,找到当前元素该插入的位置


    当序列中只有一个元素时,不需要排序,因为一个元素已经有序。


    现在来考虑有多个元素的过程:




    因为一个元素已经有序,所以需要从第二个元素开始找插入位置,即需要有一层循环从第二个元素遍历到最后一个元素。

    然后来思考在循环内该怎么做?

    首先我们应该知道,在一个已经就绪的序列中插入一个元素,肯定 会导致插入位置之后的所有元素都会向后移动一位, 要牢记这一点。

    循环内:
    我们可以先把当前把插入的元素先保存起来,然后分别将刚才保存起来的元素与有序序列中的每一个元素比较,那么比较到什么时候才停下来?
    a. 出现一个比保存的元素小的元素(saveNum < array[ i ] );
    b.以序队列已经比较完毕(i >=0 )。
    因为以序队列的范围是从 0 .. 当前插入元素位置 -1 , 所以我们需要一个循环来完成比较和搬迁元素。
    当循环条件不满足时,即找到插入位置。直接插入即可。

    参考代码:

    void InsertSort(int* array, int size)
    {
    	if (array == NULL || size <= 0)
    		return;
    
    	// 从数组第二个元素开始处理,因为一个元素已经有序
    	for (int i = 1; i < size; i++)
    	{
    		int temp = array[i];
    		int end = i - 1;
    		
    		// 插入array[i] 到已序序列中 array[0.. i-1]
    		while (end >= 0 && temp < array[end])
    		{
    			array[end + 1] = array[end];
    			end--;
    		}
    
    		// 插入 array[i]
    		array[end + 1] = temp;
    	}
    }
    
    // 打印数组
    void PrintfArray(string info , int* array, int size)
    {
    	cout << info << ":";
    	for (int i = 0; i < size - 1; ++i)
    		cout << array[i] << " ";
    	cout << endl;
    }
    
    int main()
    {
    	int array[] = {5, 9, 1, 6, 2, 4, 7, 8, 0 , 2, 0};
    	int size = sizeof(array) / sizeof(array[0]);
    	PrintfArray("排序前", array, size);
    	InsertSort(array, size);
    	PrintfArray("排序后", array, size);
    	return 0;
    }


    输出:
    排序前:5 9 1 6 2 4 7 8 0 2
    排序后:0 0 1 2 2 4 5 6 7 8


    二分插入排序


    我们知道,插入排序最重要的就是在 已序序列中找到插入位置,在上面的代码中,我们每次找位置,都需要一个一个挨着遍历元素,如果插入位置在第以序序列的头部(从后往前比较),那么时间复杂度将是线性的,最坏情况O(N)。

    细心的同仁们已经发现在以序序列,那么是不是可以把二分查找的思想搬迁过来,可以提高找位置的效率呢?     文章: 二分查找递归和循环实现

    当然是可以的。

    思路主要是利用在有序序列查找元素复杂度为对数级别,从而优化了 找元素的时间。但是搬移元素的时间是必不可少的。

    参考代码:
    void InsertSort_Binary(int * array, int size)
    {
    	if (array == NULL || size <= 0)
    		return;
    
    	for (int i = 1; i < size; ++i)
    	{
    		
    		int temp = array[i];
    
    		int left = 0;     // 有序序列的左边界
    		int right = i - 1;// 有序序列的右边界
    
    		while (left <= right)
    		{
    			int mid = (left + right) / 2;
    			// 注意这里的 等号,为了保证算法的稳定性(相同关键字排序前后位置不会变)
    			// 所以也需要向后移动
    			if (array[mid] <= temp)
    				left = mid + 1;
    			else if (array[mid] > temp)
    				right = mid - 1;
    			
    		}
    
    		// 搬移数据, 上面循环结束后,left的位置就是插入位置
    		// 需要将从left 到 当前插入元素的前一个位置都搬移一个位置
    		for (int j = i - 1; j >= left; --j)
    		{
    			array[j + 1] = array[j];
    		}
    		array[left] = temp;
    	}
    }



    希尔排序

    希尔排序是插入排序的改良版,虽然可以使用二分来较少找元素插入位置的时间。但是主要的时间消耗都在搬移元素,而且一次只能搬移一个元素。而希尔排序是在指直接插入排序的基础上,添加了一个排序增量的方法。 把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。使用不同的希尔增量会有不同的改进效果。

    希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当n值很大时数据项每一趟排序需要移动的个数很少,但数据项的距离很长。当n值减小时每一趟需要移动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

    参考代码:
    增量数值可参考网上数学分析过的数值,下面代码举例给了321。

    void ShellSort(int*array , int size)
    {
    	int gap = 3;
    	while (gap > 0)
    	{
    		for (int idx = gap; idx < size; idx += gap)
    		{
    			int temp = array[idx];
    
    			int end = idx - gap;
    			while (end >= 0 && array[end] > temp)
    			{
    				array[end + gap] = array[end];
    				end -= gap;
    			}
    			array[end + gap] = temp;
    		}
    		gap--;
    	}
    }
    




    总结一下: 如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

    展开全文
  • 线性链表排序

    2016-05-21 14:06:07
    线性链表排序算法(一种没什么卵用表插入改进的排序方法 2333)

    老师讲排序的时候讲到插入排序里的二分排序表插入排序,

    二分插入排序的特点是比较次数少,移动次数多;

    表插入排序的特点的是比较次数多,移动次数少;

    于是我在想一种介于二分插入排序和表插入排序之间的排序算法,结合两种算法的优点,于是诞生了二分表插入排序

    但是在不断的实践和思考中,我发现这种算法并不适合于插入排序,算法复杂度空间复杂度时间复杂度皆较高(和老师探讨之后,老师说这种算法挺有意思的,但并没有什么卵用,23333)。

    简单来说就是构造一个结构体指针数组,然后 指针指来指去balalalala  最后我给这种算法改名为线性链表排序法 233333

    这种算法的优点是:可以查看未排序之前的顺序,具有稳定性和适应性

    给出C语言实现:线性链表排序法

    #ifndef _SECLISTSORT_H_
    #define _SECLISTSORT_H_
    struct Node;
    typedef char DataType;
    struct Node{
        int key;
        DataType info;
        struct Node* next;
    };
    typedef struct Node* pNode;
    struct NodeArray{
        int m;
        pNode* pn;
    };
    typedef struct NodeArray* pNodeArray;
    pNodeArray createNodeArray(int m,int ak[],pNode ptop);
    void binListSort(pNodeArray pan,pNode ptop);
    #endif // _SECLISTSORT_H_
    
    线性链表排序法C文件

    #include "seqlistsort.h"
    #include <malloc.h>
    #include <stdio.h>
    pNodeArray createNodeArray(int m,int ak[],pNode ptop){ 
        int i = 0;
        pNodeArray pan;
        pan = (pNodeArray)malloc(sizeof(struct NodeArray));
        if(pan){
            pan->m = 0;
            pan->pn = (pNode)malloc(sizeof(struct Node)*m);
            if(pan->pn){
                while(i<m){
                    pan->pn[i]=(struct Node*)malloc(sizeof(struct Node));
                    if(pan->pn[i])
                        pan->m++;
                    pan->pn[i]->key = ak[i];
                    i++;
                }
                i=0;
                while(i<m-1){
                    pan->pn[i]->next=pan->pn[i+1];
                    i++;
                }
            pan->pn[i]->next = NULL;
            }
            ptop->next = pan->pn[0];
            return pan;
        }
        else
            free(pan);
            printf("Out of space!\n");
        return NULL;
    }
    void binListSort(pNodeArray pan,pNode ptop){
        pNode now,pre,p,q;
        pre = ptop->next;
        if (pre == NULL) return ;
        now = pre->next;
        if(now == NULL) return ;
        while(now){
            q = ptop;p = ptop->next;
            while(p!=now && p->key <= now->key){q = p,p = p->next;}
            if(p == now){pre = pre->next;now = pre->next;continue;}
            pre->next = now->next;
            q->next = now;now->next = p;
            now = pre->next;
        }
    }
    主文件C:

    #include <stdio.h>
    #include <stdlib.h>
    #include "seqlistsort.h"
    int main()
    {
        int ak[]={1,3,2,4,6,5,0,9,7,8};
        int i;
        pNode pt=(pNode)malloc(sizeof(struct Node)); //链表头结点指针(没有特别构造一个头结点结构体)
        pNode p=(pNode)malloc(sizeof(struct Node));;
        pNodeArray pan = createNodeArray(10,ak,pt);
        for(i=0;i<10;i++)                            //未排序序列
            printf("%d ",pan->pn[i]->key);
        printf(" 未排序序列\n");
        binListSort(pan,pt);                         //排序
        p = pt->next;
        while(p){                                    //线性链表排序后序列
            printf("%d ",p->key);
            p=p->next;
        }
        printf(" 线性链表排序后序列\n");
        for(i=0;i<10;i++)                            //原未排序序列
            printf("%d ",pan->pn[i]->key);
        printf(" 原未排序序列\n");
        return 0;
    }
    
    输出结果:

    然后你会机智的发现 这似乎真的没什么卵用  -。-
    可是很多东西刚创造出来的就是没有什么意义的啊 但是说不定有一天就改变世界了呢 (小伙子你膨胀了) 23333





    展开全文
  • 本文主要讲了插入排序、二分插入排序和希尔排序。

    插入排序

    • 插入排序的可视化图:

    • 插入排序的概念::是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    • 插入排序的算法描述如下:

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

    static void InsertSort(int[] arr) {
        int temp = 0;
        int index = 0;
        for (int i = 1; i < arr.Length; i++) {
            temp = arr[i];
            index = i - 1;
            for (; index >= 0 && temp < arr[index]; index--) 
                arr[index + 1] = arr[index];
            arr[index + 1] = temp;
        }
    }
    
    • 插入排序复杂度:
      • 时间复杂度 $O(n^{2})$
      • 最优时间复杂度 $O(n)$
      • 平均时间复杂度 $O(n^{2})$
      • 空间复杂度总共 $O(n)$,需要辅助空间 $O(1)$

    二分插入排序

    • 二分插入排序的可视化图:

    • 二分插入排序的概念:二分法插入排序是在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上。

    • 二分插入排序的算法描述如下:

      • 用待插元素的值与当前查找序列的中间元素的值进行比较,以当前查找序列的中间元素为分界,确定待插元素是在当前查找序列的左边还是右边,如果是在其左边,则以该左边序列为当前查找序列,右边也类似。按照上述方法,递归地处理新序列,直到当前查找序列的长度小于1时查找过程结束。
    • 二分插入排序的代码实现:

    public static void BinarySort(int[] arr) {
        for (int i = 1; i < arr.Length; i++) {
            int low = 0;
            int high = i - 1;
            int temp = arr[i];
            //Find
            while (low <= high) {
                int mid = (low + high) / 2;
                if (temp < arr[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
    
            for (int j = i - 1; j >= low; j--)
                arr[j + 1] = arr[j];
            arr[low] = temp;
        }
    }
    
    • 二分插入排序的复杂度:
      • 时间复杂度 $O(n^{2})$
      • 最优时间复杂度 $O(n)$
      • 平均时间复杂度 $O(n^{2})$
      • 空间复杂度:总共 $O(n)$,辅助 $O(1)$

    希尔排序

    • 希尔排序的可视化图:

    • 希尔排序的概念:也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
      希尔排序是基于插入排序的以下两点性质而提出改进方法的:
      插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
      但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

    • 希尔排序的算法描述如下:

      • 将数组列在一个表中并对列排序(用插入排序)。
      • 重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。
      • 将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)。
    • 希尔排序的代码实现:

    public static void ShellSort(int[] arr) {
        int gap, i, j;
        int temp = 0;
        int len = arr.Length;
        for (gap = len >> 1; gap > 0; gap >>= 1)
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
    }
    
    • 希尔排序的复杂度:
      • 时间复杂度 $O(n\log^2 n)$
      • 最优时间复杂度 $O(n)$
      • 平均时间复杂度:根据步长序列的不同而不同
      • 空间复杂度 $O(n)$

    如有错误,欢迎指出。

    email:dxmdxm1992#gmail.com

    blog: csdn magicdavid.top

    展开全文
  • 比较排序线性时间排序

    千次阅读 2018-07-27 20:50:37
    你的打赏是我奋笔疾书的动力!...比较排序:在排序最终结果中,元素之间的次序依赖于他们之间的比较,故称归并排序,快速排序,堆排序,插入排序为比较排序。 比较排序可以抽象为一颗决策树。《算法导论》...
  • 使用Java进行排序和搜索 二进制搜索,气泡排序,插入排序线性搜索,快速排序,时间,带定时的定时搜索
  • 经典排序之插入排序

    千次阅读 2016-09-29 20:09:53
    插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。 图1演示了对4个元素进行直接插入排序的过程,共需要(a),(b),(c)三次插入。 设数组为a
  • 插入排序 堆排序 定理 比较排序的算法速度不会超过nlgn 决策树 举例3个数进行比较排序的决策树 每一个内部节点都会有一个下标为i:j标记,左孩子为小于等于,右孩子为大于 每一个叶结点表示一个排序结果,其中有一个...
  • 一文搞定插入排序算法

    千次阅读 多人点赞 2020-06-07 00:01:06
    一文搞定插入排序算法
  • 三:插入排序 定义: 实例3: 四:希尔排序 定义: 实例4: 五:归并排序 定义: 实例5:迭代法 实例6:递归法 六:快速排序 定义: 实例7:迭代法 实例8:递归法 一:冒泡排序 定义: 冒泡排序...
  • 设计思想直接插入排序是将线性序列中的元素分为有序部分和待排序部分,每次第一个取待排序数进入排序部分查找到相应位置插入,使有序部分依旧有序,直到整个序列有序。 算法步骤: 将第一待排序序列第一个元素看做...
  • 我们知道,传统的比较排序法的时间复杂度是有下界的,最快也不会快于O(nlgn),比较排序顾名思义就是通过元素间的相互比较大小,完成排序,例如快速排序、堆排序、插入排序等等。而非比较排序法则可以做到在线性时间...
  • 扑克牌相信大家都有玩过,直接插入排序和玩扑克牌很相似,右手抓取一张扑克牌,并把它插入左手拿着的排好序的扑克里面。 如图: 算法介绍: 直接插入排序算法是最简单的算法,也是最基本的算法。SO,...
  • 直接插入排序

    千次阅读 2018-11-14 23:51:51
    直接插入排序 题目描述 利用直接插入排序算法实现线性表的排序。要求输出第k趟排序的结果。例如原来线性表为:26,12,25,4,36,15,21,第一趟直接排序排序结果为: 12,26,25,4,36,15,21,第二趟直接插入排序结果为: 12...
  • 直接插入排序: 我们的记录本身就是基本有序的,我们只需要少量的插入操作,就可以完成整个记录集的排序工作,此时直接插入很高效。还有就是记录数比较少时,直接插入的优势也比较明显。 void InsertSort(int b[],...
  • 在数据结构和算法中,排序是非常重要的一环,并且排序也是渗透编程的方方面面。 你或许在写一个sql的order by按照某组进行排序,又或者你在刷一道题时候、常常遇到贪心+自定义排序求解的思路题,或者变态的面试官让...
  • 插入排序包括直接插入排序和希尔排序;选择排序包括简单选择排序和堆排序;交换排序包括冒泡排序和快速排序。 2.算法的时间复杂度 由小到大为: 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O...
  • 概要: 希尔排序(Shell's Sort)是插入排序的一...1,插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(这是为啥呢?点击去看看), 2,但插入排序一般来说是低效的,因为插入排序
  • 什么是快速排序快速排序简介快速排序(英文名:Quicksort,有时候也叫做划分...所谓原地排序,就是指在原来的数据区域内进行重排,就像插入排序一般。而归并排序就不一样,它需要额外的空间来进行归并排序操作。为了
  • 线性时间排序 1.计数排序 2.基数排序 3.桶排序
  • 直接插入排序、折半插入排序、2-路插入排序、表插入排序、希尔排序。 下面我们来一一介绍:直接插入排序过程叙述:先将序列中的第1个记录看成是一个有序的子序列,然后从第二个记录起逐个进行插入,直至整个序列...
  • c语言插入排序算法In the last article, we discussed about the bubble sort with algorithm, flowchart and code. In this article, we are going to discuss about another basic sorting technique i.e. ...
  • 插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照...很多初学者所说的插入排序,实际上指的就是直接插入排序算法,插入排序算法还包括折半插入排序、2-路插入排序,表插入排序和希尔...
  • 一、插入排序 &lt;1&gt;介绍:插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。...
  • 排序算法之插入排序

    千次阅读 2013-11-06 18:54:10
    简单插入排序算法基本思想、算法实现、算法分析和改进...
  • 八大排序算法(直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序)
  • 插入排序1. 简单插入排序2. 希尔排序三. 选择排序1. 简单选择排序2. 堆排序四. 归并排序1. 二路归并排序2. 多路归并排序 概述 通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非...
  • 【算法】6 比较排序之外学习新的线性时间排序

    千次阅读 多人点赞 2015-06-11 12:36:30
    回顾比较排序相信阅读过前面5篇博文的童鞋们已经发现了“在排序的最终结果中,各元素的次序依赖于它们之间的比较”。于是乎,这类排序算法被统称为”比较排序“。...插入排序在该系列的【算法】1中我们便介绍
  • 前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序)、交换排序(冒泡排序,快速排序)、选择排序(简单选择排序,堆排序)、2-路归并排序(可以参考前一篇文章:各种内部排序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,565
精华内容 27,026
关键字:

线性插入排序说明