JavaScript實現堆排序，歸并排序，快速排序

FWHeart 發布于2019-08-22 18:31 / 3577人閱讀

摘要：歸并排序歸并排序前歸并排序后快速排序對于一字給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再一次對前后兩部分的記錄進行快速排序，遞歸該過程，指導序列中所有記錄均有序為止。

堆排序

堆排序的基本思想是：將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余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語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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