21xrx.com
2024-11-05 16:38:16 Tuesday
登录
文章检索 我的文章 写文章
C++实现快速排序算法代码
2023-07-13 01:41:56 深夜i     --     --
C++ 快速排序算法 代码

快速排序算法是一种高效的排序算法,它的时间复杂度可以达到 O(nlogn),在很多场景下都被广泛使用。C++ 是一种常用的编程语言,在这里我们将介绍如何使用 C++ 实现快速排序算法。

快速排序算法的基本思想是通过不断交换数组中的元素,将数组分成两个部分,一部分比另外一部分小,然后递归地对这两个部分分别进行排序。在具体实现中,我们选择一个基准值,将数组中小于它的元素放在它的左边,大于它的元素放在它的右边,然后以相同的方式递归地对左右两个部分进行排序。

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


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

  if (left < right) {

    int i = left, j = right, pivot = arr[left];

    while (i < j) {

      while (i < j && arr[j] > pivot) j--;

      if (i < j) arr[i++] = arr[j];

      while (i < j && arr[i] < pivot) i++;

      if (i < j) arr[j--] = arr[i];

    }

    arr[i] = pivot;

    quickSort(arr, left, i - 1);

    quickSort(arr, i + 1, right);

  }

}

这段代码定义了一个名为 quickSort 的函数,它接受一个整数数组和两个整数参数 left 和 right,表示要排序的数组的左右下标范围。在函数内部,我们首先判断左下标是否小于右下标,如果成立,则选择数组最左边的元素作为基准值 pivot,并用两个指针 i 和 j 分别从左右两边开始扫描数组。

当 i 和 j 相遇时,扫描结束,我们将 pivot 放到这个位置。接下来,递归地对左右两个部分进行排序,最终得到排序后的有序数组。

这段代码的时间复杂度为 O(nlogn),空间复杂度为 O(1),是一种高效的排序算法。它不需要额外的空间,只需要对原始数组进行修改,适用于处理大量数据的场景。

总之,C++ 实现快速排序算法是一种非常实用的技能,它可以大大提高数组排序的效率和速度。希望本文所介绍的算法能够对大家的日常开发工作有所帮助。

  
  

评论区

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