JavaScript中的简单排序算法

英文 | https://medium.com/javascript-in-plain-english/simple-sorting-algorithms-in-javascript-57d512ceaf5d

翻译 | web前端开发

排序是程序员处理数据处理时最常见的问题之一。在此文中，我们将介绍一些每个程序员都应该掌握的简单排序算法。所有这些都被认为很简单，因为它们的时间复杂度均为O（n²）。如果你不清楚Big O是什么，请看我在上面写的这个文章（地址：https://medium.com/swlh/small-math-to-big-o-901a90998871）。

我还建议将TopTal的排序算法动画或Visualgo的排序部分加入书签，以便在阅读本文时可视化这些算法并在整个编程过程中提供帮助。记住，程序员最好的朋友是互联网！

交换助手方法

所有这些算法都涉及交换数组中的元素。为了更好地理解算法的工作原理，我们将抽象出一个称为“交换”的可重用函数。“交换”接收一个数组，并交换该数组的两个索引。这是JS和Ruby中的实现：

function swap (arr, index1, index2){
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

冒泡排序

这些简单的排序算法中的每一个都从定义要排序的部分开始，然后从该排序的部分向外移动。冒泡排序是从找到数组中的最大值并将其移到最后一个元素（已排序的部分）开始的。然后重复执行，直到排序的部分封装了整个数组。

在上方，我们看到了冒泡排序的名称-通过不断比较两个元素并将它们交换来将最高元素冒到顶部。当数字在上面的GIF中变为橙色时，将被视为“已排序”，并且排序从头开始。然后，它将继续该过程，直到对整个数组进行排序为止。

在下面的实现中，我将跟踪两个变量-currentIndex（排序比较的对象）和endIndex（已排序的部分）。

function bubbleSort(arr){
  //start the endIndex at the last index of the array
    let endIndex = arr.length - 1;
  //run the loop until the endIndex(sorted portion) is the 0 (the full array)
    while(endIndex > 0){
        // count the number of swaps to short circuit the loop if it is already sorted
        let swaps = 0;
        //reset the currentIndex to the beginning of the array each time a new element is sorted
        let currentIndex = 0;
        // loop over the array, comparing each pair of elements until the comparison element reaches the sorted portion of the array
        while(currentIndex < endIndex){
            // uncomment this line to see the comparison in action
            // console.log(arr, arr[currentIndex], arr[currentIndex + 1])
            // if the current element is greater than the element in front of it
            if(arr[currentIndex] > arr[currentIndex + 1]){
                //swap the 2 elements using our helper function
                swap(arr, currentIndex, currentIndex + 1);
                // add 1 to the swaps counter
                swaps++;
            }
            //increase the currentIndex to continue iterating through the array
            currentIndex++;
        }
        //stop the loop if there were no swaps because the array must be already sorted 
        if(swaps === 0) break;
        // subtract the endIndex number to account for the new element added to the array
        endIndex--;


    }


    return arr;
}

选择排序

选择排序基本上与冒泡排序相反。排序不是查找最大的元素并将其冒泡到顶部，而是查找数组中的最小元素并将其移动到数组的开头- 新的sorted section。然后重复执行，直到排序的部分包含整个数组。

选择排序之所以得到它的名称，是因为它遍历数组并选择最低的元素，只有在完成遍历整个数组后才交换它。

在下面的实现中，我这次将跟踪3个变量-最小的元素，要与之比较的当前元素以及已排序部分的开头。

function selectionSort(arr){
    let smallestIndex = 0;
    let currentIndex = 1;
    let beginningIndex = 0;
    //loop until the sorted section is the full array
    while(beginningIndex < arr.length){
       //loop over the array until the currentIndex has reached the last element
        while(currentIndex < arr.length){
            //keep track of the smallest index by comparing it to the current index
            if(arr[smallestIndex] > arr[currentIndex]){
                smallestIndex = currentIndex;
            }
            //add to the current index to iterate through the array
            currentIndex++;


        }
        // after iterating through the array once, if the smallest number isn't at the sorted section, swap the two
        if(smallestIndex !== beginningIndex){
            swap(arr, smallestIndex, beginningIndex)
        }
        //add to the beginning index to incorporate the new sorted section
        beginningIndex++;
        //start the current index at 1 above the sorted section
        currentIndex = beginningIndex + 1;
        //reset the smallest index to the beginningIndex
        smallestIndex = beginningIndex;
    }
    return arr;
}

插入排序

最后，我们到达插入排序。插入排序与我们前面讨论的前两种排序略有不同，因为它不会首先找到最高或最低的数字-它将数组中的第一个数字视为已排序，然后将数字插入到排序中。

在上面的GIF中，我们发现交换在这种情况下有点不同-我们正在交换元素的下一个索引，以便为我们要比较的当前值腾出空间-以便找到正确的位置来插入它。

在实现中，我们要跟踪三个变量-我们正在排序的部分的beginIndex，我们要检查的currentIndex和我们要比较的currentVal。

function bubbleSort(arr){
  //start the endIndex at the last index of the array
    let endIndex = arr.length - 1;
  //run the loop until the endIndex(sorted portion) is the 0 (the full array)
    while(endIndex > 0){
        // count the number of swaps to short circuit the loop if it is already sorted
        let swaps = 0;
        //reset the currentIndex to the beginning of the array each time a new element is sorted
        let currentIndex = 0;
        // loop over the array, comparing each pair of elements until the comparison element reaches the sorted portion of the array
        while(currentIndex < endIndex){
            // uncomment this line to see the comparison in action
            // console.log(arr, arr[currentIndex], arr[currentIndex + 1])
            // if the current element is greater than the element in front of it
            if(arr[currentIndex] > arr[currentIndex + 1]){
                //swap the 2 elements using our helper function
                swap(arr, currentIndex, currentIndex + 1);
                // add 1 to the swaps counter
                swaps++;
            }
            //increase the currentIndex to continue iterating through the array
            currentIndex++;
        }
        //stop the loop if there were no swaps because the array must be already sorted 
        if(swaps === 0) break;
        // subtract the endIndex number to account for the new element added to the array
        endIndex--;

    }

    return arr;
}

请记住，这些排序算法在最坏的情况下都具有O（n²）的时间复杂度，因此如果处理大量未排序的数据，它们可能会非常慢。但是，这些算法充其量只能是O（n），因此，如果你拥有一组几乎可以排序的数据，则这些实现中的任何一种都应该可以快速运行。

如果你想查看这些用for循环编写的替代版本，请检查此Gist（地址：https://gist.github.com/Giagnus64/a1276f8b885221eedd05b79306536588）。如果你想查看这些用Ruby编写的类型，请检查此Gist（地址：https://gist.github.com/Giagnus64/d1909852e74a6df31a66d8e54655d319）。