常用的排序算法C语言实现

#include
#include

#define N  10
 

void initArr(int a[] );
int  findKey(int a[], int key);
void print( int  a[] );
void quickSort( int a[] );
void doQuickSort( int a[], int left, int right );
void bubbleSort( int a[] );
void swap( int *a, int *b);
void insertSort( int a[] );
void shellSort( int a[] );
void doShellSort( int a[], int dk );
void selectSort( int a[] );
int  selectMinKey( int a[], int beginIndex );

int  main(void){
 int a[N] = {-1};
 initArr(a);
 print(a);
 selectSort(a);
 print(a);
  
}

int  selectMinKey( int a[], int beginIndex ){
 int minValue = a[beginIndex];
 int retIndex = beginIndex;
 int i = 0;
 for( i = beginIndex+1; i < N; i++ )
  if( a[i] < minValue ){
   minValue = a[i];
   retIndex = i;
  }
 return retIndex;
}

void selectSort( int a[] ){
 int i = 0;
 int j = 0;
 for( i = 0; i < N; i++ ){
  j = selectMinKey( a, i );
  if( i != j )
   swap( &a[i], &a[j] );
 }
}

void shellSort( int a[] ){
 int delta[3] = {1,3,5};
 int i = 0;
 for( i = 0; i < 3; i++ )
  doShellSort( a, delta[i] );

}

void doShellSort( int a[], int dk ){
 int i = 0;
 int j = 0;
 int temp = 0;
 for( i = 1+dk; i < N; i++ ){
  temp = a[i];
  for( j = i-dk; a[j] > temp && j >=0; j -= dk )
       a[j+dk] = a[j];
  a[j+dk] = temp;
 }

}

void insertSort( int a[] ){
 int i = 0;
 int j = 0;
 int temp = 0;
 for( i = 1; i < N; i++ ){
  temp = a[i];
  for( j = i-1; a[j] > temp && j >= 0; j-- )
   a[j+1] = a[j];
  a[j+1] = temp;
 }

}

void swap( int *a, int *b){
 int temp;
 temp = *a;
 *a = *b;
 *b = temp;
}

void bubbleSort( int a[] ){
 int i = 0;
 int j = 0;
 int flag = 0;
 for( i = 0; i < N; i++){
  flag = 0;
  for( j = 0; j < (N-1)-i; j++ ){

 /* 这里注意 j < N-1-i 而不是 j < N-i
   if( a[j] < a[j+1] ){
    swap( &a[j], &a[j+1] );
    flag = 1;
   }
  }
  if( flag == 0 )
   return;
 }
}

void quickSort( int a[] ){
 doQuickSort( a, 0, N-1 );
}

void doQuickSort( int a[], int left, int right ){
 int low = left;
 int high = right;
 int temp = a[low];

 while( low < high ){
  while( low < high && a[high] >= temp )
   high --;
  a[low] = a[high];
  while( low < high && a[low] <= temp )
   low ++;
  a[high] = a[low];
 }
 a[low] = temp;
 
 if( left < low-1 )
  doQuickSort( a, left, low-1 );
 if( low+1 < right )
  doQuickSort( a, low+1, right );
}

 

void print( int  a[] ){
 int i = 0;
 for( i = 0; i < N; i++ )
  printf("a[%d] = %d\n,", i,a[i]);
 printf("\n");

}

void initArr(int a[] ){
 int i = 0;
 int temp = 0;
 srand(0);
 for( i = 0; i < N; i++ ){
  do{
   temp = rand()%100;
  }while( findKey(a, temp) == 1 );

  a[i] = temp;
 }
}

int  findKey(int a[], int key){
 int i = 0;
 for( i = 0; i < N; i++ )
  if( a[i] == key )
   return 1;
 return 0;

}