C++实现快速排序函数 |21xrx.com

C++实现快速排序函数

2023-07-09 13:04:42 深夜i -- --

C++ 快速排序函数实现排序算法

快速排序是一种高效的排序算法，其时间复杂度为O(NlogN)，是经常被使用的排序算法之一。C++是一种非常流行的编程语言，有着广泛的应用性。在C++中，实现一个快速排序函数可以使程序更加高效，下面我们就来看看如何用C++实现快速排序函数。

快速排序的核心思想是分治法，通过选取一个主元，将数组分割成两部分，使得一部分的值全部小于主元，另一部分的值全部大于主元，然后再对这两部分递归进行快速排序。

接下来，我们可以使用C++来实现快速排序函数，具体步骤如下：

1. 首先定义一个函数，这个函数需要接收一个数组和起始位置以及结束位置的下标值。


void quickSort(int arr[], int start, int end)

2. 选择一个主元，我们可以选择数组的第一个元素或者随机选择一个元素作为主元。


int pivot = arr[start];

3. 定义两个指针i和j，分别指向数组的起始和结束位置。


int i = start, j = end;

4. 在循环中，让指针i从左向右扫描数组，直到遇到一个大于等于主元的元素。


while (arr[i] < pivot) {
  i++;
}

5. 让指针j从右向左扫描数组，直到遇到一个小于等于主元的元素。


while (arr[j] > pivot)
  j--;

6. 如果i<=j，则交换arr[i]和arr[j]的值，并且i向右移动一位，j向左移动一位。


if (i <= j) {
  swap(arr[i], arr[j]);
  i++;
  j--;
}

7. 继续循环执行步骤4-6，直到i>j。


if (start < j) {
  quickSort(arr, start, j);
}
if (end > i) {
  quickSort(arr, i, end);
}

8. 最后返回排序后的数组。


return arr;

通过以上步骤，我们就可以实现一个快速排序函数。我们可以在main函数中调用这个函数，例如：


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

通过输出结果可以看到，我们成功地实现了快速排序函数，对数组进行了排序。C++提供了很多快捷的函数，例如指针和引用等，这些都能够使我们更加方便地实现快速排序函数，提高程序的效率。

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

下一篇: C++模型部署：一步步教你如何实现深度学习模型的部署

评论区

()

相似文章