자바 삽입 정렬 구현 예에 대한 자세한 설명

본 글은 주로 자바 데이터 구조와 알고리즘 삽입정렬을 소개하고, 자바 삽입정렬의 개념, 분류, 원리, 구현방법, 관련 주의사항 등을 예시 형태로 분석하여 도움이 필요한 친구들이 참고할 수 있습니다

이 기사의 예제에서는 Java 데이터 구조 및 알고리즘의 삽입 정렬을 설명합니다. 참고하시라고 자세한 내용은 다음과 같습니다.

정렬에 관한 지식을 검토한 후 더 많은 분들과 공유하고 싶어서 적어보았습니다. 가장 중요한 것은 나중에 참조할 수 있도록 백업을 만들어 두는 것입니다.

정렬

1. 개념:

n개의 레코드가 있는 시퀀스 {R1, R2, .......,Rn}(여기서 참고: 1,2,n은 아래 표의 시퀀스이며 다음은 동일한 효과를 갖습니다.) 해당 키워드의 시퀀스는 {K1,K2,. ... .....,켄}. 정렬을 통해 현재 첨자 시퀀스 1,2,...,n의 배열 p1, p2,...pn을 찾아야 하며, 해당 키워드는 다음과 같은 비감소(비증가) 관계를 만족해야 합니다. 즉, Kp1

2. 분류

정렬은 정렬 시 데이터가 차지하는 메모리의 차이에 따라 두 가지로 나눌 수 있습니다.

내부 정렬: 전체 정렬 과정은 다음과 같이 완전히 메모리에서 수행됩니다.

삽입 정렬(직접 삽입 정렬, 반 삽입 정렬, 힐 정렬) ; 🎜>선택 정렬, 트리 선택 정렬, 힙 정렬)

병합 정렬

할당 정렬(다중 키) 단어 정렬, 연결 기수 정렬, 기수 정렬의 시퀀스 테이블 구현));

외부 정렬: 정렬해야 할 레코드 데이터의 양이 많아 메모리를 확보할 수 없습니다. 모든 데이터를 수용하려면 외부 저장 장치를 사용해야 합니다(

디스크 정렬, 테이프 정렬

).

3. 안정성

정렬할 순서에 동일한 키워드를 가진 레코드가 여러 개 있다고 가정합니다. Ki=Kj(1<=i<=n,1<=j<=n,i != j)라고 가정하고, 정렬 전에 Ri가 Rj(즉, i

삽입 정렬: 아이디어: 정렬할 레코드를 키 크기에 따라 이전에 정렬된 하위 파일의 적절한 위치에 삽입할 때마다 모든 레코드가 완료될 때까지 삽입됩니다. .

직접 삽입 정렬:

알고리즘 아이디어: 정렬할 레코드가

배열

R에 저장되어 있다고 가정 [1..n] 인치 처음에는 R[1]이 정렬된 영역을 형성하고, 정렬되지 않은 영역은 R[2..n]입니다. i=2부터 i=n까지 ​​R[i]를 현재 정렬된 영역 R[1..i-1]에 순차적으로 삽입하여 n개의 레코드를 포함하는 정렬된 영역을 생성합니다.

Java에서 구현한 코드는 다음과 같습니다.

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

알고리즘 분석:

가장 좋은 경우는 정렬할 레코드를 단어가 순서대로 정렬되었습니다. 최악의 경우 정렬할 레코드가 키워드에 따라 역순으로 정렬됩니다.

시간 복잡도는 O(N^2; ), 공간 복잡도는 O(1)입니다.

이 알고리즘은 안정적인 정렬 알고리즘입니다.

정렬할 레코드 수가 적고 기본적으로 순서가 맞는 상황에 더 적합합니다

.

반 삽입 정렬: 알고리즘 아이디어: 정렬된 테이블에 대한 절반 검색 성능이 순차 검색보다 좋습니다. 알고리즘 구현 코드는 다음과 같습니다.

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

알고리즘 분석: 는 안정적인 정렬 알고리즘으로 비용이 훨씬 저렴합니다. 직접 삽입 알고리즘보다 키워드 간 비교 횟수가 줄어들어 가 직접 삽입 정렬 알고리즘

보다 빠르지만 레코드 이동 횟수는 변하지 않으므로

시간 복잡도 절반 삽입 정렬 알고리즘은 여전히 ​​O(n^2)이고,

은 직접 삽입 정렬 알고리즘과 동일합니다.

추가공간 O(1).

【관련 추천】1. 특별 추천: "php "Programmer Toolbox" V0.1 버전 다운로드

2. Java 무료 동영상 튜토리얼

YMP 온라인 매뉴얼

위 내용은 자바 삽입 정렬 구현 예에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!