Java 정렬 알고리즘 요약 삽입 정렬
이미 질서정연한 데이터 시퀀스가 있습니다. 이 배열된 데이터 시퀀스에 하나의 수를 삽입해야 하지만, 삽입된 데이터 시퀀스는 여전히 질서정연합니다. 이때 삽입 정렬법을 사용해야 합니다.본고는 주로 정렬을 삽입한java의 실현을 소개한다.
정렬을 삽입하는 기본적인 작업은 하나의 데이터를 이미 정렬된 질서 있는 데이터에 삽입하여 새로운, 개수에 하나를 더한 질서 있는 데이터를 얻는 것이다.비교와 교환의 시간 복잡도는 O(n^2)이고 알고리즘은 스스로 적응하며 데이터가 기본적으로 질서정연한 상황에 대해 시간 복잡도는 O(n)이며 알고리즘이 안정적이고 비용이 적다.알고리즘은 데이터가 이미 기본적으로 질서정연하거나 데이터 양이 적은 상황에 적합하다.
삽입 알고리즘은 정렬할 그룹을 두 부분으로 나눈다. 첫 번째 부분은 이 그룹의 모든 요소를 포함하지만, 마지막 원소를 제외하고, 두 번째 부분은 이 원소만 포함한다.첫 번째 부분을 정렬한 후에 이 마지막 요소를 현재 질서정연한 첫 번째 부분에 삽입합니다.
알고리즘 설명
일반적으로 삽입 정렬은 in-place를 사용하여 수조에서 이루어진다.구체적인 알고리즘은 다음과 같습니다.
1. 첫 번째 원소부터 이 원소는 이미 정렬되었다고 생각할 수 있다
2. 다음 요소를 추출하여 정렬된 요소 시퀀스에서 뒤로 스캔
3. 요소(정렬됨)가 새 요소보다 크면 다음 위치로 이동합니다.
4. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다.
5. 새 요소를 다음 위치에 삽입
6. 2단계 반복
만약 비교 조작의 대가가 교환 조작보다 크다면 이분 검색법으로 비교 조작의 수를 줄일 수 있다.이 알고리즘은 정렬을 삽입하는 변종으로 2분 찾기 정렬이라고 할 수 있다.
코드 구현
public void insertionSort() {
//
int out, in;
int count1 = 0, count2 = 0;// ，
for (out = 1; out < nElems; out++) {
long temp = a[out];
in = out;
boolean flag=in>0&&a[in-1]>=temp;
while(flag){
if(a[in-1]>=temp){
if(in>0){
a[in]=a[in-1];
count1++;
--in;
}
}
count2++;
flag=in>0&&a[in-1]>=temp;
}
a[in] = temp;
}
System.out.println(" ：" + count1 + " ：" + count2);
}본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
