21xrx.com
2025-03-27 05:45:00 Thursday
文章检索 我的文章 写文章
C++快速排序代码实现
2023-06-30 00:55:54 深夜i     --     --
C++ 快速排序 代码实现

C++快速排序是一种高效的排序算法,可用于对大量数据进行排序。快速排序算法基于分治的思想,不断将待排序序列划分成两个子序列,再分别对子序列进行排序。以下是C++快速排序的代码实现。

快速排序算法的关键在于如何选取一个合适的枢轴元素,并将待排序序列划分成两个子序列。以下是基本的快速排序算法:

void quicksort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2]; // 选取中间的数作为枢轴
  while (i <= j) {
    while (arr[i] < pivot) i++; // 找到左侧大于等于枢轴的元素
    while (arr[j] > pivot) j--; // 找到右侧小于等于枢轴的元素
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }
  if (left < j) quicksort(arr, left, j); // 对左半部分进行递归排序
  if (i < right) quicksort(arr, i, right); // 对右半部分进行递归排序
}

以上的代码实现了快速排序算法的核心部分,即选取枢轴元素并将待排序序列分成两个子序列。这段代码中,首先选取中间的数作为枢轴元素,然后使用两个指针i和j从序列的两端向中间扫描,找到左侧大于等于枢轴的元素和右侧小于等于枢轴的元素,将它们交换位置。当i和j相遇时,序列被划分成了两个子序列,左侧子序列中的元素都小于右侧子序列中的元素。之后,对两个子序列分别进行递归排序即可。

快速排序算法的时间复杂度为O(n log n),是一种高效的排序算法。它的缺点是对于已经排序好的序列并不是最优的,时间复杂度会达到O(n^2)。因此,在实际应用中,我们需要将快速排序算法与其他排序算法结合起来使用,以获得更高效的排序效果。

  
  

评论区