基本排序算法

贴代码，不解释。

#include
#include
#include
#include

#define ARRAYLEN 15

void genIntArr(int a[], int n);
void swap(int *a, int *b);
void printIntArr(int a[], const int size);

/*
 * in java, Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
*/
void insenBubble(char *str);

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

//================================
// bubble sort int array
// O(n^2),stable
//================================
void bubbleSort(int arr[], const int size)
{
 int i,j,flag;
 int temp = 0;
 
 for(i=0; i {
  flag = 1;
  for(j=0; j  {
   if(arr[j]>arr[j+1])
   {
    temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    flag = 0;
   }
  }
  if(flag) break;
 }
}

/* Case Insensitive Char Compare
 * @return 1 for sa>sb, or 0.
 */
int insenbigger(char sa, char sb)
{
 // toupper
 if(sa>='a' && sa<='z')
  sa -= ('a'-'A'); 
 if(sb>='a' && sb<='z')
  sb -= ('a'-'A');
 //compare
 if( (sa - sb) > 0 )
  return  1;
 else
  return 0;
}

/*
 * in java, Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER);
*/
void insenBubble(char *str)
{
 int i,j,flag;
 if(NULL == str)
  return;
 int len = strlen(str);
 char c;
 
 for(i=0; i {
  flag = 1;
  for(j=0; j  {
   if(insenbigger(str[j],str[j+1]))
   {
    c = str[j];
    str[j] = str[j+1];
    str[j+1] = c;
    flag = 0;
   }
  }
  if(flag) break;
 }
}

//========================================
// selection sort. O(n^2) Not stable
// is better than bubble when n is small
//========================================
void selectSort(int a[], int n)
{
    int i,j,t,min;
    for(i=0; i    {
        min = i; //find the minimum
        for(j=i+1; j        {
            // (n-1)+(n-2)+...+1 = n*(n-1)/2 compare
            if(a[j]                min = j;
        }
        swap(&a[min], &a[i]);
    }
}

//================================
// insert sort int array
// O(n^2), stable
//================================
void insertSort(int arr[], const int size)
{
 int i,j,temp;
 for(i=1; i {
  temp = arr[i];
  for(j=i-1; j>=0 && (arr[j]>temp); --j)
  { 
   arr[j+1] = arr[j];
  }
  arr[j+1] = temp;
  /*
   * This is OK too.
  for(j=i; j>0 && (arr[j-1]>temp); --j)
  { arr[j] = arr[j-1]; }
  arr[j] = temp;
  */
 }
}

//================================
// merge sort int array
// O(nlogn), O(n), stable
//================================
// merge before sort, assert 0<=low<=mid void domerge(int array[], int low, int mid, int high)
{
    int i, k;
    int *temp = (int *)malloc( (high-low+1)*sizeof(int) );
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;

    for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)
    {
        if(array[begin1]<=array[begin2])
        {
        temp[k] = array[begin1++];
        }
        else
        {  
        temp[k] = array[begin2++];
        }
    }
    if(begin1 <= end1)
    {
        memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
    }
    if(begin2 <= end2)
    {
        memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
    }
    memcpy(array+low, temp, (high-low+1)*sizeof(int));
    free(temp);
}
// merge_sort(data, 0, LEN-1);
void merge_sort(int array[], unsigned int first, unsigned int last)
{
 int mid = 0;
 if(first < last)
 {
     //mid = (first+last)/2; //care of overflow
  mid = (first & last) + ( (first ^ last) >> 1 );
  merge_sort(array, first, mid);
  merge_sort(array, mid+1, last);
  domerge(array, first, mid, last);
 }
}

//================================
// Heap sort int array
// O(nlogn), O(1), Not stable
//================================
void HeapAdjust(int array[], int cur, int len)
{
    int nChild, nTemp;
   
    for(nTemp=array[cur]; (2*cur + 1) < len; cur = nChild)
    {
        nChild = 2 * cur + 1;
        // get the bigger one in child node
        if( (nChild < len - 1) && (array[nChild+1] > array[nChild]) )
        {
            ++nChild;
        }
        // if the bigger child > parent, move it up as new parent
        if(nTemp < array[nChild])  // nTemp!!
        {
         array[cur] = array[nChild]; //or swap(array[cur],array[nChild])
     }
        else
            break;
        //printf("\ns=%d,child=%d: %d->[%d]; ", cur, nChild, array[nChild], cur);
    }
    array[cur] = nTemp;
    //printf("[%d]=%d\n",cur,nTemp);
}

// HeapSort(a,LEN);
void HeapSort(int array[], int len)
{
    int i;
    // creat an initial heap
    for(i = len/2 - 1; i >= 0; --i)
    {
        HeapAdjust(array, i, len);
    }
    //
    for(i = len - 1; i > 0; --i)
    {
        // swap the first and last
        swap( &array[0], &array[i] );
        // after adjust once, make the first element the max
        HeapAdjust(array, 0, i);
    }
}

//==================================================
// Shell sort int array.
// O(n^3/2) [O(nlogn) to O(n^2)], Not stable
// Just change the insertSort step_size of 1 to gap
//==================================================
void shellSort(int arr[], const int n)
{
 int i,j,temp;
 int gap=0;
 while(gap <= n)
  gap = gap*2 + 1;
 //printf("shellSort gap = %d\n", gap);
 while(gap > 0)
 {
  for(i = gap; i < n; ++i)
  {
   temp = arr[i];
   for(j=i-gap; j>=0 && (arr[j]>temp); j -= gap)
   {
    arr[j+gap] = arr[j];
   }
   arr[j+gap] = temp;
  }
  gap = (gap-1)/2;
 }
}

//================================
// quick sort int array
// O(nlogn) Not stable
//================================
void quickSort(int data[], int low, int high)
{
 int i,j,key;
 key = data[low];
 i = low;
 j = high;
 if(low > high)
  return;
 while(i {
  while(data[j]>=key && j>i)
  {
   j--;
  }
  data[i] = data[j];
  while(data[i]<=key && i  {
   i++;
  }
  data[j] = data[i];
 }
 data[i] = key;
 quickSort(data, low, i-1);
 quickSort(data, i+1, high);
}

//================================
// quick sort too - int array
// Not always better than quickSort
//================================
void quick2Sort(int data[], int low, int high)
{
 int i,j,key;
 int pivot;
 if(low > high)
  return;
 key = data[high];
 i = low-1;
 for(j = low; j < high; ++j)
 {
  if(data[j] <= key)
  {
   ++i;
   swap(data+i, data+j);
  }
 }
 pivot=i+1;
 swap(data+pivot, data+high);
 quick2Sort(data, low, pivot-1);
 quick2Sort(data, pivot+1, high);
}

// printf to show int array.
void printIntArr(int a[], const int size)
{
 int i=0;
 for(; i  printf("%d ", a[i]);
 printf("\n");
}

// Deprecated.
void genIntArr(int a[], int size)
{
 int i;
 srand( (unsigned)time(0) );
 for(i=0; i {
  a[i] = rand()%200;
 }
}

// Generate n integers in [min, max)
// assert( 0 <= min && min < max )
void genIntFromTo(int a[], int min, int max, int n)
{
 int i,range;
 if(min > max) exit(0);
 
 range = (min != 0) ? (max - min + 1) : max;
 srand( (unsigned)time(0) );
 for(i=0; i < n; ++i)
 {
  a[i] = rand()%range + min;
 }
}

int main(void)
{
 int data[ARRAYLEN]; // = {49,38,65,97,76,13,27,38,9,81};
#if 0
 const char *c_str = "TestbbBASEa";
 //==================================
 // case insensitive bubble sort
 //-------------------------------
 char *str = (char *)malloc(strlen(c_str)+1);
 strcpy(str, c_str);
 printf("str is: %s\n", str);
 insenBubble(str);
 printf("sort str: %s\n", str);
 free(str);
#endif 
 //==========================
 // sort INT array
 //------------------------
 genIntFromTo(data, 10, 200, ARRAYLEN);
 printf("before sort:\n");
 printIntArr(data, ARRAYLEN);
 
    bubbleSort(data, ARRAYLEN);
//    insertSort(data, ARRAYLEN);
    //
//    selectSort(data, ARRAYLEN);
    //
//    HeapSort(data, ARRAYLEN);
 //
//    shellSort(data, ARRAYLEN);
 // quickSort(data, 0, ARRAYLEN-1);
//    quick2Sort(data, 0, ARRAYLEN-1);
 
 printf("after sort:\n");
 printIntArr(data, ARRAYLEN);
 //==========================

 return 0;
}