1. 递归方式
const ints = [1, -1, 23, -23, 434]
console.log('排序前数组', ints)
quickSort(ints, 0, ints.length - 1)
console.log('排序后数组', ints)
function swap(arr, aIndex, bIndex) {
const temp = arr[aIndex]
arr[aIndex] = arr[bIndex]
arr[bIndex] = temp
}
function quickSort(arr, left, right) {
if (left > right) {
return
}
// 获取一个参考值的索引(这里选择数组中间位置的元素作为参考值,也可以随机选择一个)
const mid = left + (right - left >>> 1)
// 将参考值交换到数组的最左侧
swap(arr, left, mid)
// 用于记录有多少个值比参考值小
let j = left
// 开始处理数组, 比参考值小的 将其移动到数组的左侧
for (let i = left + 1; i <= right; i++) {
// 将数组值依次与数组[最左侧]的参考值进行比较
if (arr[i] < arr[left]) {
// 比参考值小 个数加一
j++
// 将比参考值小的元素交换到数组的左侧来
swap(arr, i, j)
}
}
// 最后将数组最左侧的参考值交换到他最终排序好的位置去
swap(arr, left, j)
// 然后将参考值左侧的数组和参考值右侧的数组继续进行上述操作
quickSort(arr, left, j - 1)
quickSort(arr, j + 1, right)
}
2. 循环方式
const ints = [43, 0, -1, 56, 100, -245]
console.log('排序前数组', ints)
quickSort(ints)
console.log('排序后数组', ints)
function swap(arr, aIndex, bIndex) {
const temp = arr[aIndex]
arr[aIndex] = arr[bIndex]
arr[bIndex] = temp
}
function quickSort(arr) {
if (arr.length <= 1) {
return
}
const st = []
st.push(0)
st.push(arr.length - 1)
while (st.length > 0) {
// 因为栈是先进后出,先推入的是左侧的下标
// 所以推出的时候就先是右侧的下标
const right = st.pop()
const left = st.pop()
// 获取一个参考值的索引(这里选择数组中间位置的元素作为参考值,也可以随机选择一个)
const mid = left + (right - left >>> 1)
// 将参考值交换到数组的最左侧
swap(arr, left, mid)
// 用于记录有多少个值比参考值小
let j = left
// 开始处理数组, 比参考值小的 将其移动到数组的左侧
for (let i = left + 1; i <= right; i++) {
// 将数组值依次与数组[最左侧]的参考值进行比较
if (arr[i] < arr[left]) {
// 比参考值小 个数加一
j++
// 将比参考值小的元素交换到数组的左侧来
swap(arr, i, j)
}
}
// 最后将数组最左侧的参考值交换到他最终排序好的位置去
swap(arr, left, j)
// 然后将参考值左侧的数组和参考值右侧的数组继续进行上述操作
if (left < j - 1) {
st.push(left)
st.push(j - 1)
}
if (right > j + 1) {
st.push(j + 1)
st.push(right)
}
}
}
3. 运行结果
C:\Users\admin\Desktop>node quickStort.js
排序前数组 [ 43, 0, -1, 56, 100, -245 ]
排序后数组 [ -245, -1, 0, 43, 56, 100 ]
