We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
冒泡、插入、选择排序都有一个共同点,将待排序数列分为已排序和未排序两部分。在未排序的部分中查找一个最值,放到已排序数列的恰当位置。
具体到代码层面,外层循环的变量用于分割已排序和未排序数,内层循环的变量用于在未排序数中查找。从思路上看,这三种算法其实是一样的,所以时间复杂度也相同。
核心:相邻直接进行比较,每次内循环比较一轮过后,都会找到一个最大或最小值。
这里贴出我的错误写法:
function bubbleSort(arr) { for(let i = 0; i < arr.length; i++) { for(let j = i; j < arr.length - 1; j++) { if(arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } let arr = [12, 89, 33, 6, 8, 99, 23]; bubbleSort(arr); console.log(arr);
输出的结果是:
Array(7) [12, 6, 8, 23, 33, 89, 99]
还有一种写法,结果是正确的,但是思想应该不对,我都不知道自己怎么写的
let arrTest = [12, 12, 89, 33, 6, 8, 99, 23]; function bubbleSort(arrTest) { for (let i = 0; i < arrTest.length - 1; i++) { for (let j = i + 1; j < arrTest.length; j++) { if (arrTest[i] > arrTest[j]) { let temp = arrTest[i]; arrTest[i] = arrTest[j]; arrTest[j] = temp; } } } } bubbleSort(arrTest); console.log(arrTest);
输出结果:
Array(8) [6, 8, 12, 12, 23, 33, 89, 99]
这里我做了个分析,发现确实不符合冒泡规则:
那么一个正确的冒泡排序应该是这样的:
let arrTestAnotner = [12, 12, 89, 33, 6, 8, 99, 23]; function bubbleSortAnother(arrTestAnotner) { // 判断数组长度 if(arrTestAnotner.length <= 1) { return; } // 定义一个变量用来保存数组长度,避免每次循环都计算一次 let arrLength = arrTestAnotner.length; for (let i = 0; i < arrLength; ++i) { // 定义一个提前退出循环的标识 let flag = false; // arrLength - i - 1这里多减去一个1,是为了避免内层循环越界 for (let j = 0; j < arrLength - i - 1; ++j) { if (arrTestAnotner[j] > arrTestAnotner[j + 1]) { // 利用解构来赋值 [arrTestAnotner[j], arrTestAnotner[j + 1]] = [ arrTestAnotner[j + 1], arrTestAnotner[j] ]; flag = true; } } // 如果内层循环了一圈都没数据交换,则表明确实是排好序了,所以结束外层循环 if(!flag) break; } } bubbleSortAnother(arrTestAnotner); console.log(arrTestAnotner);
首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
代码如下:
let arr = [12, 12, 89, 33, 6, 8, 99, 23]; function InsertionSort(arr) { let arrLength = arr.length; if(arrLength <= 1) { return; } // 我们把左边当作已排好的序列,右边当作没拍好的序列,每一次内循环下来就会做好一次左边部分的排序(升序) for (let i = 1; i < arrLength; i++) { // 选出一个值 let value = arr[i]; let j = i - 1; for(; j >= 0; j--) { if(arr[j] > value) { arr[j + 1] = arr[j]; }else { break; } } arr[j + 1] = value; } } InsertionSort(arr); console.log(arr);
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
let arr = [12, 12, 89, 33, 6, 8, 99, 23]; function SelectSort(arr) { let arrLength = arr.length; if(arrLength <= 1) { return; } for(let i = 0; i < arrLength - 1; i++) { // 定义一个变量用来保存找到的最大值或最小值的索引 let index = i; for(let j = i + 1; j < arrLength; j++) { // 大于 升序,小于 降序 if(arr[index] > arr[j]) { index = j; } } [arr[i], arr[index]] = [arr[index], arr[i]]; } } SelectSort(arr); console.log(arr);
输出结果为:
The text was updated successfully, but these errors were encountered:
No branches or pull requests
核心
冒泡、插入、选择排序都有一个共同点,将待排序数列分为已排序和未排序两部分。在未排序的部分中查找一个最值,放到已排序数列的恰当位置。
具体到代码层面,外层循环的变量用于分割已排序和未排序数,内层循环的变量用于在未排序数中查找。从思路上看,这三种算法其实是一样的,所以时间复杂度也相同。
冒泡排序
核心:相邻直接进行比较,每次内循环比较一轮过后,都会找到一个最大或最小值。
这里贴出我的错误写法:
输出的结果是:
还有一种写法,结果是正确的,但是思想应该不对,我都不知道自己怎么写的
输出结果:
这里我做了个分析,发现确实不符合冒泡规则:
那么一个正确的冒泡排序应该是这样的:
输出结果:
插入排序
首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
代码如下:
输出结果:
选择排序
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
代码如下:
输出结果为:
The text was updated successfully, but these errors were encountered: