数据结构和算法之快速排序

快速排序是一种基于分治法的排序算法。它通过不断地将数组分成较小的子数组，并按照递归的方式对每个子数组进行排序，最终将整个数组排序。

快速排序算法的原理如下：

1. 从待排序数组中选择一个元素作为枢轴元素。
2. 将小于枢轴元素的所有元素移动到枢轴元素的左边，大于枢轴元素的所有元素移动到枢轴元素的右边。
3. 对左子数组和右子数组进行递归调用快速排序算法，直至子数组只剩一个元素或为空。
4. 递归结束后，整个数组就变得有序。

通过不断地选择枢轴元素并分割数组，快速排序算法可以将数组划分为越来越小的子数组，直到最后将整个数组排序完成。该算法的时间复杂度为O(nlogn)。

通常采用双指针法来找到基准元素的正确位置。首先，将左指针指向数组的起始位置，右指针指向数组的末尾位置。然后，左指针从左往右移动，直到找到比基准元素大的元素，并停止。右指针从右往左移动，直到找到比基准元素小的元素，并停止。接着，交换左右指针所指向的元素。重复上述步骤，直到左指针和右指针相遇。最后，将基准元素与左指针所指向的元素进行交换，使得基准元素位于正确的位置

具体实现如下：

// 定义一个交换函数，用于交换数组中的两个元素
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

// 定义一个分区函数，用于对数组进行分区操作
function partition(arr, left, right) {
  const pivot = arr[right - 1]; // 将分区点设置为最右边的元素
  let i = left,
    j = right - 1; // 初始化指针i和j
  while (i !== j) {
    // 当i和j指针不相遇时，进行循环
    arr[i] <= pivot ? i++ : swap(arr, i, --j); // 如果arr[i]小于等于分区点，则i指针向右移动；否则进行交换，并将j指针向左移动
  }
  swap(arr, j, right - 1); // 将分区点放置在正确的位置
  return j; // 返回分区点的索引
}

// 定义一个快速排序函数
function qsort(arr, left = 0, right = arr.length) {
  if (right - left <= 1) return; // 当要排序的元素个数小于等于1时，直接返回
  const p = partition(arr, left, right); // 进行分区操作，并获取分区点的索引p
  qsort(arr, left, p); // 对分区点左侧的子数组进行快速排序
  qsort(arr, p + 1, right); // 对分区点右侧的子数组进行快速排序
}

const arr = [5, 3, 8, 4, 2, 1, 10, 11, -4, 55];
qsort(arr); // [ -4, 1, 2, 3, 4, 5, 8, 10, 11, 55 ]
console.log(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

其他的一下实现方式：

/** 
1. 第一段程序使用的是递归的方式实现快速排序。它选择数组中间的元素作为基准元素，然后将数组分割为左右两个子数组，将比基准元素小的元素放在左子数组，将比基准元素大的元素放在右子数组，然后递归地对左右两个子数组进行快速排序，最后将左右两个子数组和基准元素拼接起来作为排序结果。

2. 第二段程序使用的是基于指针的方式实现快速排序。它通过定义一个分区函数来选择基准元素，并将数组分割为左右两个子数组，然后再递归地对左右两个子数组进行快速排序。分区函数中使用了双指针的方法，从左到右找到第一个大于基准元素的元素，从右到左找到第一个小于基准元素的元素，然后交换它们的位置。这样，最终基准元素的位置就确定下来了，并且左边的元素都小于等于基准元素，右边的元素都大于基准元素。

总的来说，这两段程序的思路是相同的，都是通过不断地将数组分割为更小的子数组并排序，最后再将子数组合并成排序后的结果。它们的实现细节略有不同，但最终的结果是相同的。
*/

//---------------------------------1------------------------------------
function quickSort(arr) {
  // 如果数组长度小于等于1，则直接返回
  if (arr.length <= 1) {
    return arr;
  }

  // 选择一个基准元素
  const pivot = arr[Math.floor(arr.length / 2)];

  // 定义左右两个子数组
  const left = [];
  const right = [];

  // 将元素分割到左右两个子数组
  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) {
      continue; // 跳过基准元素
    }
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 递归地对左右两个子数组进行快速排序
  return quickSort(left).concat([pivot], quickSort(right));
}

// 测试
const arr = [5, 3, 8, 4, 2, 1, 10];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出 [1, 2, 3, 4, 5, 8, 10]


//---------------------------------2------------------------------------
// 快速排序函数
function quickSort1(arr, left, right) {
  // 递归结束条件
  if (left >= right) {
    return;
  }

  // 设置左右指针及基准值
  let pivot = arr[left];
  let i = left;
  let j = right;

  // 开始一轮排序
  while (i < j) {
    // 从右侧找到比基准值小的元素
    while (i < j && arr[j] >= pivot) {
      j--;
    }

    // 将该元素放到左侧
    arr[i] = arr[j];

    // 从左侧找到比基准值大的元素
    while (i < j && arr[i] <= pivot) {
      i++;
    }

    // 将该元素放到右侧
    arr[j] = arr[i];
  }

  // 将基准值放回数组
  arr[i] = pivot;

  // 递归调用快速排序函数对左右两个子数组进行排序
  quickSort1(arr, left, i - 1);
  quickSort1(arr, i + 1, right);
}

// 测试
let arr2 = [5, 8, 2, 6, 3, 9, 1, 7, 4];
quickSort1(arr2, 0, arr2.length - 1);
console.log(arr2);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89