C# 삽입 정렬

C#, 삽입 정렬

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;  
            }  
     }  
  
    }  
}

예 1:

키워드 시퀀스 T=(13, 6, 3, 31, 9, 27, 5 , 11) 직접 삽입 정렬의 중간 과정 순서를 적어주세요.

【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】

참고 사항: 각 배열만 배열됩니다. 작은 루프 0부터 i까지 요소의 순서(버블링과 유사)

예 2:

예 3:

최악의 경우 두 번째 요소를 삽입할 때 배열이 완전히 역순으로 바뀌고, 세 번째 요소를 삽입할 때는 반드시 이전 요소를 고려해야 합니다. 요소의 경우 이전 요소를 고려해야 합니다. 2개 요소,..., N번째 요소를 삽입하려면 첫 번째 N - 1개의 요소를 고려해야 합니다. 따라서 최악의 경우 비교횟수는 1+2+3+...+(N-1)이 되고, 연산수열을 더해 결과는 N^2/2가 되므로 최악의 경우에는 복잡도가 경우는 O(N^2)입니다.

최상의 경우에는 배열이 이미 정렬되어 있으므로 요소를 삽입할 때마다 이전 요소만 검사하면 됩니다. 따라서 가장 좋은 경우에는 삽입 정렬의 시간 복잡도가 O(N)입니다. ).

삽입 정렬의 공간 복잡도는 O(1)입니다. 삽입 정렬 중에 "꺼낸" 요소를 저장하기 위해 추가 공간만 사용하면 되므로 삽입 정렬에는 정렬을 위한 추가 A 공간만 필요하기 때문입니다. .

공간 복잡도는 알고리즘이 작동하는 동안 일시적으로 차지하는 저장 공간의 양을 측정한 것입니다.

배열은 내부적으로 정렬되어 있기 때문에 다음 부분을 비트 단위로 비교하고 이동시키면 상대적인 순서가 변하지 않고 유지될 수 있으므로 삽입 정렬은 안정적인 정렬 알고리즘입니다.

위는 C# 삽입 정렬 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!