快排 (Quick Sort) 简记¶

\(\texttt{Code:}\)¶

inline void quick_sort(int arr[], const int len)
{
  if (len <= 1) return;
  const int pivot = arr[rand() % len];
  int i = 0, j = 0, k = len;
  while (i < k)
  {
    if (arr[i] < pivot)
      std::swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      std::swap(arr[i], arr[--k]);
    else
      i++;
  }
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

原理¶

首先读入数组 \(arr_i\) 和数组长度 \(len\)；

如果 \(len \leq 1\) 的话，说明这个数组不存在，直接 \(return\)；

然后通过 STL 中的 \(rand()\) 函数随便从数组中选一个基准值，接下来就是不断比较剩余数字与这个基准值的大小；

int i = 0, j = 0, k = len;

\(i\) 指针：遍历数组中的每个数
\(j\) 指针：标记小于基准值元素的区域的最右边界
\(k\) 指针：标记大于基准值元素的区域的最左边界

然后循环比较数组中每个数与基准值的大小，这里条件能取 \(i \lt f\) 的原因是，我们在前面的遍历中已经把大于基准值的元素都抛到 \(k\) 后面了，也就是说当 \(i\) 遍历到 \(k\) 时，三个区域已经被划分出来了，也就没有必要继续遍历后面的部分了。

if (arr[i] < pivot) std::swap(arr[i++], arr[j++]);

当 \(i\) 所指向的数小于基准值时，交换 \(i\) 所指向元素与 \(j\) 所指向元素并将他俩都右移一位，因为有一个新数被纳入了左区域。

else if (pivot < arr[i]) std::swap(arr[i], arr[--k]);

当 \(i\) 所指向的数大于基准值时，交换 \(i\) 所指向元素与 \(k\) 所指向元素并将 \(k\) 左移一位，因为有一个新数被纳入了右区域。

else i++;

这一步说明 \(i\) 所指元素等于基准值，直接向右移一位即可。

然后就是继续递归遍历左区域与右区域，直到第一个条件结束。

快排 (Quick Sort) 简记¶

\(\texttt{Code:}\)¶

原理¶

评论