Javascript_javascript 기술에서 Quicksort를 구현하기 위한 알고리즘에 대한 자세한 설명-JS 튜토리얼-php.cn

Javascript_javascript 기술에서 Quicksort를 구현하기 위한 알고리즘에 대한 자세한 설명

WBOY

풀어 주다： 2016-05-16 15:40:43

원래의

1046명이 탐색했습니다.

현재 가장 일반적인 정렬 알고리즘은 약 7~8개가 있으며, 그 중 "Quicksort"가 가장 널리 사용되고 더 빠릅니다. 튜링상 수상자 C. A. R. Hoare(1934~)가 1960년에 제안했습니다.

"빠른 정렬"의 개념은 매우 간단합니다. 전체 정렬 과정은 세 단계만 거치면 됩니다:

(1) 데이터 세트에서 요소를 "피벗"으로 선택합니다.

(2) "base"보다 작은 모든 요소는 "base"의 왼쪽으로 이동되고, "base"보다 큰 모든 요소는 "base"의 오른쪽으로 이동됩니다.

(3) 모든 하위 집합에 하나의 요소만 남을 때까지 "기준선"의 왼쪽과 오른쪽에 있는 두 하위 집합에 대해 첫 번째와 두 번째 단계를 반복합니다.

예를 들어 {85, 24, 63, 45, 17, 31, 96, 50} 데이터 세트가 있습니다. 어떻게 정렬하나요?

첫 번째 단계는 중간 요소 45를 "기준선"으로 선택하는 것입니다. (기본값은 임의로 선택해도 되지만, 중간값을 선택하는 것이 이해하기 쉽습니다.)

두 번째 단계는 각 요소를 '기준선'과 비교하여 두 개의 하위 집합, 즉 '45 미만'과 '45 이상'을 형성하는 것입니다.

세 번째 단계는 모든 하위 집합에 하나의 요소만 남을 때까지 두 하위 집합에 대해 첫 번째와 두 번째 단계를 반복하는 것입니다.

다음은 인터넷에 떠도는 정보를 참고로 하며, 위의 알고리즘을 자바스크립트 언어를 사용하여 구현한 것입니다.

먼저 매개변수가 배열인 QuickSort 함수를 정의합니다.

var quickSort = function(arr) {
};

로그인 후 복사

그런 다음 배열의 요소 수를 확인하고 1보다 작거나 같으면 반환합니다.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

로그인 후 복사

다음으로 "피벗"을 선택하여 원래 배열과 분리한 다음 두 개의 빈 배열을 정의하여 왼쪽과 오른쪽에 하나씩 두 개의 하위 집합을 저장합니다.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
};

로그인 후 복사

그런 다음 배열 순회를 시작하여 "기준선"보다 작은 요소를 왼쪽 하위 집합에 배치하고 "기준선"보다 큰 요소를 오른쪽 하위 집합에 배치합니다.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

로그인 후 복사

마지막으로 재귀를 사용하여 이 프로세스를 반복하여 정렬된 배열을 얻습니다.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

로그인 후 복사

이 기사가 모든 사람의 JavaScript 프로그래밍 설계에 도움이 되기를 바랍니다.