1.cpp

数据结构 内部排序分析（C++源代码） 其中包括 第一种算法为选择排序

第一种算法为选择排序，二为插入排序，三是冒泡排序，六是二分法插入排序，随机产生了10000个数字
#include "stdafx.h"
#include <iostream>
#include "windows.h"
#include "stdlib.h"
#include "time.h"
using namespace std;
const int count = 10000;
const int SELECT = 1;
const int INSERT = 2;
const int BUBBLE = 3;
const int HEAP   = 4;
const int QUICK =  5;
const int BIINSERT =6;
void QuickSort(int a[],int start,int end)
{
    int i,j;

 if(start<end)
 {
  i = start;
  j = end;
     long lTemp = a[start];
  do 
  {
     while(i<j&&lTemp<a[j]) j--;  //从最右开始找位置
     if(i<j)                                     //与左边交换后掉头
     {
      swap(a[j],a[i]);
      i++;
     }
     while(i<j&&a[i]<lTemp) i++; //从左边找
     if(i<j)
     {
      swap(a[j],a[i]);
      j--;
     }  
  } while(i<j);   //最终找到定位的地方
 a[i] = lTemp;  //元素放入，分成两个序列
 QuickSort(a,start,i-1);  //左边序列
 QuickSort(a,i+1,end); //右边序列
 }
}

void swap(int &a,long &b)
{
 long lTemp;
 lTemp = a;
 a = b;
 b = lTemp;
}
void sort(int a[],int count,int lMethod)
{
 switch(lMethod)
 {
 case SELECT:
  {
   //Selected Sort
   for(int i=0;i<count;i++)
   {
      for(int j = i+1;j<count;j++)
      {
       if(a[j]>a[i])
       {
      swap(a[j],a[i]);  
       }
      }
   }
  }
  break;
 case INSERT:  //Insert Sort
  {
   long lTemp;
   for(int i = 0;i<count;i++)
   {
    int j = i+1;
    long lTemp = a[j] ;  //
    while(j>0&&lTemp<a[j-1])
    {
     a[j] = a[j-1];
     j--;
    }
    a[j] = lTemp;
   }
  }
  break;
 case BUBBLE: //Bubble Sort
  {
             for(int i = 0;i< count;i++)
    {
     for(int j=i+1;j<count;j++)
     {
      if(a[j]<a[j-1])
      {
       long lTemp;
       lTemp = a[j];
       a[j]= a[j-1];
       a[j-1] = lTemp; 
      }
     }
    }
  }
  break;
 case HEAP: //Heap Sort
  {

  }
  break;
 case QUICK: //Quick Sort
  {
          QuickSort(a,0,count-1);  
  }
  break;
 case BIINSERT:
  {
    long lTemp;
   for(int i = 0;i<count;i++)
   {
    int j = i+1;
    long lTemp = a[j] ;
    int k,m,n;
    m = 0;n = j;
    k = (m+n)/2;
    while(m<n)
    {
     if(lTemp>a[k])
      m = k+1;
     else
      n = k-1;
     k = (m+n)/2;
    }
    for(int L=j ; L>k ; L--)
    {
     a[L] = a[L-1];
    }
    a[L] = lTemp;
   }
         
  }
  break;
 }
}
int main(int argc, char* argv[])
{
 int a[count];
 int b[count];
  srand( (unsigned)time( NULL ) );
  long lNum = 0;
     for( int i = 0; i < count;i++ ) 
  {
  lNum = rand()%count;
  if(i%10==0)
   printf("\n");
     printf( " %6d", lNum );
  a[i] = lNum;
  b[i] = lNum;
  }
  printf("\n");
 long lStart = GetTickCount();
 sort(a,count,1);
 long lEnd = GetTickCount();
 cout<<"SELECT sort times= "<<( lEnd - lStart)<<"  uMinutes \n";

     for(  i = 0; i < count;i++ ) 
  {
  a[i] = b[i];
  } 

 lStart = GetTickCount();
 sort(a,count,2);
 lEnd = GetTickCount();
 cout<<"INSERTsort times= "<<( lEnd - lStart)<<"  uMinutes \n";

     for(  i = 0; i < count;i++ ) 
  {
  a[i] = b[i];
  } 
 lStart = GetTickCount();
 sort(a,count,3);
 lEnd = GetTickCount();
 cout<<"BUBBLE sort times= "<<( lEnd - lStart)<<"  uMinutes \n"; 
     for(  i = 0; i < count;i++ ) 
  {
  a[i] = b[i];
  } 
 lStart = GetTickCount();
 sort(a,count,6);
 lEnd = GetTickCount();
 cout<<"BIINSERT sort times= "<<( lEnd - lStart)<<"  uMinutes \n";
     for(  i = 0; i < count;i++ ) 
  {
  a[i] = b[i];
  } 
 lStart = GetTickCount();
 sort(a,count,5);
 lEnd = GetTickCount();
 cout<<"QUICK sort times= "<<( lEnd - lStart)<<"  uMinutes \n";
    for( int j = 0; j < count;j++ )
 {
//  if(j%10==0)
//   printf("\n");
//  printf( " %6d", a[j] );
 }
 return 0;
}

下面是测试结果：
一次：
SELECT sort times= 1078  uMinutes
INSERTsort times= 156  uMinutes
BUBBLE sort times= 438  uMinutes
BIINSERT sort times= 141  uMinutes
QUICK sort times= 0  uMinutes
二次：
SELECT sort times= 1047  uMinutes
INSERTsort times= 156  uMinutes
BUBBLE sort times= 453  uMinutes
BIINSERT sort times= 141  uMinutes
QUICK sort times= 0  uMinutes
三次：
SELECT sort times= 1063  uMinutes
INSERTsort times= 156  uMinutes
BUBBLE sort times= 437  uMinutes
BIINSERT sort times= 141  uMinutes
QUICK sort times= 15  uMinutes

从测试结果中可以看到，数据量大的时候，二分法插入排序的性能较好。快速排序最佳
冒泡排序由于是稳定的排序方法，排序性能适中，比较适合使用，当数据量大、不要求稳定排序时可以考虑二分法或快速，堆排序。
小数据量时用插入或冒泡排序就够了，针对随机数，通常不要使用选择排序。