JAVA 단순 선택 정렬 알고리즘 원리 및 실현

단순 선택 정렬: (최소값을 선택하여 첫 번째 자리에 놓고 첫 번째 자리가 뒤로 이동하는 순환) 첫 번째 자리와 뒤에 있는 모든 것을 하나하나 비교하고 매번 가장 작은 것을 꼭대기에 놓고 첫 번째 자리는 뒤로 밀어붙인다(즉, 방금 선택한 첫 번째 자리는 최소값이고 더 이상 비교에 참여하지 않으며 비교 횟수는 1)
복잡도: 기록 이동에 필요한 조작 횟수가 0-3(n-1)보다 적고 기록의 초기 배열이 어떻든 필요한 키워드 간의 비교 횟수가 같으며 모두 n(n-1)/2이고 전체 시간 복잡도는 O(n2)이다.공간 복잡도 O (1)
알고리즘 개선: 매번 비교할 때마다 가장 작은 값을 첫 번째로 하기 때문에 끝까지 비교하여 가장 작은 값을 찾아내고 직접 첫 번째로 하여 무의미한 변환 이동 조작을 줄일 수 있다.방향을 바꿀 수도 있다. 마지막 한 분과 앞의 한 분을 비교하고 매번 최대치를 바닥에 가라앉히고 마지막 한 분을 앞으로 밀어붙인다.
JAVA 소스 코드:

 public static void selectSort(Date[] days) {
  int min;
  Date temp;
  for (int i = 0; i < days.length; i++) {
   min = i;
   for (int j = min + 1; j < days.length; j++) {
    if (days[min].compare(days[j]) > 0) {
     min = j;
    }
   }
   if (min != i) {
    temp = days[i];
    days[i] = days[min];
    days[min] = temp;
   }
  }
 }
class Date {
 int year, month, day;
 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }
 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }
 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}

단순 선택 정렬(Simple Selection Sort): 단순 선택 정렬은 거품 정렬(Bubble Sort)과 유사하며, 매번 나머지 요소 집합 중 가장 높은 값을 선택하여 현재 위치로 채웁니다.유일한 차이점은 거품 정렬은 현재 값보다 작거나 큰 것을 발견할 때마다 원소의 위치를 교환하고, 간단한 정렬 선택은 나머지 원소 중 가장 큰 값과 현재 위치를 선택하여 데이터를 교환하는 것이다.예를 들어 원소 집합에 대한 R={37, 40, 38, 42, 461, 5, 7, 9, 12} 첫 번째 순서에서: 37과 5를 직접 교환하고 새로운 서열을 형성한다. R1={5, 40, 38, 42461, 37, 7, 9, 12} 두 번째 순서에서: 40과 7을 직접 교환하고 새로운 서열을 형성한다.마지막 원소까지 (주의: 두 번째 정렬에서 38대 42는 작지만 데이터를 교환하지 않았습니다.)다음은 정렬을 간단하게 선택한 Java 구현 버전입니다.

　　public static void selectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int i, j, value, minPos, len = data.length;
　　int outer = len - 1, tmp;
　　for （i = 0; i < outer; i++） {
　　value = data[i];
　　minPos = -1;
　　for （j = i + 1; j < len; j++） {
　　if （data[j] < value） {
　　minPos = j;
　　value = data[j];
　　}
　　}
　　if （minPos != -1） {
　　tmp = data[i];
　　data[i] = value;
　　data[minPos] = tmp;
　　}
　　//            for （int k = 0; k < len; k++） {
　　//                System.out.print（data[k] + " , "）；
　　//            }
　　//            System.out.println（）；
　　}
　　}
　　public static void main（String[] args） {
　　int[] coll = {
　　37, 40, 38, 42, 461, 5,  7, 9, 12
　　};
　　selectionSort（coll）；
　　for （int i = 0; i < coll.length; i++） {
　　System.out.print（coll[i] + " , "）；
　　}
　　}

트리 선택 정렬(Tree Selection Sort) 트리 선택 정렬 알고리즘은 간단한 정렬 선택에 비해 공간을 시간으로 바꾸는 전형적인 알고리즘이다.그 사상은 정렬된 N개의 원소를 대상으로 상대적으로 작은 (n+1)/2개의 수를 구성한 다음에 상대적으로 작은 [n+1]/4개의 수를 구성하여 하나의 원소만 있을 때까지 하는 것이다.완전 두 갈래 나무로 만들어졌다.정렬할 때 그 원소는 가장 작은 것이다. 이 가장 작은 원소를 꺼내서 이 원소를'최대치'로 바꾸고 완전한 두 갈래 나무를 조정한다.다음은 트리 선택 정렬의 Java 구현 버전입니다.

　　public static void treeSelectionSort（int[] data） {
　　if （data == null || data.length <= 1）
　　return;
　　int len = data.length , low = 0 , i , j;
　　// add Auxiliary Space
　　int[] tmp = new int[2*len -1];
　　int tSize = tmp.length;
　　//construct a tree
　　for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{
　　tmp[j]=data[i];
　　}
　　for（i = tSize -1 ; i > 0 ; i-=2）{
　　tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
　　}
　　//end
　　//remove the minimum node.
　　while（low < len）{
　　data[low++] = tmp[0];
　　for（j=tSize-1;tmp[j]!=tmp[0];j--）；
　　tmp[j] = Integer.MAX_VALUE;
　　while（j > 0）{
　　if（j%2 == 0）{  // 
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  // 
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}
　　}
　　}

완전 두 갈래 나무를 구성할 때 N개의 원소에 대한 집합은 2*N-1개의 보조 공간이 필요하다.코드:

　　while（j > 0）{
　　if（j%2 == 0）{  // 
　　tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j = （j-1）/2;
　　}else{  // 
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}

귀속된 구조의 새로운 집합 중 최소값을 실현합니다.