찾다
웹 프론트엔드JS 튜토리얼JavaScript_javascript 기술에서 일반적으로 사용되는 9가지 정렬 알고리즘

서면 인터뷰에는 다양한 알고리즘이 포함되는 경우가 많습니다. 이 기사에서는 일반적으로 사용되는 몇 가지 알고리즘을 간략하게 소개하고 이를 JavaScript로 구현합니다.

1. 삽입 정렬

1) 알고리즘 소개

Insertion-Sort의 알고리즘 설명은 간단하고 직관적인 정렬 알고리즘입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 추가 공간만 사용하는 정렬)이 사용되므로 스캔 과정에서 뒤에서 앞으로 반복적이고 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.

2) 알고리즘 설명 및 구현

일반적으로 삽입 정렬은 in-place를 사용하여 배열에서 구현됩니다. 구체적인 알고리즘은 다음과 같습니다.

첫 번째 요소부터 시작하여 요소가 정렬된 것으로 간주할 수 있습니다.
다음 요소를 꺼내고 정렬된 요소 순서에서 뒤에서 앞으로 스캔합니다.
(정렬된) 요소가 새 요소보다 크면 해당 요소를 다음 위치로 이동하세요. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복하세요. 해당 위치에 새 요소를 삽입한 후
2~5단계를 반복하세요.
JavaScript 코드 구현:

 function insertionSort(array) {
   if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
     for (var i = 1; i < array.length; i++) {
       var key = array[i];
       var j = i - 1;
       while (j >= 0 && array[j] > key) {
         array[j + 1] = array[j];
         j--;
       }
      array[j + 1] = key;
    }
    return array;
  } else {
    return 'array is not an Array!';
  }
}
3) 알고리즘 분석

최상의 사례: 입력 배열이 오름차순으로 정렬됩니다. T(n) = O(n)

최악의 경우: 입력 배열이 내림차순으로 정렬됩니다. T(n) = O(n2)

평균 사례: T(n) = O(n2)


2. 바이너리 삽입 정렬


1) 알고리즘 소개

이진-삽입-정렬 정렬은 직접 삽입 정렬 알고리즘을 약간 변경한 정렬 알고리즘입니다. 직접 삽입 정렬 알고리즘과 가장 큰 차이점은 이진 검색 방식을 사용하여 삽입 위치를 찾는 점인데, 이로 인해 속도가 어느 정도 향상됩니다.

2) 알고리즘 설명 및 구현

일반적으로 삽입 정렬은 in-place를 사용하여 배열에서 구현됩니다. 구체적인 알고리즘은 다음과 같습니다.

첫 번째 요소부터 시작하여 요소가 정렬된 것으로 간주할 수 있습니다.

다음 요소를 꺼내고 이진 검색을 사용하여 정렬된 요소 시퀀스에서 그보다 큰 첫 번째 숫자의 위치를 ​​찾습니다. 해당 위치에 새 요소를 삽입한 후

위의 두 단계를 반복합니다.
JavaScript 코드 구현:


3) 알고리즘 분석
function binaryInsertionSort(array) {
   if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
     for (var i = 1; i < array.length; i++) {
       var key = array[i], left = 0, right = i - 1;
       while (left <= right) {
         var middle = parseInt((left + right) / 2);
         if (key < array[middle]) {
           right = middle - 1;
         } else {
          left = middle + 1;
        }
      }
      for (var j = i - 1; j >= left; j--) {
        array[j + 1] = array[j];
      }
      array[left] = key;
    }
    return array;
  } else {
    return 'array is not an Array!';
  }
}
최상의 사례: T(n) = O(nlogn)

최악의 경우: T(n) = O(n2)

평균 사례: T(n) = O(n2)




3. 선택 정렬

1) 알고리즘 소개

Selection-sort는 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식: 먼저 정렬되지 않은 시퀀스에서 가장 작은(큰) 요소를 찾아 이를 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 가장 작은(큰) 요소를 계속 찾아 정렬된 시퀀스에 넣습니다. 시퀀스 끝. 모든 요소가 정렬될 때까지 계속됩니다.

2) 알고리즘 설명 및 구현

n개의 레코드에 대한 직접 선택 정렬은 n-1개의 직접 선택 정렬 패스를 통해 정렬된 결과를 얻을 수 있습니다. 구체적인 알고리즘은 다음과 같습니다.

초기 상태: 순서가 지정되지 않은 영역은 R[1..n]이고, 순서가 지정된 영역은 비어 있습니다.

i번째 정렬(i=1,2,3...n-1)이 시작되면 현재 정렬된 영역과 정렬되지 않은 영역은 각각 R[1..i-1] 및 R(i..n)입니다. 이러한 정렬 연산은 현재 비정렬 영역에서 키가 가장 작은 레코드 R[k]를 선택하여 비정렬 영역의 첫 번째 레코드 R과 교환함으로써 R[1..i]와 R[i 1..n이 되도록 한다. ) 레코드 수가 1개 증가하여 새로운 정렬된 영역이 되고, 레코드 수가 1개 감소하여 새로운 정렬되지 않은 영역이 됩니다.

n-1 패스가 끝나면 배열이 정렬됩니다.



JavaScript 코드 구현:

3) 알고리즘 분석
 function selectionSort(array) {
   if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
     var len = array.length, temp;
     for (var i = 0; i < len - 1; i++) {
       var min = array[i];
       for (var j = i + 1; j < len; j++) {
         if (array[j] < min) {
           temp = min;
           min = array[j];
          array[j] = temp;
        }
      }
      array[i] = min;
    }
    return array;
  } else {
    return 'array is not an Array!';
  }
}
최상의 사례: T(n) = O(n2)

최악의 경우: T(n) = O(n2)

평균 사례: T(n) = O(n2)




4. 버블정렬


1) 알고리즘 소개

버블 정렬은 간단한 정렬 알고리즘입니다. 정렬할 순서를 반복적으로 살펴보며 한 번에 두 개의 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.

2) 알고리즘 설명 및 구현

구체적인 알고리즘은 다음과 같습니다.

인접한 요소를 비교합니다. 첫 번째 항목이 두 번째 항목보다 크면 둘 다 교체하세요.

인접한 요소의 각 쌍에 대해 동일한 작업을 시작 부분의 첫 번째 쌍부터 끝 부분의 마지막 쌍까지 수행하여 마지막 요소가 가장 큰 숫자가 되도록 합니다.

마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

정렬이 완료될 때까지 1~3단계를 반복하세요.
JavaScript 코드 구현:


3)算法分析

最佳情况:T(n) = O(n)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(n2)

五、快速排序

1)算法简介

  快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

2)算法描述和实现

  快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

从数列中挑出一个元素,称为 "基准"(pivot);
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  JavaScript代码实现:

 //方法一
 function quickSort(array, left, right) {
   if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {
     if (left < right) {
       var x = array[right], i = left - 1, temp;
       for (var j = left; j <= right; j++) {
         if (array[j] <= x) {
           i++;
           temp = array[i];
           array[i] = array[j];
           array[j] = temp;
         }
       }
       quickSort(array, left, i - 1);
       quickSort(array, i + 1, right);
     };
   } else {
     return 'array is not an Array or left or right is not a number!';
   }
 } 
 var aaa = [3, 5, 2, 9, 1];
 quickSort(aaa, 0, aaa.length - 1);
 console.log(aaa);
 
 //方法二
 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]);
     }
   }
   return quickSort(left).concat([pivot], quickSort(right));
 };

3)算法分析

最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(nlogn)

六、堆排序

1)算法简介

  堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

2)算法描述和实现

  具体算法描述如下:

将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;
将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1] 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
  JavaScript代码实现:

 /*方法说明:堆排序
 @param array 待排序数组*/      
 function heapSort(array) {
   if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
     //建堆
     var heapSize = array.length, temp;
     for (var i = Math.floor(heapSize / 2); i >= 0; i--) {
       heapify(array, i, heapSize);
     }
    
    //堆排序
    for (var j = heapSize - 1; j >= 1; j--) {
      temp = array[0];
      array[0] = array[j];
      array[j] = temp;
      heapify(array, 0, --heapSize);
    }
  } else {
    return 'array is not an Array!';
  }
}
/*方法说明:维护堆的性质
@param arr 数组
@param x  数组下标
@param len 堆大小*/
function heapify(arr, x, len) {
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
    var l = 2 * x, r = 2 * x + 1, largest = x, temp;
    if (l < len && arr[l] > arr[largest]) {
      largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
      largest = r;
    }
    if (largest != x) {
      temp = arr[x];
      arr[x] = arr[largest];
      arr[largest] = temp;
      heapify(arr, largest, len);
    }
  } else {
    return 'arr is not an Array or x is not a number!';
  }
}

3)算法分析

最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)

七、归并排序

1)算法简介

  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

2)算法描述和实现

  具体算法描述如下:

把长度为n的输入序列分成两个长度为n/2的子序列;
对这两个子序列分别采用归并排序;
将两个排序好的子序列合并成一个最终的排序序列。
  JavaScript代码实现:

 function mergeSort(array, p, r) {
   if (p < r) {
     var q = Math.floor((p + r) / 2);
     mergeSort(array, p, q);
     mergeSort(array, q + 1, r);
     merge(array, p, q, r);
   }
 }
 function merge(array, p, q, r) {
  var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0;
  for (var i = 0; i < n1; i++) {
    left[i] = array[p + i];
  }
  for (var j = 0; j < n2; j++) {
    right[j] = array[q + 1 + j];
  }
  left[n1] = right[n2] = Number.MAX_VALUE;
  for (var k = p; k <= r; k++) {
    if (left[m] <= right[n]) {
      array[k] = left[m];
      m++;
    } else {
      array[k] = right[n];
      n++;
    }
  }
}

3)算法分析

最佳情况:T(n) = O(n)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)

八、桶排序

1)算法简介

  桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

2)算法描述和实现

  具体算法描述如下:

设置一个定量的数组当作空桶;
遍历输入数据,并且把数据一个一个放到对应的桶里去;
对每个不是空的桶进行排序;
从不是空的桶里把排好序的数据拼接起来。
  JavaScript代码实现:

 /*方法说明:桶排序
 @param array 数组
 @param num  桶的数量*/
 function bucketSort(array, num) {
   if (array.length <= 1) {
     return array;
   }
   var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;
   num = num || ((num > 1 && regex.test(num)) &#63; num : 10);
   for (var i = 1; i < len; i++) {
     min = min <= array[i] &#63; min : array[i];
     max = max >= array[i] &#63; max : array[i];
   }
   space = (max - min + 1) / num;
   for (var j = 0; j < len; j++) {
     var index = Math.floor((array[j] - min) / space);
     if (buckets[index]) {  // 非空桶,插入排序
       var k = buckets[index].length - 1;
       while (k >= 0 && buckets[index][k] > array[j]) {
         buckets[index][k + 1] = buckets[index][k];
         k--;
       }
       buckets[index][k + 1] = array[j];
     } else {  //空桶,初始化
       buckets[index] = [];
       buckets[index].push(array[j]);
     }
   }
   while (n < num) {
     result = result.concat(buckets[n]);
     n++;
   }
   return result;
 }



3)算法分析

  桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

九、计数排序

1)算法简介

  计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

2)算法描述和实现

  具体算法描述如下:

找出待排序的数组中最大和最小的元素;
统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
  JavaScript代码实现:

 function countingSort(array) {
   var len = array.length, B = [], C = [], min = max = array[0];
   for (var i = 0; i < len; i++) {
     min = min <= array[i] &#63; min : array[i];
     max = max >= array[i] &#63; max : array[i];
     C[array[i]] = C[array[i]] &#63; C[array[i]] + 1 : 1;
   }
   for (var j = min; j < max; j++) {
     C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
   }
   for (var k = len - 1; k >=0; k--) {
     B[C[array[k]] - 1] = array[k];
     C[array[k]]--;
   }
   return B;
 }

3)算法分析

  当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
es6数组怎么去掉重复并且重新排序es6数组怎么去掉重复并且重新排序May 05, 2022 pm 07:08 PM

去掉重复并排序的方法:1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句,去掉数组中的重复元素,返回去重后的新数组;2、利用sort()对去重数组进行排序,语法“去重数组.sort()”。

JavaScript的Symbol类型、隐藏属性及全局注册表详解JavaScript的Symbol类型、隐藏属性及全局注册表详解Jun 02, 2022 am 11:50 AM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题,包括了Symbol类型的描述、Symbol不会隐式转字符串等问题,下面一起来看一下,希望对大家有帮助。

原来利用纯CSS也能实现文字轮播与图片轮播!原来利用纯CSS也能实现文字轮播与图片轮播!Jun 10, 2022 pm 01:00 PM

怎么制作文字轮播与图片轮播?大家第一想到的是不是利用js,其实利用纯CSS也能实现文字轮播与图片轮播,下面来看看实现方法,希望对大家有所帮助!

JavaScript对象的构造函数和new操作符(实例详解)JavaScript对象的构造函数和new操作符(实例详解)May 10, 2022 pm 06:16 PM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于对象的构造函数和new操作符,构造函数是所有对象的成员方法中,最早被调用的那个,下面一起来看一下吧,希望对大家有帮助。

JavaScript面向对象详细解析之属性描述符JavaScript面向对象详细解析之属性描述符May 27, 2022 pm 05:29 PM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于面向对象的相关问题,包括了属性描述符、数据描述符、存取描述符等等内容,下面一起来看一下,希望对大家有帮助。

javascript怎么移除元素点击事件javascript怎么移除元素点击事件Apr 11, 2022 pm 04:51 PM

方法:1、利用“点击元素对象.unbind("click");”方法,该方法可以移除被选元素的事件处理程序;2、利用“点击元素对象.off("click");”方法,该方法可以移除通过on()方法添加的事件处理程序。

整理总结JavaScript常见的BOM操作整理总结JavaScript常见的BOM操作Jun 01, 2022 am 11:43 AM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于BOM操作的相关问题,包括了window对象的常见事件、JavaScript执行机制等等相关内容,下面一起来看一下,希望对大家有帮助。

foreach是es6里的吗foreach是es6里的吗May 05, 2022 pm 05:59 PM

foreach不是es6的方法。foreach是es3中一个遍历数组的方法,可以调用数组的每个元素,并将元素传给回调函数进行处理,语法“array.forEach(function(当前元素,索引,数组){...})”;该方法不处理空数组。

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

mPDF

mPDF

mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는

PhpStorm 맥 버전

PhpStorm 맥 버전

최신(2018.2.1) 전문 PHP 통합 개발 도구