선택 정렬 알고리즘의 JavaScript 구현 분석 예(그림)-JS 튜토리얼-php.cn

선택 정렬 알고리즘의 JavaScript 구현 분석 예(그림)

黄舟

풀어 주다： 2017-04-15 09:31:36

원래의

1860명이 탐색했습니다.

본 글에서는 JavaScript에서 구현한 선택 정렬 알고리즘을 주로 소개하며, 선택 정렬의 원리와 구현 단계, 관련 운용 기술을 예시 형태로 분석합니다. 다음

이 글의 예시는 자바스크립트로 구현된 선택 정렬 알고리즘을 설명합니다. 참고할 수 있도록 자세한 내용은 다음과 같습니다.

간단한 선택 정렬이 가장 친숙한 비교 방법입니다. 알고리즘 아이디어 from 배열 의 시작 부분부터 시작하여 첫 번째 요소를 다른 요소와 비교합니다. 모든 요소를 확인한 후 가장 작은 요소가 배열의 첫 번째 위치에 배치되고 알고리즘은 두 번째 위치부터 계속됩니다. 이 프로세스는 배열의 끝에서 두 번째 위치에 도달할 때까지 계속되며 모든 데이터가 정렬됩니다.

코드는 다음과 같습니다.

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
 function selectSort(nums){//选择排序
  var min;//最小值
  for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
     min=inner;//将其标为最小元素
    }//直到每次外循环的最小元素
    swap(nums,outer,min);//最小值被调整到合适的位置
   }
  }
 }
 function swap(arr,i,j){//交换位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//显示数组
  for(var i=0;i<nums.length;i++){
   document.write(nums[i]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 var nums=[6,8,0,6,7,4,3,5,5,10];
 show(nums);//6 8 0 6 7 4 3 5 5 10
 selectSort(nums);
 show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>

로그인 후 복사

분석 결과 단순 선택 정렬의 시간 복잡도는

O(n2)인 것으로 나타났습니다. 선택정렬의 주요 작업은 키워드 간의 비교이므로 단순 선택정렬의 개선은 비교를 줄이는 것부터 시작되어야 한다. 실제로 현실에서도 좋은 예가 있는데, 바로 게임의 종합우승이다. 8명 중에서 챔피언을 선택하는 데는 실제로 7+6+5=18게임이 필요하지 않으며, 11게임인 쌍별 비교를 통해 수행할 수 있습니다. 이 방법을 트리 선택 정렬이라고 합니다.

트리 선택 정렬은 토너먼트 아이디어를 바탕으로 한 선택 정렬 방법으로 먼저 n개 레코드의 키워드를 쌍으로 비교한 다음 n/2개를 비교합니다. 그런 다음 가장 작은 키워드가 발견될 때까지 더 작은 키워드를 쌍으로 비교합니다. n개의 노드를 포함하는 완전한 이진 트리의 깊이는 log2n+1이므로 하위 작은 키워드의 각 선택은 정렬 과정에서 log2n 연산만 필요하므로 시간 복잡도는 O (nlog2n) 하지만 이 정렬은 공간을 많이 차지한다는 단점이 있습니다.

그래서 더 나은 정렬, 즉

힙 정렬

을 소개해야 합니다.

첨부파일:

힙 정렬 알고리즘

힙 정렬

은 보조 레코드 크기 공간만 필요 , 정렬할 각 레코드는 하나의 저장 공간만 차지합니다. 힙 정렬은 큰 루트 힙(또는 작은 루트 힙)의 상단에 기록된 키가 가장 큰(또는 가장 작은) 특성을 활용하여 가장 큰(또는 가장 작은) 힙을 가진 레코드가 현재 정렬되지 않은 영역에서 선택한 키워드는 단순해야 합니다. 큰 힙을 예로 들어보겠습니다. 정렬의 기본 작업은 다음과 같습니다.

첫 번째는

힙을 구축

하는 것입니다. len2에서 시작하여 첫 번째 노드까지 계속됩니다. 여기서 len은 힙의 요소 수입니다. 힙을 만드는 과정은 선형 과정입니다. 힙을 조정하는 과정은 항상 len2에서 0으로 호출됩니다. 힙을 만드는 데 걸리는 시간 복잡도는 O(n)입니다. 다음은 조정 힙
입니다. 조정 힙은 힙 구축 및 힙 정렬 과정에서 사용됩니다. 아이디어는 노드 i와 해당 하위 노드 왼쪽(i)을 비교하는 것입니다. ) 및 오른쪽(i), 세 개 중 가장 큰(또는 가장 작은) 값을 선택합니다. 가장 큰(가장 작은) 값이 노드 i가 아니라 해당 하위 노드 중 하나인 경우 두 노드를 교환하고 계속합니다. 🎜>재귀. 그런 다음 힙 정렬:
힙의 루트 노드를 꺼내고 루트 노드를 마지막 요소로 교체한 다음 첫 번째 len-1 노드로 힙 조정 프로세스를 계속합니다. 그런 다음 모든 노드가 제거될 때까지 루트 노드를 제거하는 방법에 대해 이야기합니다. 힙 조정의 시간 복잡도는 O(log2n)그래서 힙 정렬의 시간 복잡도는 O(nlog2n)입니다. 힙 정렬은 내부 정렬이며 보조 공간은 O(1)입니다. 하지만 불안정합니다(정렬의 안정성은 정렬된 순서에 두 개의 동일한 요소가 있는 경우 정렬 전후의 상대적 위치가 변경되지 않음을 의미합니다).
다음은 힙 구축 과정을 시뮬레이션합니다.