JavaScript实现堆排序，归并排序，快速排序

FWHeart 发布于2019-08-22 18:31 / 3483人阅读

摘要：归并排序归并排序前归并排序后快速排序对于一字给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再一次对前后两部分的记录进行快速排序，递归该过程，指导序列中所有记录均有序为止。

堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

arr = [20,50,20,40,6,878,70,10,80,30,60,9,44];
    console.log("排序之前：" + arr);

    heapSort(arr);
    console.log("排序之后：" + arr);

    function heapSort(arr) {
      var end = arr.length -1;
      for (var i = parseInt(arr.length/2) -1; i >= 0; i--) {
        heapAdjust(arr,i,end);
      }
      while(end >= 0) {
        swap(arr,0,end--);    //将堆顶元素与尾节点交换后，长度减1，尾元素最大
        heapAdjust(arr,0,end);    //再次对堆进行调整
      }
    }

    function heapAdjust(arr,i,end) {
      var left = 2*i+1, right, flag;
      while(left <= end){  //判断当前父节点有无左节点（即有无孩子节点，left为左节点）
        right = left +1;
        flag = left;
        if (right <= end && arr[left] < arr[right]) {
          flag = right;
        }
        if(arr[i] < arr[flag])    //将父节点与孩子节点交换（如果上面if为真，则arr[flag]为右节点，如果为假arr[flag]则为左节点）
            swap(arr,i,flag);
        else         //说明比孩子节点都大，直接跳出循环语句
            break;
        i = flag;
        left = 2*i+1;
      }
    }

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

归并排序

归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

// 归并排序
        myarr=[2,43,4,7,4,766,7,3,324,54,5455,89];
        console.log("归并排序前：" + myarr);
        mergeSort(myarr, myarr.length);
        console.log("归并排序后：" + myarr);

        function mergeSort(arr, len) {
            var tmpArr = new Array(len);
            mergeSortDevide(arr,0,len-1,tmpArr);
            tmpArr = [];
            return true;
        }

        function mergeSortDevide(arr, first, last, tempArr) {
            if (first < last) {
                var mid = parseInt((first + last)/2);
                mergeSortDevide(arr,first,mid,tempArr);
                mergeSortDevide(arr,mid+1,last,tempArr);
                mergeArray(arr,first,mid,last,tempArr)
            }
        }

        function mergeArray(arr,first,mid,last,tempArr) {
            var i = first, j = mid + 1, m = mid, n = last;
            var k = 0;
            while(i <= m && j <= n){
                if (arr[i] <= arr[j]) {
                    tempArr[k++] = arr[i++];
                } else {
                    tempArr[k++] = arr[j++];
                }
            }

            while(i <= m) {
                tempArr[k++] = arr[i++];
            }
            while(j <= n) {
                tempArr[k++] = arr[j++];
            }

            for(t = 0; t < k; t++){
                arr[first + t] = tempArr[t];
            }

        }

快速排序

对于一字给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再一次对前后两部分的记录进行快速排序，递归该过程，指导序列中所有记录均有序为止。

// 快速排序
        function quickSort(arr, low, high) {
            var i,j,index;
            if (low>high)
                return;
            i = low;
            j = high;
            index = arr[i];
            while(i < j) {
                while(i index)
                    j--;
                if(i

云服务器 GPU云服务器归并排序二路归并排序归并排序算法堆排序排序c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95956.html

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
八大排序算法的Python实现

摘要：是稳定的排序方法。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。算法实现选择排序堆排序描述堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。 1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定...

princekin 2019-07-24 18:09 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

microcosm1994 2019-08-20 16:30 评论0 收藏0