快速排序实现导致对象数组出现undefined元素及排序异常排查

问题现象 #

• 对对象数组users_total_likes按likes键实现快速排序时，数组中频繁出现undefined元素，运行时触发以下TypeError：

if(users[i][key] >= users[hi][key] && users[j][key] < users[hi][key]){
                                 ^

TypeError: Cannot read properties of undefined (reading 'likes')
    at partition (D:\Projects\Client Work\moodlearning-screen-test\item_e.js:71:38)
    at sort (D:\Projects\Client Work\moodlearning-screen-test\item_e.js:119:17)
    at sort (D:\Projects\Client Work\moodlearning-screen-test\item_e.js:125:9)
    at sort (D:\Projects\Client Work\moodlearning-screen-test\item_e.js:125:9)
    at Object.<anonymous> (D:\Projects\Client Work\moodlearning-screen-test\item_e.js:138:1)
    at Module._compile (node:internal/modules/cjs/loader:1103:14)
    at Object.Module._extensions..js (node:internal/modules/cjs/loader:1157:10)
    at Module.load (node:internal/modules/cjs/loader:981:32)
    at Function.Module._load (node:internal/modules/cjs/loader:822:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:77:12)

• 抛出错误前的数组状态（包含undefined和空项）：

[
  { likes: 2, post: 'post 2' },
  { likes: 9, post: 'post 4' },
  { likes: 10, post: 'post 1' },
  { likes: 14, post: 'post 7' },
  { likes: 50, post: 'post 5' },
  { likes: 40, post: 'post 6' },
  undefined,
  <1 empty item>,
  { likes: 30, post: 'post 3' }
]
current hi: 6

• 偶尔能执行但排序结果不符合预期：

[
  { likes: 10, post: 'post 1' },
  { likes: 2, post: 'post 2' },
  { likes: 30, post: 'post 3' },
  { likes: 9, post: 'post 4' },
  { likes: 50, post: 'post 5' },
  { likes: 40, post: 'post 6' },
  { likes: 14, post: 'post 7' }
]
[
  { likes: 2, post: 'post 2' },
  { likes: 9, post: 'post 4' },
  { likes: 10, post: 'post 1' },
  { likes: 14, post: 'post 7' },
  { likes: 30, post: 'post 3' },
  { likes: 50, post: 'post 5' },
  { likes: 40, post: 'post 6' }
]

原实现代码 #

let users_total_likes = [{
    likes: 10,
    post: 'post 1',
  },
  {
    likes: 2,
    post: 'post 2',
  },
  {
    likes: 30,
    post: 'post 3',
  },
  {
    likes: 9,
    post: 'post 4',
  },
  {
    likes: 50,
    post: 'post 5',
  },
  {
    likes: 40,
    post: 'post 6',
  },
  {
    likes: 14,
    post: 'post 7',
  },
];


const swap = (arr, i, j) => {
  /* 
  this is a utility funciton to swap elements in an array
  given the two elements indeces i and j

  args: 
      arr - array to swap the two elements in
      i - index of element 1
      j - index of element 2

  note: this modifies the array in place so no new copy array 
  of the array is returned
  */

  [arr[i], arr[j]] = [arr[j], arr[i]];
}

const partition = (users, lo, hi, key) => {
  // quick sort here
  let pivot = Math.floor((Math.random() * hi) + lo);
  swap(users, pivot, hi);

  let i = lo;

  // set j pionter to the last end of the scan
  let j = hi - 1;


  // console.log(`${users[i][key]} at index ${i}`);
  console.log(users);
  console.log(`current hi: ${hi} \n`);

  // when i pointer has greater index it has crossed the 
  // border of the j pointer
  while (i <= j) {
    // if i and j ptrs are < and >= to pivot then increm and decrem
    if (users[i][key] >= users[hi][key] && users[j][key] < users[hi][key]) {
      swap(users, i, j);
      ++i;
    }

    // check if either of the two, needs to be incremented or decremented or both
    else if (users[i][key] >= users[hi][key] && users[j][key] >= users[hi][key]) {
      --j;
    } else if (users[j][key] < users[hi][key] && users[i][key] < users[hi][key]) {
      ++i;
    } else {
      --j;
      ++i;
    }
  }

  // swap pivot element located in [hi] and swap with i
  swap(users, i, hi);

  // return new position of fixed pivot element
  return i;
}

const sort = (users, lo, hi, key) => {
  /* 
  args:
      implements the quicksort sorting algorithm

      users - an iterable of objects containing the id and posts of users
      key - the key in which the sorting function should base from, or when
      the comparison happens between two values this is what is used

      lo -
      
      hi -

      key - key of the iterable of objects to use in comparing two values with

      note: this function modifies the array in place and does not return
      a new copy fo the array
  */

  // if lo is greater than hi, it means array length reached 1
  if (lo < hi) {
    fixed = partition(users, lo, hi, key);

    // processes the sorted left side of the pivot
    sort(users, lo, fixed - 1, key);

    // processes the sorted right side of the pivot
    sort(users, fixed + 1, hi, key);
  }
}

console.log(users_total_likes);
sort(users_total_likes, 0, users_total_likes.length - 1, 'likes');
console.log(users_total_likes);

问题根源与修复方案 #

1. 随机 pivot 索引计算错误 #

原代码中Math.floor((Math.random() * hi) + lo)会生成超出[lo, hi]范围的索引，比如当lo=2、hi=6时，计算结果可能为7，超出数组最大索引（原数组长度为7，索引最大为6）。此时执行swap(users, 7, 6)会将数组外的undefined交换到数组内，导致后续访问时触发TypeError。

修复：使用正确的区间随机数公式，确保pivot索引始终在[lo, hi]范围内：

let pivot = lo + Math.floor(Math.random() * (hi - lo + 1));

2. 未声明变量导致全局污染 #

sort函数中fixed = partition(...)未使用let/const声明，会成为全局变量，递归调用时可能被覆盖，导致排序逻辑混乱。

修复：添加变量声明：

const fixed = partition(users, lo, hi, key);

3. 排序比较逻辑方向错误 #

原代码的比较条件逻辑混乱，导致元素分区错误，最终排序结果不符合预期。以升序排序为例，应将小于等于pivot的元素放到左侧，大于pivot的元素放到右侧。

修复：调整partition函数中的循环判断逻辑：

while (i <= j) {
  // i指针找大于pivot的元素
  while (i <= j && users[i][key] <= users[hi][key]) {
    i++;
  }
  // j指针找小于等于pivot的元素
  while (i <= j && users[j][key] > users[hi][key]) {
    j--;
  }
  // 交换i和j位置的元素
  if (i < j) {
    swap(users, i, j);
    i++;
    j--;
  }
}

修复后的完整代码 #

let users_total_likes = [{
    likes: 10,
    post: 'post 1',
  },
  {
    likes: 2,
    post: 'post 2',
  },
  {
    likes: 30,
    post: 'post 3',
  },
  {
    likes: 9,
    post: 'post 4',
  },
  {
    likes: 50,
    post: 'post 5',
  },
  {
    likes: 40,
    post: 'post 6',
  },
  {
    likes: 14,
    post: 'post 7',
  },
];


const swap = (arr, i, j) => {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

const partition = (users, lo, hi, key) => {
  // 生成[lo, hi]范围内的随机pivot索引
  let pivot = lo + Math.floor(Math.random() * (hi - lo + 1));
  swap(users, pivot, hi);

  let i = lo;
  let j = hi - 1;

  while (i <= j) {
    // 找到左侧第一个大于pivot的元素
    while (i <= j && users[i][key] <= users[hi][key]) {
      i++;
    }
    // 找到右侧第一个小于等于pivot的元素
    while (i <= j && users[j][key] > users[hi][key]) {
      j--;
    }
    // 交换元素并移动指针
    if (i < j) {
      swap(users, i, j);
      i++;
      j--;
    }
  }

  // 将pivot放到正确位置
  swap(users, i, hi);
  return i;
}

const sort = (users, lo, hi, key) => {
  if (lo < hi) {
    const fixed = partition(users, lo, hi, key);
    sort(users, lo, fixed - 1, key);
    sort(users, fixed + 1, hi, key);
  }
}

console.log('排序前：', users_total_likes);
sort(users_total_likes, 0, users_total_likes.length - 1, 'likes');
console.log('排序后：', users_total_likes);

内容的提问来源于stack exchange，提问作者Mig Rivera Cueva