来源于《算法导论》第二版

 

1.插入排序

insertion-sort(A)

for j=2 to length[A]

{

    key = A[j]

    i = j - 1;

    while(i>0 && A[i]>key)

    {

          A[i+1] = A[i];

          i = i - 1;

    }   

    A[i+1] = key;

}

 //int a[] = {5,4,3,1,6,8,9,16,15};

void insert_sort(int* a, int len)

{

  for(int i=1; i<len; i++)

  {

     int j=i-1;

     int key = a[i];

     while(j>=0 && a[j]> key )

     {

        a[j+1] = a[j];

        j--;

     }

     a[j+1] = key;

   }

}

insert_sort(a, sizeof(a)/sizeof(a[0]));

 

 

2.合并排序

merge(A, p, q, r)

{

    n = q - p + 1;

    l = r - q;

    for i = 1 to n

    {

       L[i] = A[p+i-1];

    }

    for j = 1 to l

    {

       R[j] = A[q+j];

    }

    L[n+1] = 无穷大；

    R[l+1] = 无穷大；

    i = 1;

    j = 1;

    for k = p to r

    {

        if L[i] <= R[j]

        {

          A[k] = L[i];

          i = i + 1;

         }

         else

         {

           A[k] = R[j];

           j = j + 1;

         }

    }

}

 

merge-sort(A, p, r)

{

  if p < r

  {

     q = 不小于(p + r ) / 2最小整数；

     merge-sort(A, p, q);

     merge-sort(A, q+1, r);

     merge(A, p, q, r);

   }

}

//int a[] = {5,4,3,1,6,8,9,16,15};

void merge(int* a, int low, int delimitor, int high)

{

   int alen = delimitor - low + 1;

   int blen = high - delimitor;

   int* atemp = (int*)malloc((alen+1)*sizoef(int));

   int* btemp = (int*)malloc((blen+1)*sizeof(int));

   atemp[alen] = 0x7fffffff;

   btemp[blen] = 0x7fffffff;

   int i=0;

   int j=0;

   for(i=0; i<alen; i++)

       atemp[i] = a[i];

   for(j=0; j<blen; j++)

       btemp[j] = a[delimitor+j+1];

   i=0;j=0;

   int k = low;

   while( k <= high )

   {

     if( atemp[i] < btemp[j])

     {

         a[k] = atemp[i];

         i++;

     }

     else

     {

         a[k] = btemp[j];

         j++;

      }

     k++;

   }

}

void merge_sort(int* a, int low, int high)

{

  if(low < high )

  {

     int q = (low+high)/2;

     merge_sort(a, low, q);

     merge_sort(a, q+1, high);

     merge(a, low, q, high);

  }

}

merge_sort(a, 0, sizeof(a)/sizeof(a[0]));

 

3.冒泡排序算法

bubblesort(A)

{

   for i = 1 to length[A]

   {

       for j = length[A] to i+1

       {

           if A[j] < A[j-1]

           {

                exchane A[j] and A[j-1];

           }

       }

   }

}

//int a[] = {5,4,3,1,6,8,9,16,15};

void bubble_sort(int* a, int len)

{

for(int i=0; i<len-1; i++)

{

  for(int j=len-1; j>i+1; j--)

  {

     if(a[j] < a[j-1] )

     {

       int temp = a[j-1];

       a[j-1] = a[j];

       a[j] = temp;

     }

  }

}

}

bubble_sort(a, sizeof(a)/sizeof(int));

 

 

4.选择排序

select-sort(A)

{

    for i = 1 to length[A]-1

    {

        key = A[i];

        k = i;

        for j = i+1 to length[A]

        {

           if A[j] < key

           {

              k = j;

           }

        }

        exchange A[i] and A[k];

    }

}

 ////int a[] = {5,4,3,1,6,8,9,16,15};

int select_sort(int* a, int len)

{

 int min = 0;

for(int i=0; i<len-1; i++)

{

  min=i;

  for(j=i+1; j<len; j++)

  {

     if( *(a+j) < *(a+min))

     {

       min = j;

     }

   }

  int temp = *(a+min);

  *(a+min) = *(a+i);

  *(a+i) = temp;

}

}

select_sort(a, sizeof(a)/sizeof(int));

 

5.快速排序

quicksort(A, p, r)

{

   if p < r

   {

      q = partition(A, p , r);

      quicksort(A, p, q-1);

      quicksort(A, q+1, r);

   }

}

 

int partition(A, p, r)

{

    x = A[r];

    i = p-1;

    for j = p  to r-1

    {

      if A[j] <= x

      {

        i = i+1;

        exchange A[i] and A[j];

      }

    }

    exchange A[i+1] and A[r];

    return i+1;

}

//int a[] = {5,4,3,1,6,8,9,16,15};

int partition(int* a, int low, int high)

{

int key = *(a+high);

int i = -1;

for(int j=0; j<high; j++)

{

  if( *(a+j)< key )

  {

    i++;

    int temp = *(a+j);

    *(a+j) = *(a+i);

    *(a+i) = temp;

  }

}

i++;

*(a+high) = *(a+i);

*(a+i) = key;

return i;

}

 

void quick_sort(int* a, int low, int high)

{

   if(low < high)

   {

     int q = partition(a, low, high);

     quick_sort(a, low, q-1);

     quick_sort(a, q+1, high);

   }

}

 

quick_sort(a, 0, sizeof(a)/sizeof(int)-1);