C++快速排序：两种实现方式 |21xrx.com

C++快速排序：两种实现方式

2023-07-12 02:09:25 深夜i -- --

C++ 快速排序实现方式

快速排序是一种排序算法，它可以快速地将一个无序数组排序为有序的数组。C++是一种广泛使用的编程语言，它提供了两种实现快速排序的方式。下面将对这两种方式进行介绍。

第一种实现方式是使用递归函数。在递归方式中，快速排序通过找到一个“基准”元素，并将数组分成比基准元素小和比基准元素大的两个子数组来工作。然后，它递归地对这两个子数组进行排序，直到所有子数组都被排序为止。下面是递归方式实现快速排序的代码示例：


void quickSortRecursive(int arr[], int left, int right) {
  if (left < right) {
    int pivot = partition(arr, left, right);
    quickSortRecursive(arr, left, pivot - 1);
    quickSortRecursive(arr, pivot + 1, right);
  }
}
int partition(int arr[], int left, int right) {
  int pivot = arr[right];
  int i = left - 1;
  for (int j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[right]);
  return i + 1;
}

第二种实现方式是使用迭代方式。在迭代方式中，快速排序使用一个辅助栈来模拟递归函数的调用过程。在每次迭代中，快速排序将栈顶元素出栈，并将数组划分为比基准元素小和比基准元素大的两个子数组。然后，它将这两个子数组的索引压入辅助栈中，以便在下一次迭代中排序。下面是迭代方式的代码示例：


void quickSortIterative(int arr[], int left, int right) {
  stack<int> st;
  st.push(left);
  st.push(right);
  while (!st.empty()) {
    int rightIndex = st.top();
    st.pop();
    int leftIndex = st.top();
    st.pop();
    if (leftIndex < rightIndex) {
      int pivot = partition(arr, leftIndex, rightIndex);
      st.push(leftIndex);
      st.push(pivot - 1);
      st.push(pivot + 1);
      st.push(rightIndex);
    }
  }
}

无论是递归方式还是迭代方式，都可以很快地对一个无序数组进行排序。但是，如果数组的大小很小，则使用快速排序可能会产生不必要的开销。因此，在实际应用中，可以根据数组的大小来选择使用哪种排序方式。

上一篇: idea打包java可执行jar包

下一篇: C++中tuple的详细解析

评论区

()

相似文章