天天看點
傳回

經典排序算法解析

經典排序算法解析

    許多進階語言中都提供有排序函數，但是掌握一些經典排序算法的基本原理和編碼方法還是很有必要，這個學習過程可以幫助我們更好的了解每種排序算法的設計思路，本篇部落格将介紹9種十分經典的排序算法，提供了解釋性語言JavaScript與編譯型語言C的源代碼。

一、直接插入排序

    直接插入排序是最簡單的一種排序算法，也最容易了解。它的核心思想為将元素逐個插入一個有序的數列中。用文字描述可以分為如下幾步：

1.把數列中的第一個元素取出，作為有序數列的起始元素。

2.依次拿數列中的其他元素與有序數列中的元素進行比較，将其插入正确的位置。

用圖示描述插入排序如下：

經典排序算法解析

直接插入排序的特點是對新元素的每輪插入前，有序數列中的所有元素都是排序好的，即任意時刻，被排序動過的元素組成的數列都是有序的。

用JavaScript實作的簡單插入排序：

//插入排序
var array = [1,54,2,64,12,65,76,46,34,98];
for(var i = 0;i<array.length-1;i++){
    var temp = array[i+1];
    for(var j = i+1;j>0;j--){
        if (temp<array[j]) {
            array[j+1] = array[j];
            array[j] = temp;
        }
    }
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

用C實作的簡單插入排序：

#include <stdio.h>
void mySort(int array[],int size){
    for(int i=0;i<size-1;i++){
        int temp = array[i+1];
        for(int j=i+1;j>0;j--){
            if(temp<array[j]){
                array[j+1] = array[j];
                array[j] = temp;
            }
        }    
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
    mySort(a,10);
    for(int i = 0;i<10;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

二、二分插入排序(折半插入排序)

    二分插入排序也是插入排序的一種，其又叫做折半插入排序。它與直接插入排序的唯一不同隻在于查找插入位置的方式。直接插入排序是通過周遊來查找要插入元素的位置，二分插入排序則是通過二分法來查找要插入的位置，之後将此位置所有元素後移，将排序的元素進行插入。

JavaScript實作的二分插入排序：

var array = [1,54,2,64,12,65,76,46,34,98];
//二分插入排序
for(var i=0;i<array.length-1;i++){
    var temp = array[i+1];
    var left = 0;
    var right = i;
    var middle;
    while(left<=right){
        middle = Math.round((left+right)/2);
        if (array[middle]>temp) {
            right=middle-1;
        }else{
            left = middle+1;
        }
    }
    for(var j=i+1;j>left;j--){
        array[j] = array[j-1];
    }
    array[left] = temp;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];

C實作的二分插入排序：

#include <stdio.h>
//二分插入排序
void mySort(int array[],int size){
    for(int i=0;i<size-1;i++){
        int temp = array[i+1];
        int left=0,right=i,middle;
        while(left<=right){
            middle = (left+right)/2;
            if(array[middle]>temp){
                right=middle-1;
            }else {
                left = middle+1;
            }
        }
        for(int j =i+1;j>left;j--){
            array[j] = array[j-1];
        }    
        array[left] = temp;
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
    mySort(a,10);
    for(int i = 0;i<10;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

三、希爾排序

    希爾排序也是插入排序的一種，它先将整個數列分割成若幹個小的子序列進行插入排序，逐漸減少子序列的個數，直到最後組合成一個數列，完成整個排序過程。希爾排序的過程使用文字描述可以表示為如下幾步：

1.假設數列元素個數為n，先取一個小于n的增量d1，将所有間隔d1距離的元素放為1組進行插入排序，d1通常取值n/2，向下取整。

2.再次取d2<d1，将所有間隔d2距離的元素放為1組進行插入排序，通常d2取值為d1/2，向下取整。

3.重複步驟2，直到取得d等于1。

圖示希爾排序如下：

經典排序算法解析

JavaScript實作的希爾排序：

var array = [1,54,2,64,12,65,76,46,34,98];
//希爾排序
//步長 分組數
var d = Math.floor(array.length/2);
while(d>=1){
    //每組元素個數
    var counts = Math.floor(array.length/d);
    //每組排序依次
    for (var i = 0; i < d ; i++) {
        //組内的插入排序
        for(var j = 0;j<counts-1;j++){
            var temp = array[(j+1)*d];
            for(var k = ((j+1)*d);k>0;k-=d){
                if (temp<array[k]) {
                    array[k+d] = array[k];
                    array[k] = temp;
                }
            }
        }
    }
    //重取d值
    d=Math.floor(d/2);
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];

C實作的希爾排序：

#include <stdio.h>
//希爾排序
void mySort(int array[],int size){
    int d = size/2;
    while(d>=1){
    //每組元素個數
    int counts = size/d;
    //每組排序依次
    for (int i = 0; i < d ; i++) {
        //組内的插入排序
        for(int j = 0;j<counts-1;j++){
            int temp = array[(j+1)*d];
            for(int k = ((j+1)*d);k>0;k-=d){
                if (temp<array[k]) {
                    array[k+d] = array[k];
                    array[k] = temp;
                }
            }
        }
    }
    //重取d值
    d=d/2;
}
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
    mySort(a,10);
    for(int i = 0;i<10;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

四、選擇排序

        前邊所說的3種排序算法原理上都是插入排序，即從無序數列中逐個取元素将其插入到有序數列中的合适位置。選擇排序則剛好與之相反，其從無序數列中先找到最小值，放在排序數列首部，在依次找到剩餘數列的中最小值追加入有序數列，最終完成數列的排序。用文字描述選擇排序步驟不如：

1.找到數列中的最小值，将其作為有序數列的第一個元素。

2.從剩餘數列中找到最小值，追加入有序數列。

3.重複步驟2，直到排完整個數列。

圖示描述選擇排序如下：

經典排序算法解析

JavaScript實作的選擇排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];
//選擇排序
for(var i=0;i<array.length-1;i++){
    //找到最小值
    var min = array[i];
    var index = i;
    for (var j = i+1; j <array.length; j++) {
        if (array[j]<min) {
            min = array[j];
            index = j;
        }
    }
    //進行交換
    array[index]=array[i];
    array[i]=min;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C實作的選擇排序算法：

//選擇排序
void mySort(int array[],int size){
    for(int i=0;i<size-1;i++){
        int min = array[i];
        int index = i;
        for(int j=i+1;j<size;j++){
            if(array[j]<min){
                min = array[j];
                index = j;
            }
        }
        array[index] = array[i];
        array[i]=min;    
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
    mySort(a,11);
    for(int i = 0;i<10;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

五、冒泡排序

      冒泡排序和選擇排序是我們學習程式設計課時必不可少的兩種排序算法，冒泡排序算法的核心是每次比較相鄰的連個元素，如果它們的順序不對，則進行交換，一輪排序下來，最大值一定被排序到數列的末端。之後除去最後一個元素再進行第二輪冒泡，直到整個數列排序完成。用文字描述冒泡排序的過程如下：

1.從左向右依次比較相鄰兩元素，如果順序不對，則進行交換，最終最大的元素被放在最後。

2.除去最後一個元素，重複步驟1，最終剩下元素中最大的被放在倒數第2個位置。

3.繼續上面的重複，直到排完整個數列。

經典排序算法解析

JavaScript實作的冒泡排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];
//冒泡排序
for(var i=0;i<array.length-1;i++){
    for(var j=0;j<array.length-i-1;j++){
        var temp = array[j];
        if (temp>array[j+1]) {
            array[j] = array[j+1];
            array[j+1] = temp;
        }
    }
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C實作的冒泡排序算法：

#include <stdio.h>
//冒泡排序
void mySort(int array[],int size){
    for(int i =0;i<size-1;i++){
        for(int j=0;j<size-1-i;j++){
            int temp = array[j];
            if(temp>array[j+1]){
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
    mySort(a,10);
    for(int i = 0;i<10;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

六、雙向冒泡排序

    雙向冒泡排序是冒泡排序的一種變體，冒泡排序每次比較都是從左向右，找出最大的放在最後。雙向冒泡排序則是第一輪從左向右将最大的放最後，第二輪從右向左将最小的放最首，如此交替直到整個數列排序完成。文字描述雙向冒泡排序步驟如下：

1.從左向右依次比較相鄰兩個元素，如果順序不對，則進行交換，如此一輪下來，最大的元素在最後。

2.除去已經排序好的元素，從右向左依次比較相鄰的兩個元素，如果順序不對，則進行交換，最小的元素在首部。

3.交替重複步驟1與步驟2直到排序完成。

雙向冒泡排序示意圖如下：

經典排序算法解析

JavaScript實作的雙向冒泡排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];
//雙向冒泡排序
var start = 0;
var end = array.length;
while(end-start>0){
    //從左向右冒泡
    for(var i=start;i<end-1;i++){
        var temp = array[i];
        if (array[i+1]<temp) {
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }
    end--;
    //從右向左冒泡
    for(var j=end;j>start+1;j--){
        var temp = array[j];
        if (array[j-1]>temp) {
            array[j] = array[j-1];
            array[j-1] = temp;
        }
    }
    start++;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]

C實作的雙向冒泡排序算法：

#include <stdio.h>
//雙向冒泡排序
void mySort(int array[],int size){
    int start = 0;
    int end = size;
    //從左向右冒泡
    for(int i=start;i<end-1;i++){
        int temp = array[i];
        if (array[i+1]<temp) {
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }
    end--;
    //從右向左冒泡
    for(int j=end;j>start+1;j--){
        int temp = array[j];
        if (array[j-1]>temp) {
            array[j] = array[j-1];
            array[j-1] = temp;
        }
    }
    start++;
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,33};
    mySort(a,11);
    for(int i = 0;i<11;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

七、快速排序算法

    快速排序算法和基本思路是通過一趟排序将數列分成兩部分，其中一部分的所有資料都比另一部分小。之後在分别在兩個子數列中進行遞歸，直到最終排序完成。快速排序算法的核心是遞歸，是以其效率十分高。用文字描述快速排序的步驟如下：

1.随機取一個元素作為基準，将小于此元素的資料都放在此元素的左側，大于此元素的資料都放在此元素的右側，将數列分隔成左右兩個子數列。

2.分别對左右子數列進行步驟1的遞歸，直到數列長度為1或者0，表示排序完成。

經典排序算法解析

JavaScript實作的快速排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//快速排序
function sort(array, left, right) {
    if (right - left >= 1) {
        //取第一個元素作為基準
        let base = array[left];
        let i = left + 1;
        let index = left;
        while (i <= right) {
            //大于等于的已經在右邊 不需要修改 小于的要放在左邊
            if (array[i] < base) {
                if (index + 1 == i) {
                    //交換
                    array[index] = array[i];
                    array[i] = base;
                    index++;
                } else {
                    //先将base與其後一個元素交換
                    array[index] = array[index + 1];
                    array[index + 1] = base;
                    //交換
                    let temp = array[index];
                    array[index] = array[i];
                    array[i] = temp;
                    index++;
                }

            }
            i++;
        }
        //遞歸排序
        sort(array, left, index - 1);
        sort(array, index + 1, right);
    }
}
sort(array, 0, array.length - 1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C語言實作的快速排序：

#include <stdio.h>
//快速排序
void mySort(int array[],int left,int right){
    if(right-left>=1){
        int base = array[left];
        int i = left+1;
        int index = left;
        while(i<=right){
            if(array[i]<base){
                if(index+1==i){
                    array[index] = array[i];
                    array[i]=base;
                    index = i;
                }else{
                    array[index]=array[index+1];
                    array[index+1] = base;
                    int temp = array[index];
                    array[index] = array[i];
                    array[i] = temp;
                    index++;
                }
            }
            i++;
        }
        mySort(array, left, index-1);
        mySort(array, index+1, right);
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
    mySort(a,0,10);
    for(int i = 0;i<11;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

八、堆排序

    堆排序是比快速排序更加複雜的一種排序算法。堆排序使用到了堆這樣一種資料結構。首先我們需要搞清楚什麼是堆結構。堆是一種類似完全二叉樹，同時又滿足如下條件的資料結構：所有子節點的值總是小于(大于)父節點。所有子節點的值都小于父節點的堆叫大頂堆，所有子節點都大于父節點的堆叫小頂堆。

    二叉樹你應該比較熟悉，下圖就是一個小頂堆的示例：

經典排序算法解析

此二叉樹中任何一個子節點的值都是大于父節點。如何将數列構造成這樣一個堆結構呢，其實十分簡單，将數列按照從上到下，從左到右的原則來構造完全二叉樹即可。例如如下數列[1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34]如果将其構造成堆如下圖所示：

經典排序算法解析

正常情況下，這個由數組映射成的二叉樹并不符合我們堆的要求，否則也就不需要我們用算法來排序了。要讓這個二叉樹符合要求，我們需要進行整理，即從末節點開始進行調整，例如先從12，98，34中找到最小的，放在現在12所在的位置，然後從64，46，34中找到最小的元素進行上浮，接着再一層層上浮上去，直到堆頂元素為所有元素中的最小元素。整理完成後，我們隻需要将堆頂元素和最後一個元素進行交換，之後除掉最後一個元素再進行堆整理，整理完成後再将頂元素(此時為第2小)與倒數第二個元素交換，依次進行下去，即可完成數列的排序。

    用文字描述堆排序步驟如下：

1.先将數列整理成符合要求的堆。

2.将首末元素交換。

3.除掉最後一個元素在進行堆的整理。

4.重複進行2和3，直到數列排序完成。

JavaScript實作的堆排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//堆排序
//堆調整 大頂
function store(array,index,end){
    let top = array[index];
    let left;
    let right;
    if (index*2+1<=end) {
        left = index*2+1;
    }else{
        //沒有左子樹 說明已經是葉子節點
        //無需調整直接return
        return;
    }
    if (index*2+2<=end) {
        right = index*2+2;
    }else{
        //沒有右子樹 調整左子樹即可
        if (array[left]>top) {
            array[index] = array[left];
            array[left] = top;
            top = array[index];
        }
        return;
    }
    //找出堆單元中的最大值
    if (array[left]>top) {
        array[index] = array[left];
        array[left] = top;
        top = array[index];        
    }
    if (array[right]>top) {
        array[index] = array[right];
        array[right] = top;
        top = array[index];
    }
}
function sort(array,end){
    //先将堆進行調整 倒叙調整
    let i = end;
    while(i>=0){
        store(array,i,end)
        i--;
    }
    //根節點一定是最大的 放最後 再進行堆整理
    let temp = array[end];
    array[end] = array[0];
    array[0] = temp;
    end--;
    if (end>0) {
        sort(array,end);
    }else{
        return;
    }
    
}
sort(array, array.length-1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C語言實作的堆排序算法：

#include <stdio.h>
void store(int array[],int index,int end){
    int top = array[index];
    int left;
    int right;
    if (index*2+1<=end) {
        left = index*2+1;
    }else{
        //沒有左子樹 說明已經是葉子節點
        //無需調整直接return
        return;
    }
    if (index*2+2<=end) {
        right = index*2+2;
    }else{
        //沒有右子樹 調整左子樹即可
        if (array[left]>top) {
            array[index] = array[left];
            array[left] = top;
            top = array[index];
        }
        return;
    }
    //找出堆單元中的最大值
    if (array[left]>top) {
        array[index] = array[left];
        array[left] = top;
        top = array[index];        
    }
    if (array[right]>top) {
        array[index] = array[right];
        array[right] = top;
        top = array[index];
    }
}
void mySort(int array[],int end){
    //先将堆進行調整 倒叙調整
    int i = end;
    while(i>=0){
        store(array,i,end);
        i--;
    }
    //根節點一定是最大的 放最後 再進行堆整理
    int temp = array[end];
    array[end] = array[0];
    array[0] = temp;
    end--;
    if (end>0) {
        mySort(array,end);
    }else{
        return;
    }
    
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
    mySort(a,10);
    for(int i = 0;i<11;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}

需要注意，大頂堆排序完成後為升序，小頂堆排序完成後為降序。

九、歸并排序

    歸并排序的核心并不是交換元素的順序，而是将數列分成多個有序小數列，将相鄰的小數列進行歸并。文字描述歸并排序步驟如下：

1.把長度為n的數列分成長度為1的n個數列。

2.相鄰數列進行排序歸并。

3.重複操作2，直到所有數列歸并成1個整體。

JavaScript實作的歸并排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//歸并排序
function mergeArray(arrL,arrR){
    var tempArray = new Array();
    let i = 0;
    let j = 0;
    while(i<arrL.length && j<arrR.length){
        if (arrL[i]<arrR[j]) {
            tempArray.push(arrL[i]);
            i++;
        }else{
            tempArray.push(arrR[j]);
            j++;
        }
    }
    while(i<arrL.length){
        tempArray.push(arrL[i]);
        i++;
    }
    while(j<arrR.length){
        tempArray.push(arrR[j]);
        j++
    }
    return tempArray;
}
function sort(array){
    if (array.length>1) {
        let arrL = array.slice(0,Math.floor(array.length/2));
        let arrR = array.slice(Math.floor(array.length/2),array.length);
        if (arrL.length>1) {
            arrL = sort(arrL);
        }
        if (arrR.length>1) {
            arrR = sort(arrR);
        }
        return mergeArray(arrL,arrR);    
    }
    return array;
}
console.log(sort(array)); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C語言實作的歸并排序算法：

#include <stdio.h>
void merge(int array[],int temp[],int start,int end,int middle){
    int i=start,j=middle+1,k=start;
    while(i<middle+1 && j<end+1){
        if(array[i]<array[j]){
            temp[k++] = array[i++];
        }else {
            temp[k++] = array[j++];
        }
    }
    while(i<middle+1){
        temp[k++] = array[i++];
    }
    while(j<end+1){
        temp[k++] = array[j++];
    }
    for(i=start;i<=end;i++){
        array[i] = temp[i];
        // printf("%d,",temp[i]);    
    }
}
void sort(int array[],int temp[],int start,int end){
    int middle;
    if(start<end){
        middle = (start+end)/2;
        sort(array, temp, start, middle);
        sort(array, temp, middle+1, end);
        merge(array, temp, start, end, middle);
    }
}
int main(){
    int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
    int b[11] = {0};
    sort(a,b,0,10);
    for(int i = 0;i<11;i++){
        printf("%d\n",a[i]);
    }
    return 0;
}
搜尋推薦 javascript 前端開發 算法 c語言 經典算法排序 排序算法解析 javascript前端開發css javascript程式員前端分享 簡單選擇排序算法
上一篇: 從一些簡單的例子看算法時間複雜度
下一篇: MD5加密原了解析及OC版原理實作

繼續閱讀