内排序

//sort.h

using namespace std;

 

template

void Swap(T *a,T *b)

{

   T temp=*a;

   *a=*b;*b=temp;

}

 

template

void PrintArray(T array[],int n)

{

   for (int i=0;i

   std::cout<

}

 

template

void SelectSort(T A[],int n)    //简单选择排序,n为元素个数

{

   int min;

   for(int i=0;i

       min=i;

       for(int j=i+1;j

           if(A[min]>A[j]) min=j;

       }

       Swap(&A[min],&A[i]);PrintArray(A,n);

   }

}

 

template

void InsertSort(T A[],int n)    //直接插入排序

{

   for(int i=1;i

       T temp=A[i];

       int j=i;

       while(j>0 && temp

           A[j]=A[j-1];j–;

       }

       A[j]=temp;PrintArray(A,n);

   }

}

 

template

void BubbleSort(T A[],int n)    //冒泡排序

{

   int Isover=0;

   for(int i=n-1;i>0;i–){

       Isover=0;

       for(int j=0;j

           if(A[j]>A[j+1]) {Swap(&A[j],&A[j+1]);Isover=1;}

       }

       PrintArray(A,n);

       if(Isover==0) break;    //若本趟没有交换,则代表所有相邻的都是大小有序的,就排好了,不用再扫描了

   }

}

 

template

void QSort(T A[],int left,int right,int n)    //快速排序

{

   int i,j;

   if(left

       i=left,j=right+1;

       Swap(&A[left],&A[(left+right)/2]);  //把中间元素与第一个元素交换,即可实现以中间元素为关键字或分割元素,排列

       do{

           do i++;while(A[i]

           do j–;while(A[j]>A[left]);

           if(i

       }while(i

       Swap(&A[left],&A[j]);PrintArray(A,n);//std::cout<<"   "<

       //std::cout<

       QSort(A,left,j-1,n);

       //std::cout<

       QSort(A,j+1,right,n);

   }

}

template

void QuickSort(T A[],int n)

{

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

}

 

template

void Merge(T A[],int i1,int j1,int i2,int j2)   //两路合并排序,归并排序

{

   T temp[j2-i1];

   int t=0,i=i1;

   while(i<=j1 && i2<=j2){

       if(A[i]

       else {temp[t]=A[i2];i2++;t++;}//std::cout<

   }

   while(i<=j1){temp[t]=A[i];i++;t++;}//std::cout<

   while(i2<=j2){temp[t]=A[i2];i2++;t++;}//std::cout<

   for(int x=i1;x

   //delete[] temp;

}

template

void MergeSort(T A[],int n)

{

   int size=1,i=0;

   while(size

       i=0;

       while(i+size

           if(i+size+size-1

           else Merge(A,i,i+size-1,i+size,n-1);

           i=i+size+size;

       }

       size=size*2;PrintArray(A,n);

   }

}

 

template

void AdjustDown(T A[],int i,int n)  //堆排序的指定某点向下调整

{

   int lchild=2*i+1,max=0;    //i左孩子的位置

   if(lchild

       if(lchild+1

           if(A[lchild]>A[lchild+1]) max=lchild;

           else max=lchild+1;

       else max=lchild;

       if(A[i]

   }

}

template

void HeapSort(T A[],int n)  //堆排序

{

   int i;

   for(i=(n-2)/2;i>-1;i–) AdjustDown(A,i,n);  //从最后一个非叶子结点开始依次向前扫描,依次做向下调整,即可完成构建最大最小堆

   for(i=n-1;i>0;i–){

       Swap(&A[0],&A[i]);  //交换堆顶和堆底元素,即完成一个最大数的输出

       PrintArray(A,n);

       AdjustDown(A,0,i);  //此时刚交换完,只有A[0]是无序的,其他都是有序的,所以只需对A[0]进行向下调整,既可重获最大堆。此时,调整的范围由于已输出了一个,所以要减一,用i就行

   }

}

 

template  //基数排序,最大支持5位

void quwei(T a,int *wan,int *qian,int *bai,int *shi,int *ge)

{

   *wan=a/10000;

   *qian=(a-*wan*10000)/1000;

   *bai=(a-*wan*10000-*qian*1000)/100;

   *shi=(a-*wan*10000-*qian*1000-*bai*100)/10;

   *ge=a-*wan*10000-*qian*1000-*bai*100-*shi*10;

}

template

void RadixSort(T A[],int n)

{

   struct X

   {

       T element;

       int wan,qian,bai,shi,ge;

   }B[n],temp;

   int wan,qian,bai,shi,ge;

   int i;

   for(i=0;i

       quwei(A[i],&wan,&qian,&bai,&shi,&ge);

       B[i].element=A[i];

       B[i].wan=wan;B[i].qian=qian;B[i].bai=bai;B[i].shi=shi;B[i].ge=ge;

       //cout<

   }

   int t,j,z,y;

 

   for(i=0,t=0;i<10;i++){

       for(j=0;j

           if(B[j].ge==i) {temp=B[j];for(z=j;z>t;z–) B[z]=B[z-1];B[t]=temp;t++;}

       }

   }for(y=0;y

   for(i=0,t=0;i<10;i++){

       for(j=0;j

           if(B[j].shi==i) {temp=B[j];for(z=j;z>t;z–) B[z]=B[z-1];B[t]=temp;t++;}

       }

   }for(y=0;y

 

   for(i=0,t=0;i<10;i++){

       for(j=0;j

           if(B[j].bai==i) {temp=B[j];for(z=j;z>t;z–) B[z]=B[z-1];B[t]=temp;t++;}

       }

   }for(y=0;y

   for(i=0,t=0;i<10;i++){

       for(j=0;j

           if(B[j].qian==i) {temp=B[j];for(z=j;z>t;z–) B[z]=B[z-1];B[t]=temp;t++;}

       }

   }for(y=0;y

   for(i=0,t=0;i<10;i++){

       for(j=0;j

           if(B[j].wan==i) {temp=B[j];for(z=j;z>t;z–) B[z]=B[z-1];B[t]=temp;t++;}

       }

   }

 

   for(i=0;i

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//Untitled5.cpp

#include

#include

#include

#include

#include “sort.h”

 

using namespace std;

 

template

void copy(T source[],T copy[],int n)

{

   for(int i=0;i

       copy[i]=source[i];

   }

}

 

int main()

{

   ///*

   const int n=6;

   int tt[n]={46,79,56,38,40,84};

   int test[n];

   //*/

   /*

   const int n=19;

   int tt[n];

   int test[n];

   srand( (unsigned int)time(0) ); //产生随机数种子

   for(int i=0;i

       tt[i] = rand() % (n + 1 – 0) + 0;

   }

   */

 

   clock_t start=0, finish=0;  //时间变量

 

   PrintArray(tt,n);cout<

   system(“pause”);

 

   copy(tt,test,n);cout<<" SelectSort:"<

   start = clock();

   SelectSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" InsertSort:"<

   start = clock();

   InsertSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" BubbleSort:"<

   start = clock();

   BubbleSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" QuickSort:"<

   start = clock();

   QuickSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" MergeSort:"<

   start = clock();

   MergeSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" HeapSort:"<

   start = clock();

   HeapSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   copy(tt,test,n);cout<<" RadixSort:"<

   start = clock();

   RadixSort(test,n);

   finish = clock();cout<<" "<

   system(“pause”);

 

   cout<<"因为样本太少,加上有输出耽误的时间,导致这边的计时不太有说服力。在40000个随机数和去除输出的情况下,快排只需要7ms,最快。"<

   system(“pause”);

}

 

 

 

 

 

 

 

 

 

 

内排序算法演示.apk:

http://pan.baidu.com/s/1gd29wOF

内排序算法演示.exe:

http://pan.baidu.com/s/1bn6LuHL

发表评论

电子邮件地址不会被公开。 必填项已用*标注