//============================================================================
// Name : shuanfa.cpp
// Author : yuanxiang
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#include <windows.h>
#include <sys/timeb.h>
#include <time.h>
using namespace std;
struct timeval
{
long tv_sec;
long tv_usec;
};
int gettimeofday(struct timeval* tv)
{
union{
long long ns100;
FILETIME ft;
}now;
GetSystemTimeAsFileTime (&now.ft);
tv->tv_usec = (long) ((now.ns100 ) % 1000000LL);
tv->tv_sec = (long) ((now.ns100 - 116444736000000000LL) / 10000000LL);
return (0);
}
//获取1970年至今UTC的微妙数
time_t GetUtcCaressing()
{
timeval tv;
gettimeofday(&tv);
return ((time_t)tv.tv_sec*(time_t)1000000+tv.tv_usec);
}
void print(int src[],int length){
for(int i=0;i<length;i++){
cout<<src[i]<<" ";
}
cout<<endl;
}
void swap(int& a,int& b){
int temp = a;
a = b;
b=temp;
}
//冒泡排序
void maopoSort(int src[],int length){
cout<<"冒泡排序:";
print(src,length);
for(int i=0;i<length;i++){
for(int j=0;j<length-1-i;j++){
if(src[j]>src[j+1]){
int temp = src[j];
src[j] = src[j+1];
src[j+1]=temp;
}
}
}
print(src,length);
}
//简单选择排序
void xuanzheSort(int src[],int length){
cout<<"简单排序:";
print(src,length);
for(int i=0;i<length;i++){
int k = i;
for(int j=i+1;j<length;j++){
if(src[j]<src[k]){
k = j;
}
}
if(k!=i){
swap(src[k],src[i]);
}
}
print(src,length);
}
//插入排序
void charuSort(int src[],int length){
cout<<"插入排序排序:";
print(src,length);
for(int i=0;i<length;i++){
int j=0;
int k=src[i];
for(j=i-1;j>=0&&src[j]>k;j--){
src[j+1]=src[j];
}
if(j+1!=i)
src[j+1] = k ;
}
print(src,length);
}
//快速排序
void kuaisuSort(int src[],int begin,int end){
if(begin>=end)
return;
int mid =begin;
int i=begin+1;
int j=end;
while(i<=j){
while(src[i]<=src[mid]&&i<end) i++;
while(src[j]>=src[mid]&&j>begin) j--;
if(i<j){
swap(src[i],src[j]);
}else{
break;
}
i++;
j--;
}
swap(src[mid],src[j]);
kuaisuSort(src,begin,j-1);
kuaisuSort(src,j+1,end);
}
void kuaisuSort(int src[],int length){
cout<<"快速排序:";
print(src,length);
kuaisuSort(src,0,length-1);
print(src,length);
}
//堆排序
void maxHeap(int src[],int k,int length){//从0开始
int m = src[k];
int i = k;
while(i<length){
int left=2*(i+1)-1;
int right=2*(i+1);
int lagest = 0;
if(right<length)
lagest = src[right]>src[left]?right:left;
else if(left<length)
lagest = left;
else
break;
if(src[lagest]>m){
src[i]=src[lagest];
i = lagest;
}else{
break;
}
}
if(i!=k)
src[i] = m;
}
void CreateDui(int src[],int length){
for(int i=length/2-1;i>=0;i--){
maxHeap(src,i,length);
//print(src,length);
}
}
void duiSort(int src[],int length){
cout<<"堆排序:";
print(src,length);
CreateDui(src,length);
for(int i=length-1;i>=1;i--){
swap(src[0],src[i]);
maxHeap(src,0,i);
}
print(src,length);
}
//希尔排序
void shellSortDela(int src[],int dela,int begin,int length){
for(int i=begin;i<length;i+=dela){
int j=i-dela;
int m = src[i];
for(j=i-dela;src[j]>m&&j>=begin;){
src[j+dela] = src[j];
j=j-dela;
}
src[j+dela] = m;
}
// print(src,length);
}
void shellSort(int src[],int length){
cout<<"shell排序:";
print(src,length);
for(int dela=length/2;dela>0;dela/=2){
for(int i=0;i<dela;i++)
shellSortDela(src,dela,i,length);
}
print(src,length);
}
//归并排序
void merge(int a[],int low,int mid,int high){
int* b=new int[high-low+1];
int i=low;
int j=mid+1;
int k=0;
while(i<=mid&&j<=high){
b[k++]=a[i]<=a[j]?a[i++]:a[j++];
}
while(i<=mid)
b[k++]=a[i++];
while(j<=high)
b[k++]=a[j++];
// memcpy(&a[low],b,(high-low+1)*sizeof(int));
for(i=low;i<=high;i++){
a[i] = b[i-low];
}
delete b;
}
void mergeSort(int a[],int begin,int end){
if(begin>=end)
return;
int mid=(begin+end)/2;
mergeSort(a,begin,mid);
mergeSort(a,mid+1,end);
merge(a,begin,mid,end);
}
void mergeSort(int a[],int length){
cout<<"归并排序:";
print(a,length);
mergeSort(a,0,length-1);
print(a,length);
}
//基数排序
void jisuSort(int a[],int length){
cout<<"基数排序:";
print(a,length);
int* b = new int[10*length];
int k[10]={0};
bool flag=true;
int m=1;
while(flag){
flag = false;
memset(k,0,10*sizeof(int));
for(int i=0;i<length;i++){
int t = abs(a[i])/m;
if(t/10>0)
flag=true;
*(b+length*(t%10)+*(k+t%10)) = a[i];
*(k+t%10) = *(k+t%10)+1;
}
m *= 10;
int n=0;
for(int i=0;i<10;i++){
if(k[i]!=0){
for(int j=0;j<k[i];j++){
a[n++]=*(b+length*i+j);
}
}
}
}
print(a,length);
memset(k,0,10*sizeof(int));
for(int i=0;i<length;i++){
if(a[i]<0){
*(b+k[0]) = a[i];
k[0]++;
}else{
*(b+length+k[1]) = a[i];
k[1]++;
}
}
int n=0;
for(int j=k[0]-1;j>=0;j--){
a[n++]=*(b+j);
}
for(int j=0;j<k[1];j++){
a[n++]=*(b+length+j);
}
delete b;
print(a,length);
}
//计算排序时间
void computeTime(int a[],int length,void(*func)(int a[],int length)){
int* b=new int[length];
for(int i=0;i<length;i++){
b[i]=a[i];
}
time_t t1= GetUtcCaressing();
func(b,length);
time_t t2= GetUtcCaressing();
cout<<"算法消耗时间（100NS）："<<t2<<"-"<<t1<<"="<<t2-t1<<endl;
delete b;
}
int main() {
int a[]={3,2,-1,6,4,12,0,7,-4,29,-20};
int length = sizeof(a)/sizeof(int);
computeTime(a,length,maopoSort);
computeTime(a,length,xuanzheSort);
computeTime(a,length,charuSort);
computeTime(a,length,kuaisuSort);
computeTime(a,length,duiSort);
computeTime(a,length,shellSort);
computeTime(a,length,mergeSort);
computeTime(a,length,jisuSort);
return 0;
}
运行结果：
冒泡排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476843755--1476843755=0
简单排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476843755--1476843755=0
插入排序排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476843755--1476843755=0
快速排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476843755--1476843755=0
堆排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476843755--1476843755=0
shell排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476833754--1476843755=10001
归并排序:3 2 -1 6 4 12 0 7 -4 29 -20
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476833754--1476833754=0
基数排序:3 2 -1 6 4 12 0 7 -4 29 -20
0 -1 2 3 4 -4 6 7 12 -20 29
-20 -4 -1 0 2 3 4 6 7 12 29
算法消耗时间（100NS）：-1476833754--1476833754=0