// 冒泡排序 // 原理就是每一轮循环,将一个最大的值放冒泡到最后 // 1.每一趟都是比较相邻两个元素,如果后一个元素大于前一个,则交换两个元素 // 2.第一趟从第一个元素开始进行交换,最后一个元素不参与交换,第二趟最后两个元素不参与交互,以此类推 function bubbleSort(arr) { if (arr.length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 冒泡排序排的趟数=数组的长度-1 // 第一层 for 循环代表一共排序多少趟 for (let i = 0; i < arr.length - 1; i++) { count++; // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素 for (let j = 0; j < arr.length - 1 - i; j++) { // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换 // j=>左指针,j + 1=>右指针 if (arr[j] > arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } console.log(`执行了${count}趟循环`); return arr; } console.log("普通冒泡排序"); console.log(bubbleSort([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); console.log(bubbleSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 一重优化:增加交换过的状态值,当循环一趟,没有交换过,说明数组已经是有序了,下次不需要再次循环了 function bubbleSort1(arr) { if (arr.length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 冒泡排序排的趟数=数组的长度-1 // 第一层 for 循环代表一共排序多少趟 for (let i = 0; i < arr.length - 1; i++) { count++; let hasSort = true; // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素 for (let j = 0; j < arr.length - 1 - i; j++) { // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换 // j=>左指针,j + 1=>右指针 if (arr[j] > arr[j + 1]) { // 只要交换过,则不是有序 hasSort = false; let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (hasSort) { break; } } console.log(`执行了${count}趟循环`); return arr; } console.log("一重优化冒泡排序"); console.log(bubbleSort1([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); console.log(bubbleSort1([1, 2, 3, 4, 5, 6, 7, 8, 9, 9])); // 二重优化 function bubbleSort2(arr) { if (arr.length < 2) { return arr; } // 定义 count 代表执行了趟循环 let count = 0; // 记录最后一次交互元素时当前位置 let lastChangeIndex = 0; // 记录无序数列的右边界 let sortBorder = arr.length - 1; // 冒泡排序排的趟数=数组的长度-1 // 第一层 for 循环代表一共排序多少趟 for (let i = 0; i < arr.length - 1; i++) { count++; let hasSort = true; // 第二层 for 循环代表每趟需要比较多少次 每趟比较的次数会减i,因为每趟会将最后排好一个元素,排了多少趟,则代表排好了几个元素 for (let j = 0; j < sortBorder; j++) { // 在大于的时候才会交换,等于的时候不交换,所以冒泡排序属于稳定排序算法,不会对相等两个元素执行交换 // j=>左指针,j + 1=>右指针 if (arr[j] > arr[j + 1]) { // 只要交换过,则不是有序 hasSort = false; let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; lastChangeIndex = j; } sortBorder = lastChangeIndex; } if (hasSort) { break; } } console.log(`执行了${count}趟循环`); return arr; } console.log("二重优化冒泡排序"); console.log(bubbleSort2([6, 3, 7, 8, 2, 4, 0, 1, 6, 5])); console.log(bubbleSort2([1, 2, 3, 4, 5, 6, 7, 8, 9, 9]));
参考链接:https://blog.csdn.net/hcz666/article/details/117810787
标签:count,arr,console,log,冒泡排序,js,let,优化 From: https://www.cnblogs.com/beileixinqing/p/16647525.html