对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]（当用大小为n的数组存储顺序循环队列时）

25-01-26 24

本文将分享对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]的详细内容，并且还将对当用大小为n的数组存储顺序循环队列时进行详尽解释，此外，我们还将为大家带来关于C

本文将分享对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]的详细内容，并且还将对当用大小为n的数组存储顺序循环队列时进行详尽解释，此外，我们还将为大家带来关于C# bubble sort,selection sort,insertion sort、Insertion Sort List,Merge Two Sorted Lists,Sort List、Insertion Sort 与 Merge Sort的性能比较(Java)、Insertion Sort，insertionsort的相关知识，希望对你有所帮助。

本文目录一览：

对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]（当用大小为n的数组存储顺序循环队列时）
C# bubble sort,selection sort,insertion sort
Insertion Sort List,Merge Two Sorted Lists,Sort List
Insertion Sort 与 Merge Sort的性能比较(Java)
Insertion Sort，insertionsort

对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]（当用大小为n的数组存储顺序循环队列时）

在《算法简介》（Corman）一书中，练习1.2-2提出了以下有关比较插入排序和合并排序的实现的问题。对于大小为n的输入，插入排序以8n ^
2的步长运行，而合并排序以64n lg n的步长运行；插入排序优于n的哪些值进行合并排序？

尽管我对答案很感兴趣，但是我对如何逐步找到答案更感兴趣（以便我可以重复此过程以尽可能比较任何两个给定算法）。

乍一看，这个问题似乎类似于在业务演算中找到盈亏平衡点，这是我五年多以前上的一堂课，但是我不确定是否会有任何帮助。

谢谢

P / S如果我的标签不正确，此问题的分类不正确，或者此处滥用了其他约定，请限制降级为最低，因为这是我第一次发布问题。

答案1

小编典典

由于您将发现插入排序优于合并排序

8n^2<=64nlognn^2<=8nlognn<=8logn

在解决n-8logn = 0你得到

n = 43.411

因此，对于n<=43插入排序，比合并排序更好。

C# bubble sort,selection sort,insertion sort

https://www.cnblogs.com/Fred1987/archive/2020/02/12/12299546.html

static void Main(string[] args)
        {
            InsertionSortDemo();
            Console.ReadLine();
        }

        static void InsertionSortDemo()
        {
            Random rnd = new Random();
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++)
            {
                arr[i] = rnd.Next(0, 1000);
            }

            Console.WriteLine("Raw data:");
            foreach (var a in arr)
            {
                Console.Write(a + "\t");
            }

            InsertionSort(arr);
            Console.WriteLine("\n\n\nAfter insertion sort:");
            foreach(var a in arr)
            {
                Console.Write(a + "\t");
            }
        }

        static void InsertionSort(int[] arr)
        {
            int inner, temp;
            for (int outer = 0; outer < arr.Length; outer++)
            {
                temp = arr[outer];
                inner = outer;
                while (inner > 0 && arr[inner - 1] >= temp)
                {
                    arr[inner] = arr[inner - 1];
                    inner--;
                }
                arr[inner] = temp;
            }
        }

        static void SelectSortDemo()
        {
            Random rnd = new Random();
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++)
            {
                arr[i] = rnd.Next(0, 10000);
            }

            Console.WriteLine("Raw data:");
            foreach (var a in arr)
            {
                Console.Write(a + "\t");
            }

            SelectionSort(arr);
            Console.WriteLine("\n\n\nAfter selection sort:");
            foreach(var a in arr)
            {
                Console.Write(a + "\t");
            }
        }

        public void SelectSort(int[] arr)
        {
            int min;
            for(int outer=0;outer<=arr.Length;outer++)
            {
                min = outer;
                for(int inner=outer+1;inner<=arr.Length;inner++)
                {
                    if(arr[inner]<arr[min])
                    {
                        min = inner;
                    }
                }
                if(min!=outer)
                {
                    int temp = arr[min];
                    arr[min] = arr[outer];
                    arr[outer] = temp;
                }
            }
        }

        static void SelectionSortDemo()
        {
            Random rnd = new Random();
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++)
            {
                arr[i] = rnd.Next(0, 1000);
            }

            Console.WriteLine("Raw data:");
            foreach (var a in arr)
            {
                Console.Write(a + "\t");
            }

            int[] selectionArr = SelectionSort(arr);
            Console.WriteLine("\n\nSelection sort:");
            foreach(var a in selectionArr)
            {
                Console.Write(a + "\t");
            }
        }

        static int[] SelectionSort(int[] arr)
        {             
            int min = 0;
            for(int i=0;i<arr.Length-1;i++)
            {
                min = i;
                for(int j=i+1;j<arr.Length;j++)
                {
                    if(arr[j]<arr[min])
                    {
                        min = j;
                    }
                }

                if (i != min)
                {
                    int temp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = temp;
                }
            }
            return arr;
        }

        static void BubbleDemo()
        {
            Random rnd = new Random();
            int[] arr = new int[100];
            for(int i=0;i<100;i++)
            {
                arr[i] = rnd.Next(0, 1000);
            }

            Console.WriteLine("Raw data:");
            foreach(var a in arr)
            {
                Console.Write(a + "\t");
            }

            int[] ascArr = BubbleSort(arr, true);
            Console.WriteLine("\n\n\nAsc order:");
            foreach(var a in ascArr)
            {
                Console.Write(a + "\t");
            }

            int[] descArr = BubbleSort(arr, false);
            Console.WriteLine("\n\n\nDesc order:");
            foreach(var a in descArr)
            {
                Console.Write(a + "\t");
            }
        }

        static int[] BubbleSort(int[] arr,bool isAsc)
        {
            if(arr==null && arr.Length==0)
            {
                return null;
            }
             
            for(int i=0;i<arr.Length;i++)
            {
                for(int j=i+1;j<arr.Length;j++)
                {
                    //Ascending
                    if(isAsc)
                    {
                        if(arr[i]>arr[j])
                        {
                            int temp = arr[i];
                            arr[i] = arr[j];
                            arr[j] = temp;
                        }
                    }
                    //Descending
                    else
                    {
                        if(arr[i]<arr[j])
                        {
                            int temp = arr[i];
                            arr[i] = arr[j];
                            arr[j] = temp;
                        }
                    }
                }
            }
            return arr;
        }

Insertion Sort List,Merge Two Sorted Lists,Sort List

Insertion Sort List
Sort a linked list using insertion sort.

1.解题思路

题目很简单，就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素，将其插入到前面已经排好序的元素中。
因为头结点没法确定，所以我们用一个dummy节点；然后开始向后逐个遍历，当前遍历的节点为cur,另外sortnode每次都指向已经排好序的第一个节点dummy,然后从dummy开始往后，直到找到sortnode.next.val>=cur.val,则表示cur节点要插到有序链表的sortnode后面。

2.代码

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        ListNode cur=head;
        while(cur!=null){
            ListNode sortnode=dummy;
            while(sortnode.next!=null&&sortnode.next.val<cur.val)
                sortnode=sortnode.next;
            ListNode tmp=cur.next;
            cur.next=sortnode.next;
            sortnode.next=cur;
            cur=tmp;
        }
        return dummy.next;
    }
}

Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

1.解题思路

合并两个有序链表，同样需要构造一个Dummy节点。
1）考虑特殊情况，如果有一个链表为空，则直接返回另一个链接；
2）利用两个指针p,q遍历两个链表,如果都不为空，则循环继续；
3）使用node指向新链表的最后一个节点，初始化为dummy
4) 比较p,q的数值的大小，如果p小于q,则把p加到node.next,并且node赋值为p,而p指针需要前进一个；
5) 结束循环时，check一下是否还有链表中有剩余元素，并将剩余元素加入到新链表node指针的后面。

2.代码

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val<q.val){
                node.next=p;
                node=p;
                p=p.next;
                
            }
            else {
                node.next=q;
                node=q;
                q=q.next;
            }
        }
        if(p!=null)
            node.next=p;
        if(q!=null)
            node.next=q;
        return dummy.next;
    }
}

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

1.解题思路

题目要求时间复杂度为O(n log n)，所以我们就想到用归并排序，自然就想到和上一题的mergeTwoLists。
但要做mergeTwoLists，必须得先将当前的list分割成两个List,所以采用递归实现。
要分割链表，最简单的办法就是找到中点，那很明显是利用slow,fast来实现，最后slow就是链表的中间点。但要注意我们要将Slow的前一个节点记录下来pre,在找到中点后，我们要将pre.next=null,这样链表才能分割成2个。
2.代码

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode slow=head,fast=head,pre=null;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        return mergeTwoSortedList(l1,l2);
    }
    private ListNode mergeTwoSortedList(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val<q.val){
                node.next=p;
                node=p;
                p=p.next;
                
            }
            else {
                node.next=q;
                node=q;
                q=q.next;
            }
        }
        if(p!=null)
            node.next=p;
        if(q!=null)
            node.next=q;
        return dummy.next;
    }
}

Insertion Sort 与 Merge Sort的性能比较(Java)

 1 　　 public static void main(String[] args)
 2     {
 3         Scanner input = new Scanner(System.in);
 4         int n = input.nextInt();
 5         int[] a = new int[n];
 6         
 7         //生成n个随机数
 8         for(int i = 0; i < n; i++)
 9             a[i] = (int)(Math.random() * 100);
10         
11         /*long start = System.currentTimeMillis();
12         InsertionSort(a);
13         long end = System.currentTimeMillis();*/
14         //100000个测试数据InsertionSort的排序时间约为2800ms
15             
16         /*System.out.println(Arrays.toString(a));
17         System.out.println(start);
18         System.out.println(end);
19         System.out.printf("The time is: %d", end - start);*/
20         
21         //获取当前时间(ms)
22         long start = System.currentTimeMillis();
23         divide(a, 0, a.length - 1);
24         long end = System.currentTimeMillis();
25         //100000000个测试数据MergeSort的排序时间约为12000ms 10000000个测试数据用时约为1200ms
26         //相对于平均时间复杂度O(n^2)的插入排序 随着测试数据数量级的增长 性能提升极大
27         
28         //System.out.println(Arrays.toString(a));
29         System.out.println(start);
30         System.out.println(end);
31         // end - start 即为排序算法运行的时间
32         System.out.println("The time is: " + (end - start));
33     }
34     
35     /*public static void InsertionSort(int[] a)
36     {
37         for(int i = 1; i < a.length; i++)
38         {
39             int key = a[i];
40             int j;
41             for(j = i - 1; j >= 0 && key < a[j]; j--)
42                 a[j + 1] = a[j];
43             a[j + 1] = key;
44         }
45     }*/
46     
47     public static void divide(int[] a, int front, int rear)
48     {
49         if(rear <= front)
50             return;
51         
52         int mid = front + (rear - front) / 2;
53         divide(a, mid + 1, rear);
54         divide(a, front, mid);
55         merge(a, front, mid, rear);
56     }
57     
58     public static void merge(int[] a, int front, int mid, int rear)
59     {
60         int[] b = new int[rear - front + 1];
61         int i = front, j = mid + 1, k = 0;
62         
63         while(i <= mid && j <= rear)
64             if(a[i] < a[j])
65                 b[k++] = a[i++];
66             else
67                 b[k++] = a[j++];
68         
69         if(i > mid)
70             while(j <= rear)
71                 b[k++] = a[j++];
72         else
73             while(i <= mid)
74                 b[k++] = a[i++];
75         
76         for(int t = 0, q = front; t < b.length; t++, ++q)
77             a[q] = b[t];
78     }

Insertion Sort，insertionsort

insertion sort，insertionsort

<span> 1</span> <?<span>php
</span><span> 2</span> <span>function</span> swap(&<span>$a</span>, &<span>$b</span><span>){
</span><span> 3</span>     <span>$c</span> = <span>$a</span><span>;
</span><span> 4</span>     <span>$a</span> = <span>$b</span><span>;
</span><span> 5</span>     <span>$b</span> = <span>$c</span><span>;
</span><span> 6</span> <span>}
</span><span> 7</span> 
<span> 8</span> <span>#</span><span> insertion sort</span>
<span> 9</span> <span>#</span><span> ascend</span>
<span>10</span> <span>function</span> sortInsertion(&<span>$a</span>){ <span>#</span><span> a is an array of numbers</span>
<span>11</span> 
<span>12</span>     <span>#</span><span> length of a</span>
<span>13</span>     <span>$m</span> = <span>count</span>(<span>$a</span><span>);
</span><span>14</span> 
<span>15</span>     <span>if</span>(<span>$m</span> < 2<span>){
</span><span>16</span>         <span>return</span><span>;
</span><span>17</span> <span>    }
</span><span>18</span> 
<span>19</span>     <span>#</span><span> for m numbers, we have m-1 numbers to insert</span>
<span>20</span>     <span>for</span>(<span>$i</span>=1; <span>$i</span><=<span>$m</span>-1; <span>$i</span>++<span>){
</span><span>21</span>         <span>for</span>(<span>$j</span>=<span>$i</span>; <span>$j</span>>0; <span>$j</span>--<span>){
</span><span>22</span>             <span>if</span>(<span>$a</span>[<span>$j</span>] < <span>$a</span>[<span>$j</span>-1<span>]){
</span><span>23</span>                 swap(<span>$a</span>[<span>$j</span>], <span>$a</span>[<span>$j</span>-1<span>]);
</span><span>24</span> <span>            }
</span><span>25</span> <span>        }
</span><span>26</span> <span>    }
</span><span>27</span> 
<span>28</span>     <span>return</span><span>;
</span><span>29</span> <span>}
</span><span>30</span> 
<span>31</span> <span>$arr</span> = <span>range</span>(5, 0<span>);
</span><span>32</span> sortInsertion(<span>$arr</span><span>);
</span><span>33</span> <span>echo</span> <span>implode</span>('', '', <span>$arr</span><span>);
</span><span>34</span> 
<span>35</span> <span>//</span><span> 0, 1, 2, 3, 4, 5</span>
<span>36</span> ?>

登录后复制

今天关于对于大小为n的输入，insert-sort是否击败了merge-sort的n值？[关闭]和当用大小为n的数组存储顺序循环队列时的介绍到此结束，谢谢您的阅读，有关C# bubble sort,selection sort,insertion sort、Insertion Sort List,Merge Two Sorted Lists,Sort List、Insertion Sort 与 Merge Sort的性能比较(Java)、Insertion Sort，insertionsort等更多相关知识的信息可以在本站进行查询。

本文标签：