정렬의 효율성은 일반적으로 데이터 비교 횟수, 데이터 이동 횟수, 메모리 점유 공간의 세 가지 측면에서 비교됩니다.
버블정렬, 선택정렬, 삽입정렬, 퀵정렬의 일반적인 비교를 해보겠습니다. 버블 정렬 알고리즘은 여러 정렬 알고리즘 중 비교 횟수와 이동 횟수가 가장 많기 때문에 일반적으로 사용되지 않습니다. 유일한 장점은 알고리즘이 간단하고 이해하기 쉬워서 데이터의 양이 적을 때 사용할 수 있다는 것입니다. 일부 응용 프로그램 값이 될 것입니다. 선택 정렬은 n제곱인 버블 정렬과 비교 횟수는 동일하지만 교환 횟수를 최소한으로 줄여 데이터의 양이 적고 데이터 교환이 비교보다 시간이 많이 걸리는 경우에 적용할 수 있습니다. 데이터를 선택하세요.
대부분의 경우 데이터의 양이 상대적으로 적거나 기본적으로 정렬된 경우 삽입 정렬 알고리즘이 최선의 선택입니다. 더 많은 양의 데이터를 정렬하려면 일반적으로 퀵 정렬이 가장 좋은 방법입니다.
위의 정렬 알고리즘은 메모리 공간을 거의 차지하지 않으며 교환 중에 데이터 항목을 임시로 저장하기 위한 추가 변수만 필요합니다. 따라서 차지하는 메모리 공간의 크기는 비교가 되지 않습니다.
삽입 정렬의 비교 횟수는 여전히 n제곱이지만 일반적으로 버블 정렬보다 두 배 빠르고 선택 정렬보다 약간 빠릅니다. 이는 퀵 정렬과 같은 복잡한 정렬 알고리즘의 마지막 단계에서 자주 사용됩니다.
알고리즘: i-1 처리 후 L[1..i-1]이 정렬되었습니다. i번째 패스는 L[i]를 L[1..i-1]의 적절한 위치에 삽입하기만 합니다.
따라서 L[1..i]는 다시 순서가 지정된 시퀀스입니다. 이 목표를 달성하기 위해 순차적 비교를 사용할 수 있습니다.
먼저 L[i]와 L[i-1]을 비교합니다. L[i-1]<=L[i]이면 L[1..i]가 정렬되고 i번째 처리 단계가 종료됩니다.
그렇지 않으면 L[i]와 L[i-1]의 위치를 교환하고 특정 위치 j(1≤j≤i-1)가 될 때까지 L[i-1]과 L[i-2]를 계속 비교합니다. 설립하다.
L[j] ≤L[j+1]까지
장점: 이동되는 요소 수가 적고 보조 공간만 필요합니다.
시간복잡도 n*n
정렬할 레코드 수가 n개일 때 좋은 정렬 방법입니다. 그러나 n이 매우 크면 부적절합니다.
예: int[] 값 = { 5, 2, 4, 1, 3 };
정렬 과정:
첫 번째: 2,5,4,1,3
두 번째: 2,4,5,1,3
세 번째: 1,2,4,5,3
네 번째: 1,2,3,4,5
자바 코드:
다음과 같이 코드 코드를 복사합니다.
공개 클래스 InsertSort {
공개 정적 무효 메인(String[] args) {
int[] 값 = { 5, 2, 4, 1, 3 };
sort(값);
for (int i = 0; i < 값.길이; ++i) {
System.out.println(값[i]);
}
}
공개 정적 무효 정렬(int[] 값) {
내부 온도;
정수 j = 0;
for (int i = 1; i < value.length; i++) {
if(values[i]<values[i-1])//여기에서의 판단은 매우 중요합니다. 이는 삽입 정렬이 버블 정렬 및 선택 정렬보다 빠른 이유를 반영합니다.
{
온도 = 값[i];
//데이터를 뒤로 이동
for (j=i-1; j>=0 && 임시<값[j]; j--)
{
값[j+1] =값[j];
}
//j+1 위치에 데이터를 삽입합니다.
값[j+1] =온도;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k < 값.길이; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
두 번째 예
다음과 같이 코드 코드를 복사합니다.
패키지 cn.cqu.coce.xutao;
공개 클래스 zhijiecharu {
공개 정적 무효 메인(문자열 인수[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
if(a[i]>a[j])
부서지다;
if(j!=i-1){
내부 온도;
온도=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=온도;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}