C++快速排序程序？

快速排序是一种使用比较来对未排序列表（数组）进行排序的排序技术。快速排序也称为分区交换排序。

它不是稳定的排序，因为相等排序项的相对顺序不会保留。快速排序可以在数组上运行，只需要少量额外的内存来执行排序。它与选择排序非常相似，只是它并不总是选择最坏情况下的分区。因此，我们可以将其视为改进的选择排序。

快速排序是最有效的排序算法之一，它基于将数组分成更小的数组。名称来源于快速排序能够比任何常见的排序算法更快地对数据元素列表进行排序的事实。与归并排序一样，快速排序也属于分治法解决问题的范畴。

快速排序算法的工作方式如下：

  • 从类比的角度来看，考虑一下需要按姓名对印有学生姓名的纸张进行排序的情况。可以使用如下方法：

    • 选择一个分割值，例如L。分割值也称为**枢轴**。

    • 将纸张分成两堆：A-L和M-Z。这两堆不必大小相等。

    • 对A-L堆重复上述两个步骤，将其分成两半。同样对M-Z堆进行划分。重复此过程，直到堆足够小，易于排序。

    • 最终，可以将较小的堆叠在一起，形成一个完全排序的有序纸张集合。

  • 这里使用的方法是在每次分割时使用**递归**来得到单元素数组。

  • 在每次分割中，堆都被划分，然后对较小的堆使用相同的方法。

  • 由于这些特性，快速排序也称为**分区交换排序**。

Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7

解释

一个例子可能有助于理解这个概念。考虑以下数组：50, 23, 9, 18, 61, 32

**步骤1** - 从列表中决定任何值作为枢轴（通常是最后一个值）。假设有两个值“Low”和“High”，分别对应第一个索引和最后一个索引。

在我们的例子中，low为0，high为5。

low和high处的值分别为50和32，枢轴值为32。

因此，调用分区函数，重新排列数组，使枢轴（32）到达其实际位置。并且在枢轴的左侧，数组的所有元素都小于它，在右侧大于它。

在分区函数中，我们从第一个元素开始，并将其与枢轴进行比较。由于50大于32，我们不做任何更改，并继续下一个元素23。

再次与枢轴进行比较。由于23小于32，我们交换50和23。数组变为23, 50, 9, 18, 61, 32。

我们继续下一个元素9，它也小于枢轴（32），因此与50交换后，我们的数组变为：

23, 9, 50, 18, 61, 32.

类似地，对于下一个元素18（小于32），数组变为：

23, 9, 18, 50, 61, 32 现在61大于枢轴（32），因此没有变化。

最后，我们将枢轴与50交换，使其到达正确的位置。

因此，枢轴（32）到达其实际位置，其左侧的所有元素都小于它，右侧的所有元素都大于它。

**步骤2** - 因此，第一步之后的数组变为：

23, 9, 18, 32, 61, 50，取32作为枢轴。

**步骤3** - 现在列表被分成两部分：

1. 枢轴之前的子列表：23, 9, 18

2. 枢轴之后的子列表：61, 50

**步骤4** - 对这些子列表再次重复这些步骤。

因此，最终数组变为9, 18, 23, 32, 50, 61。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

#include <stdio.h>
void swap(int *a, int *b) {
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}
int Partition(int a[], int low, int high) {
   int pivot, index, i;
   index = low;
   pivot = high;
   for(i=low; i < high; i++) {
      if(a[i] < a[pivot]) {
         swap(&a[i], &a[index]);
         index++;
      }
   }
   swap(&a[pivot], &a[index]);
   return index;
}
int RandomPivotPartition(int a[], int low, int high) {
   int pvt, n, temp;
   n = rand();
   pvt = low + n%(high-low+1);
   swap(&a[high], &a[pvt]);
   return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high) {
   return 0;
}
int main() {
   int n, i;
   n=7;
   int arr[]={7,4,2,6,3,1,5};
   int high = n-1;
   int low = 0 ;
   int pindex;
   if(low < high) {
      pindex = RandomPivotPartition(arr, low, high);
      QuickSort(arr, low, pindex-1);
      QuickSort(arr, pindex+1, high);
   }
   for (i = 0; i < n; i++)
      printf("%d ", arr[i]);
   return 0;
}

更新于：2019年8月19日

1K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告