21xrx.com
2025-06-14 11:57:16 Saturday
文章检索 我的文章 写文章
C++快速排序代码
2023-07-05 02:04:14 深夜i     9     0
C++ 快速排序 代码

快速排序是一个在计算机科学中非常常用的排序算法,效率很高。C++作为一门广泛应用的编程语言,也提供了快速排序的代码实现。下面是一个简单的C++快速排序代码示例。

快速排序是一种基于递归的分治算法,其基本思想是先挑选一个数作为基准,然后将列表中小于基准的数放在基准的左边,大于基准的数放在右边,递归实现。具体实现如下:

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int i = low, j = high, pivot = arr[low];
    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, low, i-1); // 递归左边部分
    quickSort(arr, i+1, high); // 递归右边部分
  }
}

在上述代码中,参数arr表示待排序的列表,而参数low和high则是列表的左右边界。函数在每次递归时将当前的数组按照基准值进行分割,左边的数都比基准值小,右边的数都比基准值大。递归继续分治,直到处理的数组只有一个或者是空的,排序结束。

总的来说,快速排序使用递归思想,不需要额外的空间,排序时间为O(nlogn),是一种非常高效的排序方法。C++的快速排序代码示例只是其中的一种实现方式,开发者可以结合实际场景和需求进行相应的优化和改进。

  
  

评论区