Java 데이터 구조 정렬 알고리즘 (3) 단순 선택 정렬

이 글은 주로 Java 데이터 구조와 알고리즘선택 정렬의 단순성을 소개하고, 선택 정렬의 원리, 구현 방법 및 관련 작업 기술을 예제 형식으로 분석합니다. 도움이 필요한 친구들이 참고할 수 있습니다

이 글은 설명합니다. 예제가 포함된 Java 데이터 단순 선택 정렬의 구조 및 알고리즘. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

이전 기사에서 이미 교환 클래스의 정렬 알고리즘에 대해 설명했습니다. 이 섹션에서는 선택 클래스의 정렬 알고리즘에 대해 이야기하기 시작합니다. .먼저 선택 정렬의 알고리즘 아이디어를 살펴보겠습니다.

선택 정렬의 기본 알고리즘 아이디어:

각 패스에서 n-i 중에서 가장 작은 키워드가 있는 레코드를 선택합니다. +1(i=1,2,3,...,n-1)은 시퀀스의 i번째 레코드로 기록됩니다.

간단한 선택 정렬:

정렬된 시퀀스의 레코드 수가 n개라고 가정합니다. i는 1,2,…,n-1을 취하여 모든 n-i+1개 레코드(Ri, Ri+1,…,Rn) 중에서 정렬 코드가 가장 작은 레코드를 찾아 i번째 레코드와 교환합니다. n-1번 실행하면 레코드 순서 정렬이 완료됩니다.

알고리즘 구현 코드는 다음과 같습니다.

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

알고리즘 분석:

이 정렬 과정에서 이동해야 하는 레코드의 개수는 상대적으로 적습니다. 가장 좋은 경우, 즉 정렬할 레코드의 초기 상태는 이미 양의 순서이므로 최악의 경우에는 레코드를 이동할 필요가 없습니다. 즉, 정렬할 레코드의 초기 상태는 다음과 같습니다. 역순으로 말하면 필요한 최대 이동 수는 3(n-1)입니다. 정렬 과정에서 필요한 비교 횟수는 초기 상태에서 정렬할 레코드 순서의 배열과 아무런 관련이 없습니다. i=1이면 n-1개의 비교가 필요하고, i=n이면 ​​필요한 총 비교 횟수는 n(n-1)/2입니다. 즉, 비교 작업의 시간 복잡도는 O( n^ 2) 이동 작업의 시간 복잡도는 O(n)입니다. 이 정렬은 불안정한 정렬입니다.

【관련 추천】

1. java 데이터 구조 정렬 알고리즘(1) 트리 선택 정렬

2. java 데이터 구조 정렬 알고리즘(2) 병합 정렬

3. Java(Selection Sort_java) 예제 튜토리얼

4.

java 데이터 구조 정렬 알고리즘(4) 선택 정렬

위 내용은 Java 데이터 구조 정렬 알고리즘 (3) 단순 선택 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!