CavsZhouyou/Front-End-Interview-Notebook

大大,算法冒泡排序那里是不是有点问题?

CaZn opened this issue · 1 comments

CaZn commented
// 内部循环优化的那部分,是通过lastIndex来记录最后一次交换的位置是吧,但是下面代码中,lastIndex一直为length-1,没有任何赋值
function bubbleSort(array) { 
  let length = array.length,
     lastIndex = length - 1;
  // 如果不是数组或者数组长度小于等于1,直接返回,不需要排序 
  if (!Array.isArray(array) || length <= 1) return;
  // 第一层循环判断元素浮到顶端的位置
  for (let i = length; i >= 2; i--) {
    // 判断是否已经排序好的标志
    let flag = true,
      k = lastIndex;
    // 第二层对相邻元素两两比较,将最小或最大的元素浮动到顶端
    for (let j = 0; j < k; j++) {
      if (array[j] > array[j + 1]) {
        // [array[j], array[j + 1]] = [array[j + 1], array[j]];
        swap(array, j, j + 1);
        flag = false;
        k = lastIndex;  
      }
    }
    // 如果一次交换都没有则跳出循环
    if(flag) break;
  }
  return array;
}

// 下面是我个人的做法
function bubbleSort(arr) {
    if (!Array.isArray(arr) || arr.length <= 1) return;
    let lastIndex = arr.length - 1;
    while (lastIndex > 0) { // 当最后一个交换的元素为第一个时,说明后面全部排序完毕
        let flag = true, k = lastIndex;
        for (let j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = false;
              	lastIndex = j; // 设置最后一次交换元素的位置
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
      	if (flag) break;
    }
}

感谢指正,文档已经修正了