Notes.

常见排序算法的 C 语言和 JavaSript 实现之「插入排序」

2016-02-14 • ☕️ 3 min read

前言

排序，一个看似简单的问题其实存在着很深的学问。都说天下武功，无快不破，其实排序也是。排序的速度基本上决定了一个排序算法的好坏（暂不考虑空间复杂度）。常见的排序算法有插入排序，希尔排序，归并排序和快速排序。现在我们分别用C 语言和JavaScript分别实现，并比较这四种排序算法的优劣。此外，我们还比较了不同语言版本（C 语言和JavaScript）的同一种排序算法排序快慢。

插入排序

算法描述

插入排序这 4 中排序里面最慢的，但同时也是最简单的排序算法。它理解起来其实很简单，对于 N 个元素的排序，插入排序由N - 1趟组成。对于这 P = 1 到 P= N - 1 趟中的每一趟 P 而言，插入排序保证从位置 0 到位置 P 上的元素均为已排序状态。在第 P 趟的时候，算法将位置 P 上的元素向左移动到它在前 P+1 个元素中的正确位置。

算法时间复杂度

因为算法需要进行的循环次数为 $1 + 2 + 3 + ... + N = (N + 1) * N / 2$ ，所以算法的时间复杂度为 $O(N^2)$ 。

C 语言实现

int * insert_sort(int* data, int num){
	int i,j, temp;
	for(i = 1; i < num; i ++){
		temp = data[i];
		for(j = i; j > 0 && data[j - 1] > temp; j --){
			data[j] = data[j - 1];
		}
		data[j] = temp; //将第 i 趟的第 i 个元素放到前 i+1 个元素的合适位置
	}
	return data;
}

JavaScript 实现

function insert_sort(data){
    var temp;
    for(var i = 1 ; i < data.length; i ++) {
        temp = data[i];
        for(var j = i; j > 0; j --) {
            if(temp < data[j]) {
                data[j - 1] = data[j]
            }
        }
        data[j] = temp; //将第 i 趟的第 i 个元素放到前 i+1 个元素的合适位置
    }
}

性能横向比较

操作系统：Windows 8 企业版 64 位
软件平台：Visual Studio 10 和 Nodejs v4.2.1
测试数据：100000 条随机生成的数据

C 语言版本的测试代码

/**
*C 语言版本的插入排序测试
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int * insert_sort(int* data, int num);
int main(){
    FILE * file;
    int data_size = 100000;// 测试数据的大小
    int *data = (int*) malloc(sizeof(int) * data_size),temp, i;
    time_t start, end;
    file = fopen("src.txt", "r");
    if(file) {
        for(i = 0; i < data_size && !feof(file); i ++) {
            fscanf(file, "%d", &temp);
            data[i] = temp;
        }// 读取文件中的数据到内存
        start = clock();
        insert_sort(data, data_size);
        end = clock();
        printf("C 语言版 insert_sort: %dms", end - start);
    } else {
        printf("open file src.txt error!");
    }
    getchar();
    return 0;
}

int * insert_sort(int* data, int num){
	int i,j, temp;
	for(i = 0; i < num; i ++){
		temp = data[i];
		for(j = i; j > 0 && data[j - 1] > temp; j --){
			data[j] = data[j - 1];
		}
		data[j] = temp;
	}
	return data;
}

JavaSript 版本的测试代码

var fs = require("fs");
var result;
function insert_sort(data){
    var temp;
    for(var i = 0 ; i < data.length; i ++) {
        temp = data[i];
        for(var j = i; j > 0; j --) {
            if(temp < data[j]) {
                data[j - 1] = data[j]
            }
        }
        data[j] = temp; //将第 i 趟的第 i 个元素放到前 i+1 个元素的合适位置
    }
}

fs.readFile("src.txt", function(err, result){
   data =  result.toString("ascii").split("\n").map(function(value){
        return parseInt(value)
    });
    console.time("javascript 版本 insert_sort");
    insert_sort(data);
    console.timeEnd("javascript 版本 insert_sort")
})

测试结果

C 语言插入排序 JavaScript 语言插入排序从图中我们可以看到，C 语言版本的插入排序和NodeJS版本的插入排序在性能上基本相当，看到Nodejs平台借用 V8 引擎，叼叼的啊！

Personal blog by Natumsol.
Note thoughts and experience.