21xrx.com
2024-11-22 07:26:25 Friday
登录
文章检索 我的文章 写文章
C++实现快速排序
2023-06-28 10:33:10 深夜i     --     --
C++ 快速排序 实现

快速排序是一种高效的排序算法,也是C++编程中常用的算法之一。该算法采用了分治的思想,具有时间复杂度为O(nlogn)的优秀性能。

首先,我们需要了解快速排序算法的大致思路。快速排序的基本思路是通过挑选数组元素作为基准数,将数组分成比基准数小的一部分和比基准数大的一部分,然后递归地对这两部分进行排序。其中,每次递归时,需要先确定一个基准数,然后采用两个指针来指向数组的头部和尾部,然后开始比较和交换,直到指针相遇,操作结束。接下来分别对基准数两侧的数组重复上述操作即可。

接下来,我们展示如何使用C++语言实现快速排序算法。下面是一段基于递归的C++代码,实现了快速排序算法。


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

  int i = left, j = right;

  int temp, pivot = arr[(left + right) / 2];

  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--;

    }

  }

  if (left < j)

    quickSort(arr, left, j);

  if (i < right)

    quickSort(arr, i, right);

}

在上述代码中,我们使用了两个指针i和j,它们分别指向数组的左边和右边。我们首先选取数组中间的元素作为基准数pivot,然后移动指针,从左到右找到第一个大于等于pivot的元素,从右到左找到第一个小于等于pivot的元素,然后交换这两个元素。直到左右指针相遇,此时左侧的元素由小到大排列,右侧的元素由大到小排列。然后将整个数组分成两部分,分别对左右两个部分采用快速排序算法进行排序,直到整个数组有序。

快速排序算法是一种值得我们学习和使用的排序算法,在C++编程中也是常用的算法之一。掌握了快速排序算法的原理和实现,不仅可以丰富我们的编程知识,还能提高我们的编程效率和算法思维。

  
  

评论区

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