JavaScript實(shí)現(xiàn)堆排序，歸并排序，快速排序

FWHeart 發(fā)布于2019-08-22 18:31 / 3570人閱讀

摘要：歸并排序歸并排序前歸并排序后快速排序?qū)τ谝蛔纸o定的記錄，通過一趟排序后，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再一次對(duì)前后兩部分的記錄進(jìn)行快速排序，遞歸該過程，指導(dǎo)序列中所有記錄均有序?yàn)橹埂?/p>

堆排序

堆排序的基本思想是：將待排序序列構(gòu)造成一個(gè)大頂堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了

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--);    //將堆頂元素與尾節(jié)點(diǎn)交換后，長(zhǎng)度減1，尾元素最大
        heapAdjust(arr,0,end);    //再次對(duì)堆進(jìn)行調(diào)整
      }
    }

    function heapAdjust(arr,i,end) {
      var left = 2*i+1, right, flag;
      while(left <= end){  //判斷當(dāng)前父節(jié)點(diǎn)有無左節(jié)點(diǎn)（即有無孩子節(jié)點(diǎn)，left為左節(jié)點(diǎn)）
        right = left +1;
        flag = left;
        if (right <= end && arr[left] < arr[right]) {
          flag = right;
        }
        if(arr[i] < arr[flag])    //將父節(jié)點(diǎn)與孩子節(jié)點(diǎn)交換（如果上面if為真，則arr[flag]為右節(jié)點(diǎn)，如果為假arr[flag]則為左節(jié)點(diǎn)）
            swap(arr,i,flag);
        else         //說明比孩子節(jié)點(diǎn)都大，直接跳出循環(huán)語(yǔ)句
            break;
        i = flag;
        left = 2*i+1;
      }
    }

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

歸并排序

歸并排序，其的基本思路就是將數(shù)組分成二組A，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序了？

可以將A，B組各自再分成二組。依次類推，當(dāng)分出來的小組只有一個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個(gè)小組就可以了。這樣通過先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

// 歸并排序
        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];
            }

        }

快速排序

對(duì)于一字給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再一次對(duì)前后兩部分的記錄進(jìn)行快速排序，遞歸該過程，指導(dǎo)序列中所有記錄均有序?yàn)橹埂?/p>

// 快速排序
        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