快速排序是基于分治策略的一个排序算法，实现快速排序的分治过程如下：
分解：数组A[p..r]被划分为两个（可能空）子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A(q),而且，小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算。
解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序
合并：因为两个子数组是就地排序的，将它们的合并不需要操作，整个数组
A[p..r]已排序。
实验代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <iostream> using namespace std; int num; void swap(int &a, int &b) { int temp = a; a = b; b = temp; }//交换元素位置 void PrintArray(int *arr) { for(int i=1; i<=num; ++i) cout << arr[i] << " "; cout << endl; } int Partition1(int *arr, int p, int r) { int x=arr[r]; int i=p-1; int j; for(j=p;j<=r-1;j++) { if(arr[j]<=x) {i=i+1; swap(arr[i],arr[j]); } } swap(arr[i+1],arr[r]); return i+1; }//对子数组A[p..r]进行就地重排 void QuickSort(int *arr, int p, int r) { if(p < r) { int q = Partition1(arr, p, r); QuickSort(arr, p, q-1); QuickSort(arr, q+1, r); } }//该过程实现快速排序 int main() { int arr[100]; cout << "请输入元素个数:\n"; cin >> num; cout << "请输入元素大小:\n"; for(int i=1; i<=num; ++i) cin >> arr[i]; QuickSort(arr, 1, num); cout << "最后结果:"; PrintArray(arr); return 0; } |
该算法在最坏情况下的时间复杂性为T(n)=O(n^2),平均情况下的时间复杂性是O(nlogn)
文章评论