C++快速排序实现代码 |21xrx.com

C++快速排序实现代码

2023-06-26 12:34:48 深夜i 10 0

C++ 快速排序实现代码

快速排序是一种高效的排序算法，也是C++程序中常用的排序算法之一。以下是使用C++语言实现快速排序的代码：

void quickSort(int* arr, int left, int right){
  int i = left, j = right;
  int temp;
  int pivot = arr[(left + right) / 2];
  // Partition
  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--;
    }
  };
  // Recursion
  if (left < j)
    quickSort(arr, left, j);
  if (i < right)
    quickSort(arr, i, right);
}

这个实现函数使用递归来排序一个整型数组。它接受三个参数：数组指针、左边界和右边界。

首先，它定义了两个指针，分别指向数组的左右两边。然后，它选择数组中间位置的数作为枢轴（pivot），并将其与左右两端的数依次比较，将比pivot小的数放到它的左边，大的数放到它的右边，最后将pivot放到中间，这样就完成了一次分区（Partition）操作。

接着，递归调用函数依次对左右两部分进行分区操作，直到左右部分的长度都不大于1，就达到了递归的终止条件。

在编写C++程序时，可以在main函数中调用这个实现函数，例如：

int main(){
  int arr[] = 15;
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
  return 0;
}

这个程序以一个无序数组作为输入，使用上面的实现函数对其进行排序，然后输出排好序的数组。

简而言之，C++的快速排序实现代码是一个简单却高效的排序算法，在C++程序中广泛使用。它适用于对大量数据进行排序，并且在排序时不需要额外的内存空间。

上一篇: idea打包java可执行jar包

下一篇: C++组合的实例

评论区

相似文章