21xrx.com
2024-11-25 05:05:20 Monday
登录
文章检索 我的文章 写文章
C++快速排序实现代码
2023-07-03 15:29:47 深夜i     --     --
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[] = 8 ;


  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++程序中广泛使用。它适用于对大量数据进行排序，并且在排序时不需要额外的内存空间。

  
  

评论区

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