빠른 정렬 알고리즘의 JavaScript 구현에 대한 코드 그래픽 분석
- 黄舟원래의
- 2017-04-15 09:31:271611검색
이번 글에서는 JavaScript 기반의 퀵 정렬 알고리즘을 주로 소개하고, 퀵 정렬의 원리를 분석하고, 자바스크립트 퀵 정렬의 동작 단계와 관련 구현 기법을 예제 형식으로 제공합니다. 다음을 참고하시면 됩니다
본 글의 예시는 자바스크립트 기반의 빠른 정렬 알고리즘을 설명하고 있습니다. 참고하실 수 있도록 공유해 드리며, 자세한 내용은 다음과 같습니다.
먼저 버블 정렬을 소개하겠습니다. 먼저 한 레코드의 키를 두 번째 레코드의 키와 비교합니다. 순서가 바뀌면 두 키를 교환한 후 마지막 비교가 완료될 때까지 두 번째와 세 번째 키를 비교합니다. 이것이 첫 번째 버블링이며, 결과적으로 가장 큰 키워드를 가진 레코드가 마지막 위치에 배치됩니다. 그런 다음 두 번째로 시퀀스의 첫 번째 n-1 요소를 버블링하고 두 번째 요소를 선택합니다. 이런 식으로 모두 선택되면 버블링이 종료됩니다 .
분석을 통해 버블 정렬의 시간복잡도는 O(n2)라는 결론을 내릴 수 있습니다.
퀵 정렬은 버블 정렬을 개선한 것으로, 재귀 방법을 통해 대규모 데이터 세트를 처리하는 가장 빠른 정렬 중 하나입니다. 데이터를 더 작은 요소와 더 큰 요소를 포함하는 서로 다른 하위 시퀀스로 순차적으로 분해하고 모든 데이터가 정렬될 때까지 프로세스를 반복합니다. 이 알고리즘은 먼저 기준 값을 선택하고 기준 값을 중심으로 진행해야 합니다.
예시는 다음과 같습니다.
알고리즘 아이디어는 다음과 같습니다.
을 선택하세요. 기본 요소 및 목록 추가
목록을 재정렬하여 참조 요소보다 작은 모든 요소를 앞에 배치하고 더 큰 요소를 뒤에 배치합니다. >
작은 요소의 하위 순서와 큰 요소의 하위 순서에 대해 위의 두 단계를 반복합니다.js
<!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]+' ');
}
document.write('<br>');
}
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>평균 시간 기준으로 현재 퀵 정렬은 최고의 내부 정렬 방법으로 간주됩니다. 퀵 정렬은 대규모 데이터 세트에 매우 적합하지만, 작은 데이터 세트를 처리할 때는 성능이 저하됩니다. 시간 복잡도는 O(nlog2n)
입니다.
위 내용은 빠른 정렬 알고리즘의 JavaScript 구현에 대한 코드 그래픽 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!