JavaScript排序性能比较

2011-02-15

排序是经常使用的编程例子，在JavaScript里各种排序的性能又如何呢？每个浏览器测试得出的数据会不一样。比如我用chrome 测试一般快速排序都会最快，IE 则根据数组长度有可能希尔最快。

不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)。

[quickSort]: 0,1,2,3,4,5,6,7,8,9

[insertSort]: 0,1,2,3,4,5,6,7,8,9

[shellSort]: 0,1,2,3,4,5,6,7,8,9

[systemSort]: 0,1,2,3,4,5,6,7,8,9

[bubbleSort]: 0,1,2,3,4,5,6,7,8,9

快速排序插入排序希尔排序系统方法冒泡排序清空

测试数组长度：
测试次数：10次
数组太长请慎用冒泡排序

算法数组长度分别用时(毫秒) 平均(毫秒) 点击测试

快速排序	1000	1, 1, 0, 1, 0, 0, 0, 0, 0, 0,	0.3	测试
插入排序	1000	2, 2, 1, 1, 1, 1, 1, 2, 1, 1,	1.3	测试
希尔排序	1000	1, 0, 1, 0, 0, 0, 1, 1, 0, 0,	0.4	测试
系统方法	1000	0, 0, 0, 0, 0, 1, 0, 0, 0, 1,	0.2	测试
冒泡排序	1000	6, 5, 5, 5, 3, 4, 5, 5, 5, 5,	4.8	小心测试

个人理解：

冒泡排序：最简单，也最慢，貌似长度小于7最优
插入排序：比冒泡快，比快速排序和希尔排序慢，较小数据有优势
快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合
希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快
系统方法：在forfox下系统的这个方法非常快

JavaScript Code

001

<script type="text/javascript">

002
Jun = {};

003
Jun.array = {

004

005

006

    df:function(len){

007

        var array = [], i;

008

        len = len || 1000;

009

        for(i = 0; i< len; i++){

010

            array.push(i);

011

        }

012

        return array.sort(function(){ return Math.random() > 0.5});

013

    },

014

    // Jun.array.test();

015

    test:function(method, arrayLength, callBack){

016

017

        var times = [];

018

        var i = 0;

019

        var sum = 0;

020

        var len = 10;

021

022

        for(;i<len;i++){

023

            test();

024

        }

025

026

        for(i=0;i<times.length;i++){

027

            sum+=times[i];

028

        }

029

030

031
 
032

        function test(){

033

            var array = Jun.array.df(arrayLength);

034

            var st = new Date().getTime();

035

            Jun.array[method](array); //shellSort  quickSort  systemSort

036

            var d = new Date().getTime() - st;

037

            callBack && callBack(new Date().getTime() - st);

038

            times.push(d);

039

        }

040

041

        return sum / len;

042

    },

043

044

    // ---------- 一些排序算法

045

    // js 利用sort进行排序

046

    systemSort:function(array){

047

        return array.sort(function(a, b){

048

            return a - b;

049

        });

050

    },

051

    // 冒泡排序

052

    bubbleSort:function(array){

053

        var i = 0, len = array.length,

054

            j, d;

055

        for(; i<len; i++){

056

            for(j=0; j<len; j++){

057

                if(array[i] < array[j]){

058

                    d = array[j];

059

                    array[j] = array[i];

060

                    array[i] = d;

061

                }

062

            }

063

        }

064

        return array;

065

    },

066

    // 快速排序

067

    quickSort:function(array){

068

        //var array = [8,4,6,2,7,9,3,5,74,5];

069

        //var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];

070

        var i = 0;

071

        var j = array.length - 1;

072

        var Sort = function(i, j){

073

074

            // 结束条件

075

            if(i == j ){ return };

076

077

            var key = array[i];

078

            var stepi = i; // 记录开始位置

079

            var stepj = j; // 记录结束位置

080

081

            while(j > i){

082

                // j <<-------------- 向前查找

083

                if(array[j] >= key){

084

                    j--;

085

                }else{

086

                    array[i] = array[j]

087

                    //i++ ------------>>向后查找

088

                    while(j > ++i){

089

                        if(array[i] > key){

090

                            array[j] = array[i];

091

                            break;

092

                        }

093

                    }

094

                }

095

            }

096

097

            // 如果第一个取出的 key 是最小的数

098

            if(stepi == i){

099

                Sort(++i, stepj);

100

                return ;

101

            }

102

103

            // 最后一个空位留给 key

104

            array[i] = key;

105

106

            // 递归

107

            Sort(stepi, i);

108

            Sort(j, stepj);

109

        }

110

111

        Sort(i, j);

112

113

        return array;

114

    },

115

116

    // 插入排序

117

    insertSort:function(array){

118

119

        // http://baike.baidu.com/image/d57e99942da24e5dd21b7080

120

        // http://baike.baidu.com/view/396887.htm

121

        //var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];

122

123

        var i = 1, j, step, key,

124

            len = array.length;

125

126

        for(; i < len; i++){

127

128

            step = j = i;

129

            key = array[j];

130

131

            while(--j > -1){

132

                if(array[j] > key){

133

                    array[j+1] = array[j];

134

                }else{

135

                    break;

136

                }

137

            }

138

139

            array[j+1] = key;

140

        }

141

142

        return array;

143

    },

144

145

    // 希尔排序

146

    //Jun.array.shellSort(Jun.array.df(10000));

147

    shellSort:function(array){

148
 
149

        // http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

150

        // var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];

151

152

        var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组

153

        //var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择

154

        var i = 0;

155

        var stepArrLength = stepArr.length;

156

        var len = array.length;

157

        var len2 =  parseInt(len/2);

158

159

        for(;i < stepArrLength; i++){

160

            if(stepArr[i] > len2){

161

                continue;

162

            }

163

164

            stepSort(stepArr[i]);

165

        }

166
 
167

        // 排序一个步长

168

        function stepSort(step){

169

170

            //console.log(step) 使用的步长统计

171

172

            var i = 0, j = 0, f, tem, key;

173

            var stepLen = len%step > 0 ?  parseInt(len/step) + 1 : len/step;

174

175

176

            for(;i < step; i++){// 依次循环列

177
 
178

                for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循环每列的每行

179

                    tem = f = step * j + i;

180

                    key = array[f];

181
 
182

                    while((tem-=step) >= 0){// 依次向上查找

183

                        if(array[tem] > key){

184

                            array[tem+step] = array[tem];

185

                        }else{

186

                            break;

187

                        }

188

                    }

189

190

                    array[tem + step ] = key;

191

192

                }

193

            }

194

195

        }

196

197

        return array;

198

199

    }

200

 };

201
</script>

202
 
203

<script type="text/javascript">

204

    var jelle = {

205

        index:1,

206

        $:function(id){

207

            return document.getElementById(id);

208

        },

209

        test:function(method, num){

210

            var arrayLength = parseInt(jelle.$('arrayLength').value);

211

            jelle.index = num;

212

            jelle.$('length_'+num).innerHTML = arrayLength;

213

            jelle.$('times_'+num).innerHTML = '';

214

            jelle.$('time_'+num).innerHTML = Jun.array.test(method, arrayLength, jelle.insert);;

215

        },

216

        insert:function(num){

217

            jelle.$('times_'+jelle.index).innerHTML += num+', ';

218

        },

219

        correctness:function(method){

220

            var array = new Function('return '+ jelle.$('testArray').value)();

221

            jelle.$('testResults').innerHTML += '<div>['+method+']: '+Jun.array[method](array)+'</div>';

222

        }

223

    }

224
</script>