상용 정렬 알고리즘 구현 정렬 (Insertion Sort)

1503 단어 알고리즘일 하 다J#
정렬 (Insertion Sort) 을 삽입 하 는 알고리즘 설명 은 간단 하고 직관 적 인 정렬 알고리즘 입 니 다.그것 의 작업 원 리 는 질서 있 는 서열 을 구축 하여 정렬 되 지 않 은 데이터 에 대해 정렬 된 서열 에서 뒤로 스 캔 하여 해당 하 는 위 치 를 찾 아 삽입 하 는 것 이다.삽입 정렬 은 실현 에 있어 서 보통 in - place 정렬 (즉, O (1) 의 추가 공간 으로 만 정렬) 을 사용 하기 때문에 뒤에서 앞으로 스 캔 하 는 과정 에서 정렬 된 요 소 를 점차적으로 뒤로 옮 겨 최신 요소 에 삽입 공간 을 제공 해 야 합 니 다.알고리즘 설명 은 일반적으로 삽입 정렬 은 in - place 로 배열 에서 이 루어 집 니 다.구체 적 인 알고리즘 설명 은 다음 과 같다. 1. 첫 번 째 요소 부터 이 요 소 는 정렬 되 었 다 고 볼 수 있다.정렬 된 요소 가 새 요소 보다 작 거나 같은 위 치 를 찾 을 때 까지 5. 새 요 소 를 이 위치 에 삽입 합 니 다. 6. 반복 단계 2
 
예제 코드
  
void InsertSort(int array[], int length)
{
　　　 int i, j, key;

　　　 for (i = 1; i < length; i++)
　　　 {
　　　　　　　 key = array[i];
　　　　　　　 //  i    array[i]       
　　　　　　　 for (j = i - 1; j >= 0 && array[j] > key; j--)
　　　　　　　 {
　　　　　　　　　　　 array[j + 1] = array[j];
　　　　　　　 }
　　　　　　　 //            
　　　　　　　 array[j + 1] = key;
　　　 }
}

 
 알고리즘 복잡 도
 
만약 에 목표 가 n 개 요소 의 서열 을 정렬 하 는 것 이 라면 삽입 정렬 을 사용 하 는 것 이 가장 좋 은 상황 과 최 악의 상황 이 존재 합 니 다.가장 좋 은 상황 은 서열 이 이미 오름차 순 으로 배열 되 었 다 는 것 이다. 이런 상황 에서 진행 해 야 할 비교 작업 은 (n - 1) 회 만 있 으 면 된다.최 악의 경우 서열 이 내림차 순 으로 배열 되 어 있 으 면 이때 진행 해 야 할 비 교 는 모두 n (n - 1) / 2 회 이다.정렬 을 삽입 하 는 할당 작업 은 비교 작업 횟수 에 (n - 1) 회 입 니 다.평균 적 으로 정렬 알고리즘 을 삽입 하 는 복잡 도 는 O (n2) 이다.따라서 삽입 정렬 은 데이터 양 이 많은 정렬 에 적합 하지 않다.그러나 정렬 이 필요 한 데 이 터 는 양 이 적 습 니 다. 예 를 들 어 양 이 천 보다 적 으 면 정렬 을 삽입 하 는 것 이 좋 습 니 다.
REST API 녹 슬림 + 휨 2: POST
푸 시 알고리즘 1

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage