南邮数据结构上机实验四内排序算法的实现以及性能比较

.

i=n-1; while(i>0) {

last=0;

for(j=0;j

Swap(A[j],A[j+1]); last=j; } i=last; } }

template

void QuickSort(T A[],int n) //快速排序 {

QSort(A,0,n-1); }

template

void QSort(T A[],int left,int right) {

int i,j;

if(left

i=left; j=right+1; do {

do i++;while (A[i]A[left]); if(i

Swap(A[i],A[j]); }while(i

Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } }

template

void GQuickSort(T A[],int n) //改进的快速排序 {

GQSort(A,0,n-1); }

template

.

.

void GQSort(T A[],int left,int right) {

int i,j; if(right>=9) {

if(left

i=left; j=right+1; do {

do i++;while (A[i]A[left]); if(i

Swap(A[i],A[j]); }while(i

Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } else {

InsertSort(A,right-left+1); return ; } }

template

void Merge(T A[],int i1,int j1,int i2,int j2) //{

T* Temp=new T[j2-i1+1]; int i=i1,j=i2,k=0; while(i<=j1&&j<=j2) {

if(A[i]<=A[j])

Temp[k++]=A[i++]; else Temp[k++]=A[j++]; }

while (i<=j1)

Temp[k++]=A[i++]; while(j<=j2)

Temp[k++]=A[j++]; for(i=0;i

.

两路合并排序 .

delete[] Temp; }

template

void MergeSort(T A[],int n) {

int i1,j1,i2,j2; int size=1; while(size

i1=0;

while(i1+size

i2=i1+size; j1=i2-1;

if(i2+size-1>n-1) j2=n-1; else

j2=i2+size-1; Merge(A,i1,j1,i2,j2); i1=j2+1; }

size*=2; } }

int main() {

clock_t start,finish; srand(time(NULL)); int n=1000;

int *a=new int[n]; int *b=new int[n]; int *c=new int[n]; int *d=new int[n]; int *e=new int[n]; int *f=new int[n];

cout<<\待排序序列为:\ for(int i=0;i

a[i]=rand()?; cout<

.

.

e[i]=a[i]; f[i]=a[i]; }

cout<

start=clock(); SelectSort(a,n);

cout<<\经过简单选择排序后的序列为:\ for(i=0;i

cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); InsertSort(b,n);

cout<<\经过直接插入排序后的序列为:\ for(i=0;i

cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); BubbleSort(c,n);

cout<<\经过冒泡排序后的序列为:\ for(i=0;i

cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); QuickSort(d,n);

cout<<\经过快速排序后的序列为:\ for(i=0;i

cout<<\开始时间为:\\结束时间为:\时间为:\ start=clock(); MergeSort(e,n);

cout<<\经过两路合并排序后的序列为:\ for(i=0;i

.

持续持续持续持续.

cout<

cout<<\开始时间为:\\结束时间为:\持续时间为:\ start=clock(); GQuickSort(f,n);

cout<<\经过改进后的快速排序后的序列为:\ for(i=0;i

cout<<\开始时间为:\\结束时间为:\时间为:\ return 0; }

.

持续