Posted on 2008-11-05 22:09
kainster 阅读(138)
评论(0) 编辑 收藏
最近看算法导论，把几种排序重新写一下吧
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <windows.h>
using namespace std;
#define MAX 999999;
void Merge(int *A,int p,int q,int r)
{
int n1 = q-p+1;
int n2 = r-q;
int *L = new int[n1+1];
int *R = new int[n2+1];
int i;
int j;
for(i=0;i<n1;i++)
L[i] = A[ p+i ];
for(i=0;i<n2;i++)
R[i] = A[ q+1+i ];
L[n1] = MAX;
R[n2] = MAX;
i=0;
j=0;
for(int k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}
void MergeSort( int *A, int p, int r )
{
int q;
if(p<r)
{
q = (p+r) / 2;
MergeSort(A,p,q);
MergeSort(A,q+1,r);
Merge(A,p,q,r);
}
}
void PrintArray(int *A,int length)
{
for(int i=0;i<length;i++)
cout << *(A+i) << ",";
cout << endl;
}
void InsertionSort(int *A,int length)
{
for(int j=1;j<length;j++)
{
int key = A[j];
int i = j-1;
while(i>=0 && A[i] > key)
{
A[i+1] = A[i];
i--;
}
A[i+1] = key;
}
}
void BubbleSort(int *A,int length)
{
int temp;
bool flag = false;
for(int i=0;i<length;i++)
{
flag = false;
for(int j=length-1;j>i;j--)
if(A[j]<A[j-1])
{
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
flag = true;
}
if(flag == false)
break;
}
}
void RandArray(int *A,int length)
{
for(int i=0;i<length;i++)
A[i] = rand()%100;
}
int main()
{
int i;
int start;
int length = 10000;
int *intArray = new int[length];
RandArray(intArray,length);
start = GetTickCount();
BubbleSort(intArray,length);
cout << "BubbleSort costs" << GetTickCount()-start << endl;
RandArray(intArray,length);
start = GetTickCount();
InsertionSort(intArray,length);
cout << "InsertionSort costs" << GetTickCount()-start << endl;
RandArray(intArray,length);
start = GetTickCount();
MergeSort(intArray,0,length-1);
cout << "MergeSort costs" << GetTickCount()-start << endl;
cin>>i;
return 0;
}