21xrx.com
2024-12-27 20:15:35 Friday
登录
文章检索 我的文章 写文章
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)。因此,在实际应用中,我们需要将快速排序算法与其他排序算法结合起来使用,以获得更高效的排序效果。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复