JS 에 따 른 빠 른 정렬 을 위 한 인 스 턴 스 코드

알고리즘 의 평균 시간 복잡 도 는 O(nlogn)이다.그러나 입력 이 정렬 된 배열 이나 거의 정렬 된 입력 일 때 시간 복잡 도 는 O(n^2)입 니 다.이 문 제 를 해결 하고 평균 시간 복잡 도 를 O(nlogn)로 확보 하 는 방법 은 예비 처리 절 차 를 도입 하 는 것 이다.유일한 목적 은 요소 의 순 서 를 바 꾸 어 무 작위 로 정렬 하 는 것 이다.이러한 예비 처리 절 차 는 O(n)시간 내 에 실행 할 수 있다.같은 역할 을 할 수 있 는 또 다른 간단 한 방법 은 알고리즘 에 무 작위 요 소 를 도입 하 는 것 이다.이것 은 무 작위 로 요 소 를 나 누 는 주 원 을 선택 하여 실현 할 수 있다.주 원 을 무 작위 로 선택 한 결 과 는 입력 요소 의 모든 배열 가능성 과 같은 절 차 를 완화 시 켰 다.이 단 계 를 도입 하여 원래 의 빠 른 정렬 을 수정 하면 아래 의 에 세이 화 빠 른 정렬 을 얻 을 수 있 습 니 다.새 알고리즘 은 구간[low...high]에서 일치 하 게 랜 덤 으로 색인 v 를 선택 하고 A[v]와 A[low]를 교환 한 다음 에 원래 의 빠 른 정렬 알고리즘 에 따라 계속 합 니 다.여기 서 parseInt(Math.random()*(high-low+1)+low)는 low 와 high 사이 의 수 를 되 돌려 줍 니 다.
  
/****************************************
   :split
   : A[low...high]
   :
  1. , A;
  2. A[low] w;
  ****************************************/
  function split(array, low, high) {
  var i = low;
  var x = array[low];
  for(var j = low + 1; j <= high; j++) {
  if(array[j] <= x) {
  i ++;
  if(i != j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
  }
  }
  }
  temp = array[low];
  array[low] = array[i];
  array[i] = temp;
  return i;
  }
  /****************************************
   :rquicksort
   :A[0...n-1]
   : A[0...n-1]
  rquicksort(A, 0, n-1);
  ****************************************/
  function rquicksort(array, low, high) {
  if(low < high) {
  /****** *******/
  var v = parseInt(Math.random()*(high-low+1) + low);
  var tmp = array[low];
  array[low] = array[v];
  array[v] = tmp;
  /****** *******/
  var w = split(array, low, high);
  rquicksort(array, low, w -1);
  rquicksort(array, w +1, high);
  return array;
  }
  }
  var array = [33, 22, 11, 88, 23, 32];
  array = rquicksort(array, 0, array.length-1);
  console.log(array);

좋은 웹페이지 즐겨찾기