21xrx.com
2024-11-22 07:12:39 Friday
登录
文章检索 我的文章 写文章
王道书中C++实现快排算法
2023-07-05 03:17:30 深夜i     --     --
王道书 C++ 快排算法 实现

快速排序（Quick Sort）是一种基于分治和递归思想的高效排序算法。它在排序过程中不需要额外的空间，只需要对原始数据进行交换、移动操作就可以完成排序。快速排序由于其高效性和广泛应用性，成为经典的排序算法之一。在 C++ 中实现快速排序算法，可以掌握 C++ 函数调用，递归调用以及数组元素访问的技巧。

快排的基本思想是分治思想，将一个数组按照一个基准元素划分为两个子序列，递归地对两个子序列执行同样的操作。排序过程如下：

1. 选择基准元素；

2. 将小于等于基准元素的元素移到基准元素的左侧，大于基准元素的元素移到基准元素的右侧；

3. 递归对基准元素左侧和右侧的子序列进行相同的操作，直到只剩下一个元素或没有元素。

下面是 C++ 实现快速排序的程序：



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


  int i = left, j = right;


  int tmp;


  int pivot = arr[(left + right) / 2]; // 选择中间的元素作为基准


  // 划分序列


  while (i <= j) {


    while (arr[i] < pivot)


      i++;


    while (arr[j] > pivot)


      j--;


    if (i <= j) {


      tmp = arr[i];


      arr[i] = arr[j];


      arr[j] = tmp;


      i++;


      j--;


    }


  }


  // 递归处理


  if (left < j)


    quickSort(arr, left, j);


  if (i < right)


    quickSort(arr, i, right);


}

这个程序中，`left` 和 `right` 分别表示数组的左右边界。在程序开头选择数组的中间元素作为基准元素 `pivot`，然后从左侧开始找比 `pivot` 大的元素，从右侧开始找比 `pivot` 小的元素，交换它们的位置，直到 `left` 和 `right` 指针相遇。如果此时，左侧元素全部小于等于 `pivot`，右侧元素全部大于等于 `pivot`，那么 `pivot` 的位置就是分界点。这时，左侧和右侧的子序列都不需要处理包含 `pivot` 的位置，因为 `pivot` 已经是正确的位置了。接下来，分别递归处理 `pivot` 的左侧和右侧子序列，直到左侧子序列和右侧子序列都只包含一个元素或是空序列，排序完成。

使用上述程序，可以对任意长度的整数序列进行快速排序。在实际编程过程中，要注意数组越界问题、函数递归调用次数等问题，以确保程序的正确执行。通过练习和实践不断深入了解和掌握算法，我们可以成为一名优秀的程序员，为工业界和科学界做出贡献。

  
  

评论区

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