Java 정렬 알고리즘 요약 선택 정렬

2465 단어 Java정렬 선택
본고는 자바 정렬 알고리즘의 요약된 선택 정렬을 실례로 다루고 있다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적인 분석은 다음과 같다.
정렬을 선택하는 기본적인 작업은 정렬을 기다리는 데이터 요소 중에서 가장 작은 (또는 가장 큰) 요소를 선택하는 것이다. 정렬을 기다리는 모든 데이터 요소가 다 정렬될 때까지 정렬된 수열의 마지막에 순서를 놓는다.알고리즘이 불안정하고 O(1)의 추가 공간은 비교 시간의 복잡도는 O(n^2)이며 교환 시간의 복잡도는 O(n)이며 스스로 적응하는 것이 아니다.대부분의 경우 사용을 권장하지 않습니다.교환 횟수를 줄이고 싶은 경우에만 사용할 수 있다.
 
기본 사상
 
n개의 기록된 파일의 직접 선택 정렬은 n-1번의 직접 선택 정렬을 통해 질서정연한 결과를 얻을 수 있습니다.
① 초기 상태: 무질서 영역은 R[1.n]이고 질서 영역은 비어 있습니다.
② 1차 정렬
무질서 구역 R[1.n]에서 키워드가 가장 작은 기록 R[k]을 선택하여 무질서 구역의 첫 번째 기록 R[1]과 교환하여 R[1..1]과 R[2.n]을 각각 기록 개수 1개 증가의 새로운 질서 구역과 기록 개수 1개 감소의 새로운 무질서 구역으로 변경한다.
……
③ i회 정렬
i번 정렬이 시작되었을 때 현재 질서 구역과 무질서 구역은 각각 R[1.i-1]과 R(1≤i≤n-1)이다.이번 정렬은 현재 무질서 구역에서 키워드가 가장 작은 기록 R[k]을 선택하여 무질서 구역의 첫 번째 기록 R과 교환하여 R[1.i]와 R을 각각 기록 개수 증가 1개의 새로운 질서 구역과 기록 개수 감소 1개의 새로운 무질서 구역으로 변경합니다.
이렇게 하면 n개의 기록된 파일의 직접 선택 정렬은 n-1번의 직접 선택 정렬을 통해 질서정연한 결과를 얻을 수 있다.
 
코드 구현

public class Test { 
  public static int[] a = {10,32,1,9,5,7,12,0,4,3};
  //   
  public static void main(String args[]) { 
    int i; //   
    int Index = a.length;//   
    System.out.print(" : "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s", a); 
    System.out.println(""); 
    SelectSort(Index - 1); //   
    //   
    System.out.print(" : "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s", a); 
    System.out.println(""); 
  } 
  public static void SelectSort(int Index) { 
    int i, j, k; //   
    int MinValue; //   
    int IndexMin; //   
    int Temp; //   
    for (i = 0; i < Index - 1; i++) { 
      MinValue = 32767;//   
      IndexMin = 0; //   
      for (j = i; j < Index; j++) { 
        if (a[j] < MinValue) //   
        { 
          MinValue = a[j]; //   
          IndexMin = j; 
        } 
        Temp = a; //   
        a = a; 
        a = Temp; 
      } 
      System.out.print(" : "); 
      for (k = 0; k < Index; k++) 
        System.out.printf("%3s", a[k]); 
      System.out.println(""); 
    } 
  } 
}
선택 정렬법은 거품 정렬법과 마찬가지로 가장 바깥쪽 순환은 n-1회를 실행해야 하는데 그 효율은 여전히 비교적 떨어진다.
본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.

좋은 웹페이지 즐겨찾기