21xrx.com
2024-12-27 19:45:55 Friday
登录
文章检索 我的文章 写文章
C++ 快速排序的代码实现
2023-07-03 06:21:56 深夜i     --     --
C++ 快速排序 代码实现

快速排序是一种常见的排序算法,在C++中实现快速排序非常简单。本文将介绍如何使用C++编写快速排序的代码。

快速排序的原理是通过分治的思想,将一个序列分成左右两个子序列,然后递归地对子序列进行排序。具体实现方法是先选取一个基准值(pivot),然后将数组中小于等于基准值的元素移到左边,大于基准值的元素移到右边,最后再分别对左右两个子序列进行递归排序。

下面是C++中实现快速排序的代码:


void quickSort(int arr[], int left, int right) {

  int i = left, j = right;

  int temp;

  int pivot = arr[(left + right) / 2];

  while (i <= j) {

    while (arr[i] < pivot)

      i++;

    while (arr[j] > pivot)

      j--;

    if (i <= j) {

      temp = arr[i];

      arr[i] = arr[j];

      arr[j] = temp;

      i++;

      j--;

    }

  }

  if (left < j)

    quickSort(arr, left, j);

  if (i < right)

    quickSort(arr, i, right);

}

在这个函数中,参数 `arr` 是待排序的数组,`left` 和 `right` 是数组的左右边界。

首先,选取基准值(pivot),然后定义两个下标 `i` 和 `j`,分别指向数组的左右两端。然后,进行双向扫描,找出左边第一个大于基准值的元素和右边第一个小于等于基准值的元素,交换这两个元素的位置,直到两个下标指向同一个位置。

接着,使用递归的方式对左右两个子序列进行排序,直到最终整个序列有序。

在实际应用中,快速排序是一种高效的排序算法,时间复杂度为O(nlogn),但最坏情况下时间复杂度会退化为O(n^2)。因此,在实现快速排序时需要注意选取合适的基准值,以及对递归深度进行限制。

总之,本文介绍了使用C++实现快速排序的方法和代码,希望能对读者有所帮助。

  
  

评论区

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