#include <iostream>
#include <cstdlib>
#include <ctime>

inline void exch(int &A, int &B){int temp = A; A = B; B = temp;}
inline void compexch(int &A, int &B){if (A > B) exch(A,B);}

void selection_sort(int src[],int lengh);
void insertion_sort(int src[],int lengh);
void insertion_sort_adv(int src[],int lengh);
void bubble (int src[] , int lengh);
void quick_sort(int src[],int l, int lengh);
int partition(int src[],int l, int lengh);
void shell_sort(int src[], int lengh);

using namespace std;

int main()
{
 int *src;
 int index_i;
 clock_t start, finish;
 clock_t save[10];
 int max;

 cout <<"enter\n";
 cin >>max;

 src = (int *) malloc (max*sizeof(int));

 for (index_i = 0; index_i < max ; index_i++)
  src[index_i] =max - index_i;

 start = clock();
 selection_sort( src, max-1);
 finish = clock();
 save[0] =finish - start ;

////////////////////////////////////////////////////////////////

 for (index_i = 0; index_i < max ; index_i++)  //reset
  src[index_i] =max - index_i;

 start = clock();
 insertion_sort(src ,max - 1);
 finish = clock();
 save[1] =finish - start ;

////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////
 
 for (index_i = 0; index_i < max ; index_i++)  //reset
  src[index_i] =max - index_i;

 start = clock();
 insertion_sort_adv(src ,max - 1);
 finish = clock();
 save[2] =finish - start ;

////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////

 for (index_i = 0; index_i < max ; index_i++)  //reset
  src[index_i] =max - index_i;

 start = clock();
 bubble (src , max-1);
 finish = clock();

 save[3] =finish - start ;

////////////////////////////////////////////////////////////////

 
////////////////////////////////////////////////////////////////

 for (index_i = 0; index_i < max ; index_i++)  //reset
  src[index_i] =max - index_i;

 start = clock();
 shell_sort (src , max-1); 
 finish = clock();

 save[4] =finish - start ;

////////////////////////////////////////////////////////////////

 cout << "\n      "<<max<<" Itmes sorting\n";
 cout << "selection sort          time: " << save[0] << "ms" << endl;
 cout << "insertion sort          time: " << save[1] << "ms" << endl;
 cout << "insertion sort  adv   time: " << save[2] << "ms" << endl;
 cout << "bubble                     time: " << save[3] << "ms" << endl;
 cout << "shell sort                 time: " << save[4] << "ms" << endl;

 free (src);
 system("pause");
 return 0 ;
}

////////////////////////////////////////////////
////////////////////////////////////////////////
////////////////////////////////////////////////

void selection_sort(int src[],int lengh)    //选择排序
{
 for ( int i = 0 ; i < lengh ; i++)
 {
  int min = i;

  for (int j = i + 1 ; j <= lengh ; j++)
  {
   if (src[j] < src[min])
    min = j;

   exch(src[i] , src[min]);
  }
 }
}

void insertion_sort(int src[],int lengh)  //插入排序
{
 /*
 for ( int i = 1 ; i <= lengh ; i++ )
 {
  for ( int j = i ; j > lengh ; j--)
   compexch(src[j-1],src[j]);
 }

 */
 int i,j;
 int next;

 for (i = 1 ; i< lengh ; i++)
 {
  next = src[i];

  for (j = i - 1 ; j >= 0 && next < src[j] ; j--)
   src[j+1] = src[j];
  
  src[j+1] = next;
 }
}

void insertion_sort_adv(int src[],int lengh)//改进版 插入排序
{
 int i;

 for (i = lengh ; i > 0 ; i--)
  compexch(src[i-1],src[i]);
 
 for ( i = 2 ; i <= lengh ; i++)
 {
  int j = i ;
  int v = src[i];

  while ( v < src[j-1])
  {
   src[j] = src[j-1];
   j--;
  }

  src[j] = v;
 }
}

void bubble (int src[] , int lengh)
{
 for (int i = 0 ; i < lengh ; i++)
 {
  for (int j = lengh ; j > i ; j--)
  {
   compexch(src[j-1],src[j]);
  }
 }
}

void quick_sort(int src[], int l,int lengh)
{
 if ( lengh <= 0 ) return ;

 int i = partition(src ,0,  lengh);

 quick_sort(src , 0 , i - 1);
 quick_sort(src , i + 1 , lengh);
}

int partition(int src[], int l,int lengh)
{
 int i = l-1 ,j = lengh ;
 int v = src[lengh];

 for (;;)
 {
  while (src[++i] < v) ;
  while (v < src[--j])
  {
   if ( j == l) break;
  }

  if (i >= j)
   break;
  exch(src[i],src[j]);
 }  
 
 exch(src[i],src[lengh]);
 return i;
}

void shell_sort(int src[], int lengh)
{
 int h;
 for (h=1 ; h <= lengh / 9 ; h = 3*h+1) ;

 for ( ; h > 0 ; h /= 3)
 {
  for (int i = h; i <= lengh ; i++)
  {
   int j = i;
   int v = src[i];

   while (j >= h && v < src[j-h])
   {
    src[j] = src[j-h];
    j -= h;
   }

   src[j] = v;
  }
 }
}

测试结果大致如下:
---------------------------------------------------------------
selection sort          time:   157163 ms
insertion sort         time:   39598 ms
insertion sort adv   time:   37767 ms
bubble  sort           time:   223095 ms
shell sort                time:    16 ms
---------------------------------------------------------------
   因为我只是将书上的算法实现代码运行了一下,所以上述各个排序算法的实现都不一定是最优的.至于如何优化,我会慢慢学习的.
  如果有哪位朋友知道还望告知小弟.

评论