搜索
您的当前位置:首页正文

javascript冒泡排序小结_基础知识

2023-12-02 来源:欧尚宠物网

冒泡排序示例,双向冒泡排序与对双向冒泡排序稍微的改进的可视化效果。

代码很简单,不知道有木有未知bug。大神请勿吐槽

冒泡排序示例

双向冒泡排序示例

双向冒泡排序稍微改进示例

 

小编还为您整理了以下内容,可能对您也有帮助:

JS排序之冒泡排序以及写法?

时间复杂度指的是一个算法执行所耗费的时间

空间复杂度指运行完一个程序所需内存的大小

稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面

不稳定指,如果a=b,a在b的前面,排序后可能会交换位置

原理

依次比较相邻的两个值,如果后面的比前面的小,则将小的元素排到前面。依照这个规则进行多次并且递减的迭代,直到顺序正确。

时间复杂度,空间复杂度,稳定性

1.平均时间复杂度O(n*n)

2.最好情况O(n)

3.最差情况O(n*n)

4.空间复杂度O(1)

5.稳定性:稳定

冒泡排序的写法

两个循环

当i=0的时候,里面的循环完整执行,从j=0执行到j=6,这也就是第一遍排序,结果是将最大的数排到了最后,这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]

当i=1的时候,里面的循环再次完整执行,由于最大的数已经在最后了,没有必要去比较数组的最后两项,这也是j<arr.length-1-i的巧妙之处,结果是[8,15,55,76,21,39,88,94]

说到这里,规律就清楚了,天通苑北大青鸟建议每次将剩下数组里面最大的一个数排到最后面,当第一个循环执行到最后的时候,也就是i=6,此时,j=0,只需要比较数组的第一和第二项,比较完毕,返回。

JavaScript中几种排序算法的简单实现_基础知识

排序算法的实现

我的JS水平就是渣渣,所以我就用类似于JAVA和C的方式来写JavaScript的排序算法了。

而且这里我不讲算法原理,仅仅只是代码实现,可能会有Bug,欢迎大家博客评论指导。

插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

实现代码如下:

时间复杂度为:O(n^2)

当然,该算法是有优化余地的,例如将搜索替换的位置算法改为二分查找。

冒泡排序

经典的排序算法,提到冒泡排序我就心痛。本科时候的必须论文的冒泡排序算法的改进,结果写完论文之后都不能完整的实现冒泡排序算法,好尴尬。

时间复杂度为:O(n^2)

快速排序

非常经典的排序算法,排序过程主要i分为三步:

从数列中挑出一个元素,称为 “基准”(pivot);

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现代码如下:

时间复杂度为:O(nlogn)。

归并排序

也是非常经典的排序算法,我就是借着学习js的机会复习经典的排序算法了。归并排序的思想可以参考我的这篇博客:归并排序。我这里只写js实现。

写归并排序的时候还有一个小插曲:就是js不能自动取整,后来用了parseInt方法,感觉萌萌大。

javascript中的冒泡排序法

冒泡排序的原理是这样的,比方说有五个数字54321,要按从小到大排列;

首先比较前两个,就是5和4,如果第一个小于第二个,不做操作,如果第一个大于第二个,那么交换二者的位置,即变成45321,然后比较第二个和第三个,交换位置,变成43521,然后第三个和第四个,第四个和第五个,这样一次循环下来,变成43215

所以,一层循环的效果就是挑出最大的一个数字5,冒泡到最后面。但是还要挑出第二大,第三大的数字,等等。所以一层循环根本就不够用,必须再套一层才行。像这个例子,五个数字,起码要进行四轮循环才行。至于为什么要this.length-i,是因为第一次比较五个数字,第二个只要比较前四个就行了,第五个肯定是最大的了。。

var array = [5, 4, 3, 2, 1];

var temp = 0;

for (var i = 0; i < array.length; i++)

{

for (var j = 0; j < array.length - i; j++)

{

if (array[j] > array[j + 1])

{

temp = array[j + 1];

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

array[j] = temp;

}

}

}

console.log(array);

js数组排序的几种方法

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一 个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。因此需要用到递归

核心:归并排序,拆分成左右两块数组,分别排序后合并

动图:

4.gif

注意:递归中最小的左右数组比较为单个元素的数组,因此在较上层多个元素对比时,左右两个数组一定是顺序的

代码:

function mergeSort(arr) { const len = arr.length; if (len < 2) return arr; // 递归的终止条件 const middle = Math.floor(len / 2); // 拆分左右数组 const left = arr.slice(0, middle); const right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));}function merge(left, right) { // 将左右两侧比较后进行合并 const ret = []; while (left.length && right.length) { if (left[0] > right[0]) { ret.push(right.shift()); } else { ret.push(left.shift()); } } while (left.length) { ret.push(left.shift()); } while (right.length) { ret.push(right.shift()); } return ret;}

2.5 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn),且它的性能通常比其他的复 杂度为O(nlogn)的排序算法要好。和归并排序一样,快速排序也使用分治的方法,将原始数组分为较小的数组

核心:分治算法,以参考值为界限,将比它小的和大的值拆开

动图:

5.gif

注意:每一次遍历筛选出比基准点小的值

代码:

function quickSort(arr, left = 0, right = arr.length - 1) { // left和right默认为数组首尾 if (left < right) { let partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr;}function partition(arr, left, right) { let pivot = left; let index = left + 1; // 满足比较条件的依次放在分割点后 for (let i = index; i <= right; i += 1) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index += 1; } } swap(arr, index - 1, pivot); // 交换顺序时,以最后一位替换分隔项 return index - 1;}

三、搜索算法

3.1 顺序搜索

顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。

function findItem(item, arr) { for (let i = 0; i < arr.length; i += 1) { if (item === arr[i]) { return i; } } return -1;}

3.2 二分搜索

二分搜索要求被搜索的数据结构已排序。以下是该算法遵循的步骤:

  1. 选择数组的中间值
  2. 如果选中值是待搜索值,那么算法执行完毕
  3. 如果待搜索值比选中值要小,则返回步骤1在选中值左边的子数组中寻找
  4. 如果待搜索值比选中值要大,则返回步骤1在选中值右边的子数组中寻找
function binarySearch(item, arr) { arr = quickSort(arr); // 排序 let low = 0; let high = arr.length - 1; let mid; while (low <= high) { min = Math.floor((low + high) / 2); if (arr[mid] < item) { low = mid + 1; } else if (arr[mid] > item) { high = mid - 1; } else { return mid; } } return -1;}

四、算法复杂度

4.1 理解大O表示法

大O表示法用于描述算法的性能和复杂程度。分析算法时,时常遇到一下几类函数

2.png

(1)O(1)

function increment(num){ return ++num;}

执行时间和参数无关。因此说,上述函数的复杂度是O(1)(常数)

(2)O(n)

顺序搜索函数为例,查找元素需要遍历整个数组,直到找到该元素停止。函数执行的总开销取决于数组元素的个数(数组大小),而且也和搜索的值有关。但是函数复杂度取决于最坏的情况:如果数组大小是10,开销就是10;如果数组大小是1000,开销就是1000。这种函数的时间复杂度是O(n),n是(输入)数组的大小

(3)O(n2)

冒泡排序为例,在未优化的情况下,每次排序均需进行n*n次执行。时间复杂度为O(n2)

时间复杂度O(n)的代码只有一层循环,而O(n2)的代码有双层嵌套循环。如 果算法有三层遍历数组的嵌套循环,它的时间复杂度很可能就是O(n3)

4.2 时间复杂度比较

(1)常用数据结构时间复杂度

3.png

(2)排序算法时间复杂度

4.png

相关视频教程推荐:《JavaScript教程》

js数组排序的几种方法

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一 个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。因此需要用到递归

核心:归并排序,拆分成左右两块数组,分别排序后合并

动图:

4.gif

注意:递归中最小的左右数组比较为单个元素的数组,因此在较上层多个元素对比时,左右两个数组一定是顺序的

代码:

function mergeSort(arr) { const len = arr.length; if (len < 2) return arr; // 递归的终止条件 const middle = Math.floor(len / 2); // 拆分左右数组 const left = arr.slice(0, middle); const right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right));}function merge(left, right) { // 将左右两侧比较后进行合并 const ret = []; while (left.length && right.length) { if (left[0] > right[0]) { ret.push(right.shift()); } else { ret.push(left.shift()); } } while (left.length) { ret.push(left.shift()); } while (right.length) { ret.push(right.shift()); } return ret;}

2.5 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn),且它的性能通常比其他的复 杂度为O(nlogn)的排序算法要好。和归并排序一样,快速排序也使用分治的方法,将原始数组分为较小的数组

核心:分治算法,以参考值为界限,将比它小的和大的值拆开

动图:

5.gif

注意:每一次遍历筛选出比基准点小的值

代码:

function quickSort(arr, left = 0, right = arr.length - 1) { // left和right默认为数组首尾 if (left < right) { let partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr;}function partition(arr, left, right) { let pivot = left; let index = left + 1; // 满足比较条件的依次放在分割点后 for (let i = index; i <= right; i += 1) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index += 1; } } swap(arr, index - 1, pivot); // 交换顺序时,以最后一位替换分隔项 return index - 1;}

三、搜索算法

3.1 顺序搜索

顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。

function findItem(item, arr) { for (let i = 0; i < arr.length; i += 1) { if (item === arr[i]) { return i; } } return -1;}

3.2 二分搜索

二分搜索要求被搜索的数据结构已排序。以下是该算法遵循的步骤:

  1. 选择数组的中间值
  2. 如果选中值是待搜索值,那么算法执行完毕
  3. 如果待搜索值比选中值要小,则返回步骤1在选中值左边的子数组中寻找
  4. 如果待搜索值比选中值要大,则返回步骤1在选中值右边的子数组中寻找
function binarySearch(item, arr) { arr = quickSort(arr); // 排序 let low = 0; let high = arr.length - 1; let mid; while (low <= high) { min = Math.floor((low + high) / 2); if (arr[mid] < item) { low = mid + 1; } else if (arr[mid] > item) { high = mid - 1; } else { return mid; } } return -1;}

四、算法复杂度

4.1 理解大O表示法

大O表示法用于描述算法的性能和复杂程度。分析算法时,时常遇到一下几类函数

2.png

(1)O(1)

function increment(num){ return ++num;}

执行时间和参数无关。因此说,上述函数的复杂度是O(1)(常数)

(2)O(n)

顺序搜索函数为例,查找元素需要遍历整个数组,直到找到该元素停止。函数执行的总开销取决于数组元素的个数(数组大小),而且也和搜索的值有关。但是函数复杂度取决于最坏的情况:如果数组大小是10,开销就是10;如果数组大小是1000,开销就是1000。这种函数的时间复杂度是O(n),n是(输入)数组的大小

(3)O(n2)

冒泡排序为例,在未优化的情况下,每次排序均需进行n*n次执行。时间复杂度为O(n2)

时间复杂度O(n)的代码只有一层循环,而O(n2)的代码有双层嵌套循环。如 果算法有三层遍历数组的嵌套循环,它的时间复杂度很可能就是O(n3)

4.2 时间复杂度比较

(1)常用数据结构时间复杂度

3.png

(2)排序算法时间复杂度

4.png

相关视频教程推荐:《JavaScript教程》

没有中间变量的javascript冒泡排序

// 冒泡排序必须创建一个变量吗? 答案: NO NO NO! 不信请看下方↓↓↓

// 知识重点:连续对 2 个变量使用 3 次异或运算,可以交换两者的值!

let a = 10,
    b = 99;

    a ^= b;
    b ^= a;
    a ^= b;

console.log(a) // 99
console.log(b) // 10

------------------------------------------------------------------------------

示例: 冒泡排序

let numList = [2,6,4,1,9,8,10,7,5,3],
    numListLen = numList.length;

for(let i = 0; i < numListLen; i++){
    for(let j = 0; j < numListLen; j++){
        if(numList[j] > numList[j+1]){
            numList[j] ^= numList[j+1];
            numList[j+1] ^= numList[j];
            numList[j] ^= numList[j+1];
        }
    }
}

console.log(numList); //  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

没有中间变量的javascript冒泡排序

// 冒泡排序必须创建一个变量吗? 答案: NO NO NO! 不信请看下方↓↓↓

// 知识重点:连续对 2 个变量使用 3 次异或运算,可以交换两者的值!

let a = 10,
    b = 99;

    a ^= b;
    b ^= a;
    a ^= b;

console.log(a) // 99
console.log(b) // 10

------------------------------------------------------------------------------

示例: 冒泡排序

let numList = [2,6,4,1,9,8,10,7,5,3],
    numListLen = numList.length;

for(let i = 0; i < numListLen; i++){
    for(let j = 0; j < numListLen; j++){
        if(numList[j] > numList[j+1]){
            numList[j] ^= numList[j+1];
            numList[j+1] ^= numList[j];
            numList[j] ^= numList[j+1];
        }
    }
}

console.log(numList); //  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

javascript冒泡排序怎么实现的

你想要什么样的结果?还是不理解。
比方 当1 小于2时,1和2交换位置;
当1小于3时,1和3交换位置;
所有的数据以此类推,才出现这样的结果。

javascript冒泡排序怎么实现的

你想要什么样的结果?还是不理解。
比方 当1 小于2时,1和2交换位置;
当1小于3时,1和3交换位置;
所有的数据以此类推,才出现这样的结果。

关于javascript冒泡排序的一个疑问

封装成函数,方便其它的地方使用,不用每次使用时再写一遍程序。

既然封装成函数了,就一定需要对传入的参数进行验证,这样起到了严谨性。

追问这里实现了传入参数验证么?
var a = arr[i];
var b = arr[i + dir];
var c = a;
arr[i] = b;
arr[i + dir] = c;

追答if (dir === 1) {
start = 0;
end = arr.length;
} else if (dir === -1) {
start = arr.length - 1;
end = -1;
}
这个是一个验证,其实就是一个升序还是降序排列的一个验证。

关于javascript冒泡排序的一个疑问

封装成函数,方便其它的地方使用,不用每次使用时再写一遍程序。

既然封装成函数了,就一定需要对传入的参数进行验证,这样起到了严谨性。

追问这里实现了传入参数验证么?
var a = arr[i];
var b = arr[i + dir];
var c = a;
arr[i] = b;
arr[i + dir] = c;

追答if (dir === 1) {
start = 0;
end = arr.length;
} else if (dir === -1) {
start = arr.length - 1;
end = -1;
}
这个是一个验证,其实就是一个升序还是降序排列的一个验证。

谁能用javascript的冒泡算法排一下54321.要求每一步都要说明原因噢!谢谢各位亲了

var a=[];

for( var i=1; i<1000;i++){

a.push(Math.round(100*Math.random()*10*Math.random()*10));

}

var l=a.length;

var k=0,p=0;

function b(){

var g=new Date(),s=g.getTime();

for(var i=0;i<l;i++){

for(var j=i;j<l;j++){

k++;

if(a[i]>a[j]){

var m=a[j];

a[j]=a[i];

a[i]=m;

}

}

}

var v=new Date(),h=v.getTime();

var pb=document.createElement('p');

pb.innerHTML="冒泡排序需要计算"+k+"次"+(h-s)+"毫秒";

document.body.appendChild(pb);

}

b();追问你是学编程的吗?

这道题谁会做,用JavaScript的数组个冒泡排序做,两道题都是的。

<script language="JavaScript" type="text/javascript">

<!--

//冒泡排序

function bubbleSort(arr){

    //外层循环,共要进行arr.length次求最大值操作

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

        //内层循环,找到第i大的元素,并将其和第i个元素交换

        for(var j=i;j<arr.length;j++){

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

                //交换两个元素的位置

                var temp=arr[i];

                arr[i]=arr[j];

                arr[j]=temp;

            }

        }

    }

}

var arr=[32,55,78,43,78,10,45,20,9,89];

bubbleSort(arr);

//输出:89,78,78,55,45,43,32,20,10,9

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

    document.write(arr[i]+",");

}

//-->

</script>

<script>

var a=[1,2,3,5];

alert(Math.max.apply(null, a));//最大值

alert(Math.min.apply(null, a));//最小值

</script>

第一个是冒泡,第二个是求最大值和最小值

欧尚宠物网还为您提供以下相关内容希望对您有帮助:

JS排序之冒泡排序以及写法?

5.稳定性:稳定 冒泡排序的写法 两个循环 当i=0的时候,里面的循环完整执行,从j=0执行到j=6,这也就是第一遍排序,结果是将最大的数排到了最后,这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]当i=...

js数组排序的几种方法

(1)直接插入排序:将第一个数和第二个数排序,然后构成一个有序序列;将第三个数插入进去,构成一个新的有序序列;对第四个数、第五个数...直到最后一个数,重复第二步 (2)二分插入排序:将寻找每个数插入位置...

javascript中的冒泡排序法

冒泡排序的原理是这样的,比方说有五个数字54321,要按从小到大排列;首先比较前两个,就是5和4,如果第一个小于第二个,不做操作,如果第一个大于第二个,那么交换二者的位置,即变成45321,然后比较第二个和第三个,...

JavaScript中几种排序算法的简单实现_基础知识

它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把...

关于javascript冒泡排序的一个疑问

封装成函数,方便其它的地方使用,不用每次使用时再写一遍程序。既然封装成函数了,就一定需要对传入的参数进行验证,这样起到了严谨性。

javascript冒泡排序怎么实现的

你想要什么样的结果?还是不理解。比方 当1 小于2时,1和2交换位置;当1小于3时,1和3交换位置;所有的数据以此类推,才出现这样的结果。

用Javascript写排序算法的动画演示

1.让JavaScript暂停下来,慢下来。JavaScript排序是很快的,要我们肉眼能看到它的实现过程,我首先想到的是让排序慢下来。 排序的每一个循环都让它停300ms然后再继续进行。 怎么样才能停下来呢。查了一下JavaScript貌似没有...

冒泡排序流程图怎么画

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是冒泡排序算法:冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个...

请问一个关于javascript排序的问题

我看懂 原来是冒泡排序呀 function bubbleSort(array) { if(Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for(var i = 0; i &lt; len - 1; ...

,使用冒泡排序法把其中的数字按从大到小的顺序排序,并输出排序前和排序...

数组哪有join方法?你说的是js吧 下面是js的代码: 冒泡排序 function BubbleSort(array){ var temp;for (var i = 1; i &lt; array.length; i++) { for (var j = array.length - 1; j &gt;= i; j--)...

本文如未解决您的问题请添加抖音号:51dongshi(抖音搜索懂视),直接咨询即可。

Top