Skip to content
TheChatArchiveThe Chat Archive
Human-written demonstration (OpenAssistant volunteers)· OpenAssistant (human-written)Hugging Face OpenAssistant Conversations (oasst2)

用JS编写归并排序函数

In OpenAssistant data, “assistant” turns were written by human volunteers as demonstrations. They are not model outputs.
  1. User

    用JS编写归并排序函数

  2. Assistant

    归并排序(MergeSort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。归并排序的算法时间复杂读为O(NLogN),是一种稳定的排序算法。

    function mergeSort(array) {
      const half = array.length / 2
      
      if(array.length < 2){
        return array 
      }
      
      const left = array.splice(0, half)
      return merge(mergeSort(left),mergeSort(array))
    }
    
    // 把两个排好序的子数组(left、right)合并来获得一个排好序的大数组
    function merge(left, right) {
        let arr = []
        // 如果任何一个数组为空,就退出循环
        while (left.length && right.length) {
            // 从左右子数组的最小元素中选择较小的元素
            if (left[0] < right[0]) {
                arr.push(left.shift())  
            } else {
                arr.push(right.shift()) 
            }
        }
        
        // 连接剩余的元素,防止没有把两个数组遍历完整
        return [ ...arr, ...left, ...right ]
    }
    
    
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.