JavaScript中的中间排序算法

英文 | https://medium.com/@gianfranconuschese/intermediate-sorting-algorithms-in-javascript-4ec8b641b32

翻译 | web前端开发（ID：web_qdkf)

最近，我介绍了一些使用JavaScript的简单排序算法《​​JavaScript中的简单排序算法​​》。我使用“简单”一词是因为这些算法更易于理解和实现，但是缺点是它们的时间复杂度很高- 最坏时为O（n²）。

在本文中，我们将逐步介绍一些更复杂的算法，以缩短我们的排序时间。（如果你想查看ruby的实现，我将它们包括在本文的底部。）

递归

合并和快速排序使用一种称为递归的概念。递归是当函数在自身内部调用自身时。每个递归函数都需要一个基本情况来返回，以便该函数不会陷入调用它的无限循环中。

我们将编写一个快速的递归函数，以探讨递归的工作方式。

function reverse(str){
//如果我们到达字符串的最后一个字符，则返回该字符
if (str.length === 1) return str[0];
//否则返回字符串的最后一个字符，以及在该字符串的切片版本上调用的反向函数
return str[str.length - 1] + reverse(str.slice(0, str.length - 1))}

我建议将其放入你最喜欢的测试环境中，以便你可以在函数起作用时跟踪调用堆栈-请记住，你始终可以将其放入Chrome的代码段中，并使用“调试器”行逐步完成该函数。让我们看看如果要反转字符串“ bar”会发生什么。

function reverse(str){
// if we arrive at the final character of the string, return that character
if (str.length === 1) return str[0];
//otherwise return the last character of the string, plus the reverse function called on a sliced version of that string
return str[str.length - 1] + reverse(str.slice(0, str.length - 1))
}

//1st Call returns "r" +  reverse("ba")  
//2nd call                "a" + reverse("b")
//3rd Call                          "b"
//returns     "r"      +  "a" +     "b"

合并排序

既然我们已经介绍了递归，那么让我们开始实现排序算法。合并和快速排序都利用了长度为0或1的数组始终被排序这一事实。合并排序的工作方式是将元素数组分成两半，直到与长度为0或1的“排序”数组合并，然后将这些排序数组合并在一起，直到与最终排序数组合并。让我们分解一下。

排序中最重要的部分是实现合并数组的功能。此函数假定数组已排序-我们将使用0或1个长度的数组。

//ASSUMES THE ARRAYS ARE SORTED*****
const merge = (arr1, arr2) => {
//establish a final sorted array to sort the elements, and a pointer for each array
let sortedArray = [];
let firstPointer = 0;
let secondPointer = 0;
//while the first pointer and the second pointer have not reached the end of their respective arrays
while (firstPointer <  arr1.length && secondPointer < arr2.length){
//add lesser number to array, and move pointer
if(arr2[secondPointer] >= arr1[firstPointer]){
            sortedArray.push(arr1[firstPointer])
            firstPointer++;
        } else{
            sortedArray.push(arr2[secondPointer])
            secondPointer++;
        } 
    }
//after arrays have been exhausted, add the rest of the numbers from whatever array's pointer has not reached gone through the array
while(firstPointer < arr1.length) {
        sortedArray.push(arr1[firstPointer]);
        firstPointer++;
    } 
while(secondPointer < arr2.length) {
        sortedArray.push(arr2[secondPointer])
        secondPointer++;
    }
return sortedArray
}

现在我们已经构建了合并功能，我们可以使用它来构建排序功能。

const mergeSort = (arr) => {
//if array is SORTED(length is 0 or 1), return array
if (arr.length <= 1) return arr;
//find midpoint
let midpoint = Math.floor(arr.length/2);
//split array by midpoint and merge sort the split arrays
let arr1 = mergeSort(arr.slice(0, midpoint))

let arr2 = mergeSort(arr.slice(midpoint))
//return the merged arrays
return merge(arr1, arr2)
}

似乎太简单了，但让我们考虑一下解决方案：我们的基本情况是返回一个长度为0或1的数组。如果不是，我们将数组分成两半，对两个数组进行合并排序，然后将排序后的数组合并在一起。以下是视觉细分：

快速排序

快速排序就像合并排序一样拆分数组，但是它没有找到中点，而是使用枢轴点。找到枢轴点后，我们将所有小于枢轴点的值移到数组的左侧，并将所有值移到数组的右侧。在那一步，枢轴点被“排序”。当我们对枢轴点的每一侧进行相同操作直到对数组进行排序时，该函数将变为递归。

视觉辅助和我们的实现将始终选择数组中的第一项作为我们的枢轴点。当前枢轴点为黄色。红色代表我们当前正在迭代的数组值。紫色表示该值大于轴心点，绿色表示小于该轴心点。每当我们找到小于枢轴值的项目时，我们都会将其与当前迭代交换，将其放置在数组未排序部分的开始处。到达终点后，我们将枢轴点交换为交换的最后一个数字，将所有小于的值置于前面，使之排序并由橙色表示。

然后，我们在枢轴点的左侧进行相同的排序，最终到达我们的基本案例（如上所示，分别为5和15）-两个长度为1的数组被排序。

然后，我们将在右侧执行相同操作，最后得到一个排序数组。请注意，我们将所有这些数字交换到位-而不是Merge Sort，我们将数组拆分并合并在一起。

让我们开始使用我们的辅助方法。这次我们将需要两个：交换辅助方法和数据透视辅助方法。我们的数据透视方法将需要返回一个数据透视索引，以便当我们递归调用它时，我们知道从哪里开始我们的新数据透视。

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

//快速排序
//为开始索引和结束索引设置默认大小写，因为以后在递归调用时需要更改它们
const pivot = (arr, startIndex = 0, endIndex = arr.length - 1) => {
//选择一个枢轴数字（在这种情况下，是数组中的第一个数字）
let pivotNum = arr[startIndex]
//保持索引的位置，其中将数据透视表交换到
let pivotIndex = startIndex;
//遍历数字，如果枢轴数更大，则交换当前数字和枢轴索引处的数字，并将枢轴索引增加1
for(let i = startIndex + 1; i < arr.length; i++) {
if(pivotNum > arr[i]){
            pivotIndex++;
            swap(arr, i, pivotIndex) 
        }
    }
//最后，将数据透视表编号与pivotIndex交换
    swap(arr, pivotIndex, startIndex)
return pivotIndex;
}

我们还将需要为我们的快速排序方法建立默认参数，因为我们将在每个枢轴上传递不同的参数。你应该注意到，我们的基本情况与正常情况有些不同-我们仅在数组未排序的情况下调用数据透视表，而只是在函数末尾返回原始数组。

这是因为我们要对数组进行适当的变异，因此，只要传递适当的数字以进行枢轴旋转，我们最终将返回相同的数组，已排序。

大O合并和快速排序

因此，由于我们将数组按这些类型拆分，因此可以期望至少具有O（log n）。请记住，日志的发现多少的一个数字我们乘拿到另一个号码？—因为我们将数组拆分为一个或零个元素，所以这意味着我们必须将元素加倍n次才能达到原始数组的长度。

由于我们在这两类中进行比较，我们将每一个元素的数组中进行比较，这意味着我们会做ñ比较日志N倍。因此，最糟糕的是，我们的排序的时间复杂度为O（n log n）。但是，快速排序有点不同。

实际上，我们的效率取决于我们的关键点。在最好的情况下，我们的枢轴点大约是数组中数字的中点，从而导致两侧的拆分均匀分布。

我们的实现每次都选择数组中的第一个元素。如果我们有一个已经排序过的数组的最坏情况，我们最终将数组拆分n次，然后将数字进行n次比较，得出O（n²）。

记住，这并不比我们简单的排序算法好。我们可以通过总是在数组中选择一个随机元素来解决这个问题，但是如果我们选择数组中最高或最低的数字，我们仍然会得到O（n²）。

基数排序

我介绍的所有排序算法（包括简单的排序算法）都基于比较值。基数排序的独特之处在于它不比较值，而是根据它们的数字位置将它们排序为“存储桶”。从技术上讲，“基数排序”仅适用于数字，但可用于字符串和图像，因为它们可以转换为二进制。

我们将在实现中使用基数为10的数字，但是该排序可以与其他数字一起使用。这些数字根据其数字位置分类到存储桶中。以红色突出显示的数字是当前排序依据的数字。然后排序将数字从0桶开始放回到列表中，直到所有桶都为空。该过程需要重复x次，其中x是排序中最大的数字所具有的位数。

这种排序将使用三个辅助函数-getDigit，digitCount和mostDigits。我们将使用getDigit在快速排序实现中找到需要排序的数字。digitCount将在mostDigits函数中使用，以找到我们需要迭代的最大位数。这些函数可以用不同的方式编写（例如将数字转换为字符串然后返回），但是由于它们加深了对Radix Sort起作用的理解，因此我加入了数学运算法则。

//在请求的位置获取数字（向后工作，即，一个位置是最后一位，十位是倒数第二位，依此类推）
const getDigit = (num, place) => {
//将小数点移到所请求的数字（考虑负数的绝对值）
const divided = Math.abs(num) / Math.pow(10, place);
//四舍五入以消除小数点后的数字
const floored = Math.floor(divided);
//取数字除以底数（10）得到余数
const digit = floored % 10;

return digit

}

//获取位数
const digitCount = (num) => {
//特殊情况忽略在0上运行log10
if(num === 0) return 1;
//由于我们以10为底，所以需要将10乘以多少次才能获得传入的数字？
const power = Math.log10(Math.abs(num))
//将其删除以除去小数点后的数字
const floored = Math.floor(power)
//将1位数字加到小数点后的数字
return floored + 1

}

//获取列表中要包含的最大位数
const mostDigits = (nums) => {
//设置最大位数的变量
let maxDigits = 0;
//遍历列表
for(let i = 0; i < nums.length; i++){
//获取列表的当前最大位数和当前迭代的位数
        maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
return maxDigits
}

现在我们已经有了助手，我们的排序实现比上面的实现更加复杂。请注意第18行：将所有内容放入存储桶后，我们将“ nums”重新分配给使用“ .concat”和散布运算符将存储桶中的阵列展平的新数组–太酷了吗？

const radixSort = (nums) => {
//get the max digits for the list
let maxDigits = mostDigits(nums);

//iterate from 0 to number of max digits
//digit iterator
for(let i = 0; i < maxDigits; i++){
// make digit buckets by crafting an array with 10 arrays inside it
let digitBuckets = Array.from({length:10}, () => [])// same as const digitBuckets = [[],[],[],[],[],[],[],[],[],[]]
//iterate over our numbers and place them into the proper bucket using helper functions
for(let j = 0; j < nums.length; j++){
//get the digit at the current digit iterator place
let digitized = getDigit(nums[j], i)
//place into the proper bucket based on digit
            digitBuckets[digitized].push(nums[j])
        }
//reassign nums to a new array from the spreading of the digit buckets array (like flattening the arrays)
        nums = [].concat(...digitBuckets)
    }
return nums;
}

基数大O

我们要遍历n个数字k次，因此最坏的情况是时间复杂度为O（nk），其中n是数组的长度，k是这些数字中的位数。它是线性时间，比合并和快速排序要快，因此它是大型数据集的流行选择。

Ruby的Sorts实现

# ASSUMES ARRAYS ARE SORTED
def merge(arr1, arr2)
    sorted_array = []
    first_pointer = 0
    second_pointer = 0
    while(first_pointer < arr1.size && second_pointer < arr2.size)
        if(arr2[second_pointer] >= arr1[first_pointer])
            sorted_array.push(arr1[first_pointer])
            first_pointer += 1
        else 
            sorted_array.push(arr2[second_pointer])
            second_pointer += 1
        end
    end
    while(first_pointer < arr1.size)
        sorted_array.push(arr1[first_pointer])
        first_pointer += 1
    end
    while(second_pointer < arr2.size)
        sorted_array.push(arr2[second_pointer])
        second_pointer += 1
    end
   
    return sorted_array
end


def merge_sort(arr)
    if(arr.size <= 1)
        return arr
    end
    midpoint = (arr.size/2).floor
    left = merge_sort(arr.slice(0...midpoint))
    right = merge_sort(arr.slice(midpoint..arr.size))


    return merge(left, right)
end


#print merge_sort(arr3)


def pivot(arr, start_index = 0, end_index = arr.size - 1) 
    pivot_number = arr[start_index]
    pivot_index = start_index
    for i in (start_index + 1)..end_index do 
        if(pivot_number > arr[i])
            pivot_index += 1
            swap(arr, i, pivot_index)
        end
    end
    swap(arr, start_index, pivot_index)
    #print arr
    return pivot_index
end
#print pivot(arr3)


def quick_sort(arr, left = 0, right = arr.size - 1)
    if(left < right)
        pivot_index = pivot(arr, left, right)
        quick_sort(arr, left, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, right)
    end
    return arr
end
#print quick_sort(arr3)


def get_digit(num, place)
    divided = num.abs / (10**place)
    floored = divided.floor
    digit = floored % 10
end


# print get_digit(743, 1)




def digit_count(num)
    if(num == 0)
        return 1
    end
    power = Math.log(num.abs, 10)
    floored = power.floor
    return floored + 1
end
# print digit_count(4387)


def most_digits(arr)
    max_digits = 0
    i = 0
    while(i < arr.size)
        if(digit_count(arr[i]) > max_digits)
            max_digits = digit_count(arr[i])
        end
        i += 1
    end
    max_digits
end


def radix_sort(arr)
    max_digits = most_digits(arr)
    for i in 0...max_digits do
        digit_buckets = [[],[],[],[],[],[],[],[],[],[]]
        j = 0
        while(j < arr.size)
            digitized = get_digit(arr[j], i)
            digit_buckets[digitized].push(arr[j])
            j += 1
        end
        arr = digit_buckets.flatten
    end
    arr
end


#print radix_sort(arr3)