빠른 정렬 알고리즘의 JavaScript 구현에 대한 코드 그래픽 분석-JS 튜토리얼-php.cn

빠른 정렬 알고리즘의 JavaScript 구현에 대한 코드 그래픽 분석

黄舟

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

원래의

1763명이 탐색했습니다.

이번 글에서는 JavaScript 기반의 퀵 정렬 알고리즘을 주로 소개하고, 퀵 정렬의 원리를 분석하고, 자바스크립트 퀵 정렬의 동작 단계와 관련 구현 기법을 예제 형식으로 제공합니다. 다음을 참고하시면 됩니다

본 글의 예시는 자바스크립트 기반의 빠른 정렬 알고리즘을 설명하고 있습니다. 참고하실 수 있도록 공유해 드리며, 자세한 내용은 다음과 같습니다.

먼저 버블 정렬을 소개하겠습니다. 먼저 한 레코드의 키를 두 번째 레코드의 키와 비교합니다. 순서가 바뀌면 두 키를 교환한 후 마지막 비교가 완료될 때까지 두 번째와 세 번째 키를 비교합니다. 이것이 첫 번째 버블링이며, 결과적으로 가장 큰 키워드를 가진 레코드가 마지막 위치에 배치됩니다. 그런 다음 두 번째로 시퀀스의 첫 번째 n-1 요소를 버블링하고 두 번째 요소를 선택합니다. 이런 식으로 모두 선택되면 버블링이 종료됩니다 .

분석을 통해 버블 정렬의 시간복잡도는 O(n2)라는 결론을 내릴 수 있습니다.

퀵 정렬은 버블 정렬을 개선한 것으로, 재귀 방법을 통해 대규모 데이터 세트를 처리하는 가장 빠른 정렬 중 하나입니다. 데이터를 더 작은 요소와 더 큰 요소를 포함하는 서로 다른 하위 시퀀스로 순차적으로 분해하고 모든 데이터가 정렬될 때까지 프로세스를 반복합니다. 이 알고리즘은 먼저 기준 값을 선택하고 기준 값을 중심으로 진행해야 합니다.

예시는 다음과 같습니다.

알고리즘 아이디어는 다음과 같습니다.

을 선택하세요. 기본 요소 및 목록 추가

목록을 재정렬하여 참조 요소보다 작은 모든 요소를 앞에 배치하고 더 큰 요소를 뒤에 배치합니다. >

작은 요소의 하위 순서와 큰 요소의 하위 순서에 대해 위의 두 단계를 반복합니다.

를 통해 다음과 같이 코드를 구현합니다.

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//选择基准元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成两个之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//递归
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+&#39; &#39;);
    }
    document.write(&#39;<br>&#39;);
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希尔排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>