Imbas kembali kemuncak algoritma pengisihan menggunakan JavaScript untuk pemula

Patricia Arquette
Lepaskan: 2024-10-06 06:18:31
asal
506 orang telah melayarinya

Recap the highlight of the sorting algorithms using JavaScript for beginners

Sorting algorithms are methods used to arrange elements of a list or array in a specific order, typically numerical or lexicographical. They are fundamental in computer science for organizing data efficiently. It is an exercise in understanding how to break down a problem into steps and then implement those steps, i.e., how to create an algorithm. It's also an exercise in realizing that there are multiple methods to tackle an issue, and some are superior to others.

Why should I learn it?

  • It's a simple practical example for thinking recursively (see: merge sort and quick sort) and divide and conquer.
  • It's a simple but nontrivial example for algorithmic analysis (I.e. big O).
  • It's a traditional intro computer science topic that is expected to be taught.
  • It's a simple example to motivate why you might care about having a better algorithm than the simplest native one (I.e. bubble sort).

Here are some common sorting algorithms

Bubble Sort

Description: Repeatedly swaps adjacent elements if they are in the wrong order.
Time Complexity: O(n²)
Use Case: Simple but inefficient for large datasets.
Bubble Sort GitHub Gist


<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>

<p>function bubbleSort(arr)<br>
{<br>
    var temp, i, j;</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">for(i = 0; i&lt;arr.length; i++)
{
    for(j = 0; j&lt; arr.length; j++)
    {
        if (arr[j] &gt; arr[j+1])
        {
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

return arr;
Salin selepas log masuk

}

console.log(bubbleSort(arr));

Enter fullscreen mode Exit fullscreen mode




Selection Sort

Description: Selects the smallest element from the unsorted part and swaps it with the first unsorted element.
Time Complexity: O(n²)
Use Case: Inefficient for large datasets but easy to implement.
Selection Sort GitHub Gist


<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>

<p>function selectionSort(arr)<br>
{<br>
   var min;<br>
   for(var i = 0; i < arr.length; i++)<br>
   {<br>
       min = i;<br>
       for(var j = i+1; j < arr.length; j++ )<br>
       {<br>
           if (arr[j] < arr[min])<br>
           {<br>
               min = j;<br>
           }<br>
       }</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">   if (min !== i) {
       var s = arr[min];
       arr[min] = arr[i];
       arr[i] = s;
   }
Salin selepas log masuk

}

return arr;
}

console.log(selectionSort(arr));

Enter fullscreen mode Exit fullscreen mode




Insertion Sort

Description: Builds the sorted list one element at a time by inserting each element into its correct position.
Time Complexity: O(n²)
Use Case: Good for small datasets or nearly sorted arrays.
Insertion Sort GitHub Gist


<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>

<p>function insertionSort(arr)<br>
{<br>
    for(let i = 1; i< arr.length; i++)<br>
    {<br>
        let key= arr[i];<br>
        let j = i - 1</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">    while (j &gt;= 0 &amp;&amp; key &lt; arr[j]) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
}

return arr;
Salin selepas log masuk

}

console.log(insertionSort(arr));

Enter fullscreen mode Exit fullscreen mode




Merge Sort

Description: Divides the array into halves, recursively sorts them, and then merges the sorted halves.
Time Complexity: O(n log n)
Use Case: Efficient for large datasets, uses additional space for merging.
Merge Sort GitHub Gist
Merge Sort 2 GitHub Gist


<p>var unsortedArr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>

<p>function merge(left, right)<br>
{<br>
    const result = new Array();</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">let i = j = 0;
while (i &lt; left.length &amp;&amp; j &lt; right.length) {
    if (left[i] &lt; right[j]){
        result.push(left[i]);
        i++;
    }else {
        result.push(right[j]);
        j++;
    }
}

while (i &lt; left.length) {
    result.push(left[i]);
    i++;
}

while (j &lt; right.length) {
    result.push(right[j]);
    j++;
}

return result;
Salin selepas log masuk

}

function mergeSort(arr)
{
if (arr.length <= 1)
return arr;

const mid = Math.floor(arr.length/2);
const LA = new Array();
const RA = new Array();

for(let i = 0; i&lt; mid; i++)
    LA.push(arr[i]);

for(let j = mid; j&lt; arr.length; j++)
    RA.push(arr[j]);


const leftSorted = mergeSort(LA);
const rightSorted = mergeSort(RA);

return merge(leftSorted, rightSorted);
Salin selepas log masuk

}

console.log(mergeSort(unsortedArr));

Enter fullscreen mode Exit fullscreen mode




Quick Sort

Description: Selects a pivot element and partitions the array into two sub-arrays: elements less than the pivot and elements greater than the pivot, then recursively sorts the sub-arrays.
Time Complexity: O(n log n) on average, O(n²) in the worst case.
Use Case: Fast and widely used for large datasets.
Quick Sort GitHub Gist


<p>var arr = [10, 55, 20, 4, 28, 69, 22, 85, 7, 37];</p>

<p>function partition(arr, low, high)<br>
{<br>
    const pivot = arr[high];</p>
<div class="highlight js-code-highlight">
<pre class="highlight plaintext">let i = low -1;

for(let j = low; j &lt;= high -1; j++)
{
    if (arr[j] &lt; pivot) {
        i++
        swap(arr, i, j)
    }
}

swap(arr, i+ 1, high);

return i + 1
Salin selepas log masuk

}

function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function QuickSort(arr, low, high)
{
if (low < high){
const po = partition(arr, low, high);
QuickSort(arr, low, po - 1);
QuickSort(arr, po + 1, high);
}

return arr;
Salin selepas log masuk

}

console.log(QuickSort(arr, 0, arr.length - 1));

Enter fullscreen mode Exit fullscreen mode




Heap Sort

Description: Converts the array into a heap data structure and repeatedly extracts the maximum element to build the sorted array.
Time Complexity: O(n log n)
Use Case: Efficient and doesn't require extra space like merge sort.

Radix Sort

Description: Non-comparative sorting algorithm that sorts elements digit by digit, starting from the least significant digit to the most significant.
Time Complexity: O(nk) where k is the number of digits.
Use Case: Suitable for sorting numbers or strings with fixed-length keys.

Bucket Sort

Description: Divides elements into several buckets and then sorts each bucket individually (usually using another sorting algorithm).
Time Complexity: O(n + k) where k is the number of buckets.
Use Case: Effective when input is uniformly distributed over a range.

Each algorithm has its strengths and weaknesses, and the choice of which one to use depends on the size of the dataset, memory constraints, and whether the data is partially sorted.

Let's discuss how often we should practice those.

Atas ialah kandungan terperinci Imbas kembali kemuncak algoritma pengisihan menggunakan JavaScript untuk pemula. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:dev.to
Artikel sebelumnya:Seret dan Lepaskan dalam HTML5 Artikel seterusnya:Memahami salinan dalam dalam JavaScript
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Isu terkini
Topik-topik yang berkaitan
Lagi>
Cadangan popular
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan