수색…
비고
정렬 알고리즘의 성능을 분석 할 때 주로 비교 및 교환 횟수에 관심이 있습니다.
평균 거래
E n 을 N 개의 원소의 배열을 정렬하기위한 전체 평균 교환 횟수 라하자. E 1 = 0 (우리는 하나의 원소로 배열을 교환 할 필요가 없다). N 개의 요소 배열을 정렬하기위한 교환 평균 수는 N-1 요소 배열에 마지막 요소를 삽입하기 위해 평균 교환을 사용하여 N-1 요소 배열을 정렬하는 평균 교환 수의 합입니다.
합계 단순화 (산술 시리즈)
용어 확장
합계를 다시 단순화 (산술 시리즈)
평균 비교
C n 을 N 요소 배열을 정렬하기위한 총 비교 평균 수로 보자. C 1 = 0 (요소 배열 하나에 비교할 필요 없음). N 개의 요소 배열을 정렬하는 평균 비교 수는 N-1 개의 요소 배열에 마지막 요소를 삽입하기 위해 평균 비교를 사용하여 N-1 개의 요소 배열을 정렬하는 평균 비교 수의 합입니다. 마지막 요소가 가장 큰 요소 인 경우 하나의 비교 만 필요합니다. 마지막 요소가 두 번째로 작은 요소이면 N-1 비교가 필요합니다. 그러나 마지막 요소가 가장 작은 요소 인 경우 N 비교가 필요하지 않습니다. 우리는 여전히 N-1 비교 만 필요합니다. 그래서 아래 방정식에서 1 / N을 제거하는 것입니다.
합계 단순화 (산술 시리즈)
용어 확장
합계를 다시 단순화하십시오 (산술 시리즈 및 고조파 번호)
알고리즘 기초
삽입 정렬은 매우 간단하고 안정적인 장소 정렬 알고리즘입니다. 작은 시퀀스에서는 잘 수행되지만 큰 목록에서는 효율성이 떨어집니다. 모든 단계에서 알고리즘은 주어진 시퀀스의 i 번째 요소를 고려하여 올바른 위치에 올 때까지 왼쪽으로 이동합니다.
그래픽 일러스트레이션
의사 코드
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
예
다음 정수 목록을 고려하십시오.
[5, 2, 4, 6, 1, 3]
알고리즘은 다음 단계를 수행합니다.
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
C # 구현
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
보조 공간 : O(1)
시간 복잡성 : O(n)
하스켈 구현
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs