JAVA 단순 선택 정렬 알고리즘 원리 및 구현-java지도 시간-php.cn

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

高洛峰

풀어 주다： 2017-01-17 13:08:35

원래의

2211명이 탐색했습니다.

간단한 선택 정렬: (가장 작은 값을 선택하여 먼저 넣은 다음 첫 번째 값을 뒤로 이동하는 등) 첫 번째 값을 다음 값과 하나씩 비교하고 가장 작은 값을 맨 위에 놓습니다. 비트가 뒤로 밀려납니다(즉, 방금 선택한 첫 번째 비트가 최소값이므로 더 이상 비교에 포함되지 않으며 비교 횟수가 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);
 }
}

로그인 후 복사

단순 선택 정렬:

단순 선택 정렬은 버블 정렬과 유사하며 항상 아래 요소 집합에서 가장 높은 값을 선택합니다. 현재 위치에 채우세요. 유일한 차이점은 버블 정렬은 현재 값보다 작거나 큰 것을 발견할 때마다 요소의 위치를 교환하는 반면, 단순 선택 정렬은 나머지 요소 중에서 가장 높은 값을 선택하여 현재 값과 데이터를 교환한다는 것입니다. 위치.

　예를 들어 요소 집합 R={37, 40, 38, 42, 461, 5, 7, 9, 12}

　첫 번째 정렬 패스에서 37이 직접 교환됩니다. 5를 사용하여 새 시퀀스 R1={5,40,38,42,461,37,7,9,12}
두 번째 정렬에서 40을 7과 직접 교환하여 새 시퀀스 R2={5, 7, 38,42,461,37,40,9,12}

등을 마지막 요소까지 계속합니다(참고: 두 번째 정렬 단계에서는 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;
　　}
　　}

로그인 후 복사

는 새 세트에서 최소값의 재귀적 구성을 구현합니다.

JAVA 단순 선택 정렬 알고리즘의 원리 및 구현과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!