请选择 进入手机版 | 继续访问电脑版

HTML5星空

冒泡排序

[复制链接]
发表于 2017-9-1 03:18:31 | 显示全部楼层 |阅读模式

冒泡排序可能是很多人接触的第一个排序算法,也是一种简单、又易于理解的算法。

冒泡排序名字由来是因为其排序过程中越小的元素会经由交换慢慢“浮”到数列的顶端。


原理概述:

冒泡排序会重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序颠倒就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。


算法执行步骤

(1). 遍历数组,比较相邻的元素。如果前者比后者大,就交换双方的位置;

(2). 依次完成每一对相邻元素的比较,数列末尾的元素应是每次循环,所有参与排序元素中最大的数;

(3). 重复步骤1~2,直到排序完成。


代码部分:

// 原始冒泡排序
function bubbleSort(arr) {

   console.time('排序耗时');
   
   var len = arr.length;
   
   for (var i = 0; i < len; i++) {
       for (var j = 0; j < len-1-i; j++) {
           if (arr[j] > arr[j+1]) {
               var temp = arr[j+1];
               arr[j+1] = arr[j];
               arr[j]   = temp;
           }
       }
   }
   
   console.timeEnd(
'排序耗时');

   return arr;
   
}

动图演示:


下面介绍两种对原始冒泡排序的修改(它们的具体表现如何,大家可以进行测试)
修改一:(设置一变量,取值为最后一次循环中最后一对发生位置交换的相邻元素中前者在数组中的索引)

// 修改1
function
bubbleSort1(arr) {


   console.time('排序耗时');
   
   var i = arr.length - 1;
   
   while (i > 0) {
   
       var pos = 0;
       
       for (var j = 0; j < i; j++) {
           if (arr[j] > arr[j+1]) {
               var temp = arr[j+1];
               arr[j+1] = arr[j];
               arr[j]   = temp;
               pos = j;
           }
       }
       
       // console.log(arr);
       i = pos;
       
   }
   
   console.timeEnd('排序耗时');
   
   return arr;
   
}


修改二:(从正反双向对数列进行排序)

// 修改2
function bubbleSort2(arr) {

   
console.time('排序耗时');
   
   
var low = 0;
   
var high =arr.length - 1;
   
var temp;
   
var i;
   
   
while (low < high) {
       
for (i = low; i < high; i++) {
           
if (arr[i] > arr[i+1]) {
               temp = arr[i+1];
               arr[i+1] = arr[i];
               arr[i] = temp;
           }
       }
       high--;
       
       
for (i = high; i > low; i--) {
           
if (arr[i] < arr[i-1]) {
               temp = arr[i-1];
               arr[i-1] = arr[i];
               arr[i] = temp;
           }
       }
       low++;
       
   }
   
   
console.timeEnd('排序耗时');
   
   
return arr;
   
}


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快讯
发布主题 快速回复 返回列表

     京ICP备14042305号

html5star team © 2012-2013 html5星空 Comsenz Inc.

GMT+8, 2017-11-25 02:38 , Processed in 0.171477 second(s), 35 queries .

快速回复 返回顶部 返回列表