C# insertion sort

C# , insertion sort

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class InsertSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            InsertSort(a);  
            return a;  
        }  
        private static void InsertSort(int[] myArray)  
        {  
           int i, j,temp;            for (i = 1; i < myArray.Length; i++)  
            {  
                temp = myArray[i];//保存当前数据，当前数据即待插入的数据          
                //将数组标号i及i之前的元素，排成递增序列  
                for (j = i - 1; j >= 0 && myArray[j] >temp; j--)  
                {  
                    myArray[j + 1] = myArray[j];                 
                }  
                myArray[j + 1] = temp;  
            }  
     }  
  
    }  
}

Example 1:

Keyword sequence T=(13, 6, 3, 31, 9, 27, 5, 11) Please write the intermediate process sequence of direct insertion sort.

【13】, 6, 3, 31, 9, 27, 5, 11

【6, 13】, 3, 31, 9, 27, 5, 11

【3, 6, 13】, 31, 9, 27, 5, 11

【3, 6, 13, 31】, 9, 27, 5, 11

【3 , 6, 9, 13, 31】, 27, 5, 11

【3, 6, 9, 13，27, 31】, 5, 11

【3, 5, 6 , 9, 13, 27, 31】, 11

【3, 5, 6, 9, 11, 13, 27, 31】

Small note: Each small loop only arranges the array The order of these elements from 0 to i (similar to bubbling)

Example 2:

Example 3:

In the worst case, the array is completely in reverse order. When inserting the second element, the previous element must be considered. When inserting the third element, the previous element must be considered. 2 elements,..., to insert the Nth element, the first N - 1 elements must be considered. Therefore, the number of comparisons in the worst case is 1 + 2 + 3 + ... + (N - 1), and the arithmetic sequence is summed, and the result is N^2 / 2, so the complexity in the worst case is O (N^2).

In the best case, the array is already ordered. Every time an element is inserted, only the previous element needs to be examined. Therefore, in the best case, the time complexity of insertion sort is O(N).

The space complexity of insertion sort is O(1), because during insertion sort, you only need to use an extra space to store the "taken out" element, so insertion sort only requires additional A space for sorting.

Space Complexity is a measure of the amount of storage space an algorithm temporarily occupies during operation.

Since the array is sorted internally, the relative order can be kept unchanged by comparing and moving the subsequent parts bit by bit in order, so insertion sort is a stable sorting algorithm.

The above is the content of C# insertion sort. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!