数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究带有给定复杂度限制的 C++ 程序来实现快速排序
快速排序基于分治法。此算法的平均时间复杂度为 O(n*log(n))，但最坏情况复杂度为 O(n^2)。为了减少最坏情况发生的概率，此处快速排序使用随机数进行实现。
算法
partition(int a[], int l,int h)
Begin pivot = h Index = l start = l and end = h while start < end do while a[start] <= pivot AND start < end do start = start +1 done while a[end] > pivot do end = end – 1 done if start < end then swap a[start] with a[end] done a[low] = a[end] a[end] = pivot return end End
RandomPivotPartition(int a[], int l, int h)
Begin n = rand() pivot = l + n%(h-l+1); Swap a[h] with a[pivot] return Partition(a, l, h) End
QuickSort(int a[], int l, int h)
Begin int pindex; If (l<h) pindex = RandomPivotPartition(a, l, h) QuickSort(a, l, pindex-1) QuickSort(a, pindex+1, h) return 0 End
示例代码
#include<iostream>
#include<cstdlib>
using namespace std;
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int l, int h) {
int pivot, index, i;
index = l;
pivot = h;
for(i = l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int l, int h) {
int pvt, n, temp;
n = rand();
pvt = l + n%(h-l+1);
swap(&a[h], &a[pvt]);
return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = RandomPivotPartition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}输出
Enter the number of data element to be sorted: 4 Enter element 1: 3 Enter element 2: 4 Enter element 3: 7 Enter element 4: 6 Sorted Data ->3->4->6->7
更新时间：2019-07-30
3K+ 次浏览
广告