2
js--js实现基础排序算法 - 丶Serendipity丶
source link: https://www.cnblogs.com/zaishiyu/p/15768120.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
文本来总结常见的排序算法，通过 JvavScript 来实现
1、冒泡排序
算法思想：比较相邻两个元素的大小，如果第一个比第二个大，就交换它们。从头遍历到尾部，当一轮遍历完后，数组最后一个元素是最大的。除去最后一个元素，对剩下的元素重复执行上面的流程，每次找出剩余元素中最大的，遍历完后，数组是升序的
算法分析：总共需要进行length * (length - 1) / 2 次比较，所以时间复杂度为O(n^2)，因为只需要有一个存放常量的空间，元素本身在原数组上进行交换，所以空间复杂度为O(1)
function bubbleSort(array) {
if (!Array.isArray(array)) {
throw new Error('参数必须为数组');
return;
}
var n = 0, m = 0 // n表示趟数,m表示比较次数
for (let i = array.length - 1; i > 0; i--) { // 外层for表示遍历的趟数
for (let j = 0; j < i; j++) { // 内层for表示每趟需要比较的 j 和 j+1 对应的数
if (arr[j] > arr[j + 1]) {
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
m++
}
n++
}
console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数8 比较次数36
return array
}
var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]
console.log(bubbleSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]
我们在每一轮循环中，可以记住最后一次交换的元素，这之后的元素就肯定是已经排完序的，这样可以减少总的循环次数
function bubbleSort2(array) {
if (!Array.isArray(array)) {
throw new Error('参数必须为数组');
return;
}
var n = 0, m = 0 // n表示趟数,m表示比较次数
for (var i = array.length - 1; i > 0;) { // 用来表示遍历 n-1 趟
var cursor = 0; // 用来记录本轮最后一次交换的元素位置
for (var j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
cursor = j;
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
m++
}
n++
i = cursor;
}
console.log("遍历趟数" + n, "比较次数" + m);//遍历趟数6 比较次数29
return array
}
var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]
console.log(bubbleSort2(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]
2、选择排序
（1）从头遍历到尾部，找出所有项中最大的一个元素
（2）将这个元素和第一个元素交换
（3）对剩下的元素重复进行上面的操作，每次找出剩余中最大的最后的数组是降序排列的
（4） 算法分析
总共需要进行length * (length - 1) / 2 次比较，所以时间复杂度为O(n^2)，因为只需要有两个存放常 量的空间，元素本身在原数组上进行交换，所以空间复杂度为O(1)
function selectSort(array) {
if (!Array.isArray(array)) {
throw new Error('参数必须为数组');
return;
}
for (let i = 0; i < array.length; i++) {
var maxIndex = i, maxValue = array[i] // 设置i为最大元素下标
// 找出剩下元素中的最大值,第一次循环找出最大值
for (let j = i + 1; j < array.length; j++) {
if (array[j] > maxValue) {
maxIndex = j
maxValue = array[j]
}
}
// 如果剩下的元素中最大值下标大于i则发生交换
if (maxIndex > i) {
[array[i], array[maxIndex]] = [array[maxIndex], array[i]]
}
}
return array
}
var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]
console.log(selectSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]
3、插入排序
（1）将数组前面部分看做有序数组
（2）每次将后面部分的第一个与已排序数组作比较，插入到合适的位置
（3）有序数组初始状态有1个数字
（4）算法分析
（5）时间复杂度为O(n^2)
function insertSort(array) {
if (!Array.isArray(array)) {
throw new Error('参数必须为数组');
return;
}
for (var i = 1; i < array.length; i++) {
var temp = array[i] //当前值
for (var j = i; j > 0 && temp < array[j - 1]; j--) {
// 当前值和之前的每个值进行比较，发现有比当前值小的值就进行重新赋值
array[j] = array[j - 1];
}
array[j] = temp;
}
return array;
}
var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]
console.log(insertSort(arr)); //[45, 24, 9, 8, 7, 6, 3, 1, 0]
4、快速排序：
算法思想：将数组的第一个数字作为基准，最后使得基准数字位于数组中间某个位置，它的左边的数字都比它小，它的右边的数字都比它大。
算法实现：设置两个分别指向数组头部和尾部的指针i和j，首先向左移动j，使得array[j] 小于基准。然后向右移动i，使得array[i] 大于基准，交换这两个元素。当i 和j 的值相等时，交换基准与位置i上的元素，然后对i左边以及右边的元素分别进行快速排序。
function quickSort(array) {
const sort = function (arr, left = 0, right = arr.length - 1) {
if (left >= right) {// 递归退出条件
return
}
let i = left, j = right // 定义两个指针
let pivot = arr[i] // 定义基准数据
while (i < j) { // 把所有比基准数
while (j > i && arr[j] >= pivot) { //找到一个比基准值小的数位置为j
j--
}
arr[i] = arr[j] // 将j的值给了i位置的元素，此时j位置还是原来的数
while (i < j && arr[i] < pivot) {
i++
}
arr[j] = arr[i] // 将i位置的值给了j位置的元素，此时i的位置还是原来的数
}
// 本次交换完毕，此时ij两个指针重合,把基准值赋值给i即可
arr[i] = pivot
sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
}
const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr)
return newArr
}
var arr = [7, 3, 6, 9, 24, 0, 1, 45, 8]
console.log(quickSort(arr)); //[0, 1, 3, 6, 7, 8, 9, 24, 45]
以上就是本文的全部内容，希望给读者带来些许的帮助和进步，方便的话点个关注，小白的成长之路会持续更新一些工作中常见的问题和技术点。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK