合併排序

合併就是把兩堆已經排序好的資料

按大小重新排列成一堆

//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define  LEFT      'L'
#define  RIGHT     'R'
//---------------------------------------------------------------------------
int      g_icount = 1;
//---------------------------------------------------------------------------
void mergeSort(int *list, int *tmp, char type, int left, int right)
{
    if(left >= right) return;
   
    int middle = (left+right)/2;
   
    mergeSort(list, tmp, LEFT,  left,     middle);
    mergeSort(list, tmp, RIGHT, middle+1, right);
   
    int indexL = left;
    int indexR = middle+1;
    int index  = 0;
   
    while(indexL <= middle && indexR <= right)
    {
        if(list[indexL] <= list[indexR])
        {
            tmp[index++] = list[indexL++];
        }
        else
        {
            tmp[index++] = list[indexR++];
        }
    }
   
    //Copy from Left
    for(int i = indexL; i <= middle; i++)
        tmp[index++] = list[i];
    //Copy from Right
    for(int i = indexR; i <= right; i++)
        tmp[index++] = list[i];
   
    //Debug
    printf("[%02d] %c ", g_icount++, type);
    for(int i = 0; i < index; i++)
        printf("%d ", tmp[i]);
    printf("\n");
   
    //Copy to list
    int j;
    for(int i = left, j = 0; i <= right; i++, j++)
        list[i] = tmp[j];   
}
//---------------------------------------------------------------------------
int main(void)
{
    int list[] = {12,15,49,22,15,10};
   
    int max = sizeof(list)/sizeof(int);
   
    int tmp[6];   
   
    mergeSort(list, tmp, LEFT, 0, max-1);
   
    printf("\nResult: ");
    for(int i = 0; i < max; i++)
        printf("%d ", list[i]);
    printf("\n\n");
       
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------
 

快速排序

//---------------------------------------------------------------------------
#define  SWAP(x,y) {int t; t = x; x = y; y = t;}
//---------------------------------------------------------------------------
#define  LEFT      'L'
#define  RIGHT     'R'
//---------------------------------------------------------------------------
int      g_icount = 1;
//---------------------------------------------------------------------------
void quickSort(char type, int preindex, int list[], int left, int right)
{
    int i     = left;
    int j     = right;
    int pivot = left;
    int max   = right;
    int min   = left;
   
    //current index
    int index = g_icount;
   
    //debug
    printf("(%02d) %02d %c  ", g_icount++, preindex, type);
   
    for(int i = left; i <= right; i++)
        printf("%02d ", list[i]);
    printf("\n");
   
    if(left >= right) return;
   
    while(i < j)
    {
        while(list[i] <= list[pivot] && i < max) i++;
       
        while(list[j] > list[pivot] && j > min) j--;
       
        if(i < j)
        {
            //i,j change
            SWAP(list[i], list[j]);
        }           
    }

    //pivot, j change
    SWAP(list[j], list[pivot]);
   
    quickSort(LEFT,  index, list, left, j-1);
    quickSort(RIGHT, index, list, j+1, right);
}