📄 main.cpp

📁 本文档讲解了几种排序方式的优缺点。包含直接插入、希尔、直接选择、冒泡、快速、堆、二路归并等排序方式。
💻 CPP
📖 第 1 页 / 共 2 页
字号:
12 下一页
#include "sqlist.h"
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iomanip.h>
#include <time.h>
#include "InsertSort.h"
#include "BInsertSort.h"
#include "BubbleSort.h"
#include "BubbleSort2.h"
#include "SelectSort.h"
#include "HeapSort.h"
#include "ShellSort.h"
#include "ShellSort2.h"
#include "QuickSort.h"
#include "QuickSort2.h"
#include "MergeSort.h"
#include "MergeSort2.h"

rectype *R=new rectype[5000000];
rectype *R1=new rectype[5000000];
long i;
long n;
long t1,t2;
int iflag;
char *cflag=new char;
int random()
{
  int A=48271;      //也可取A=16807
  int M=2147483647;
  int Q=M/A;
  int R=M%A;
  static int x=1;   //种子，这里固定地设为1
  int x1;
  x1=A*(x%Q)-R*(x/Q);
  if(x1>=0) x=x1;
  else      x=x1+M;
  return x;
}
void finsert()
{
	//(1)直接插入及改进
/*-------------------直接插入排序-------------------*/   
	cout<<setw(12)<<setfill(' ')<<"直接插入:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	cout<<setw(8)<<setfill(' ')<<"--";
	cout<<setw(8)<<setfill(' ')<<"--";

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	InsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;


/*-----------------------直接插入排序改1(折半插入)-------------*/
    cout<<setw(12)<<setfill(' ')<<"直接改进1:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

    cout<<setw(8)<<setfill(' ')<<"--";
	cout<<setw(8)<<setfill(' ')<<"--";

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	BInsertSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;
}
void fshell()
{
	//(2)shell排序及改进
	/*------------------------Shell排序-------------------*/
    cout<<setw(12)<<setfill(' ')<<"希尔排序:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	ShellSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

/*----------------------Shell排序2----------------------*/
    cout<<setw(12)<<setfill(' ')<<"希尔改进1:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	ShellSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;
}
void fselect()
{
	//(3)直接选择排序
	/*------------------------直接选择排序--------------------*/
  cout<<setw(12)<<setfill(' ')<<"直接选择:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	cout<<setw(8)<<setfill(' ')<<"--";
	cout<<setw(8)<<setfill(' ')<<"--";

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	SelectSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;
}
void fbubble()
{
	//(4)冒泡排序及改进
	/*-------------------冒泡排序-----------------------*/
	cout<<setw(12)<<setfill(' ')<<"冒泡:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	cout<<setw(8)<<setfill(' ')<<"--";
	cout<<setw(8)<<setfill(' ')<<"--";

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	BubbleSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

/*-------------------------冒泡排序改1-双向冒泡---------------------*/
    cout<<setw(12)<<setfill(' ')<<"冒泡双向:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	cout<<setw(8)<<setfill(' ')<<"--";
	cout<<setw(8)<<setfill(' ')<<"--";

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	BubbleSort2(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;
}


void fquick()
{
	//(5)快速排序及改进
	/*------------------------快速排序-------------------*/
    cout<<setw(12)<<setfill(' ')<<"快速排序:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
12 下一页
💿 文件大小 83 K
👤 上传用户 wylyyzjz
📂 所属分类书籍源码
🏷️ 相关标签

#排序 #方式 #文档
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -