21xrx.com
2024-05-20 11:28:58 Monday
登录
文章检索 我的文章 写文章
C++快速排序代码
2023-07-05 02:04:14 深夜i     --     --
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++的快速排序代码示例只是其中的一种实现方式,开发者可以结合实际场景和需求进行相应的优化和改进。

  
  

评论区

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