程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之合並排序)

一步一步寫算法(之合並排序)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    前面一篇博客提到的快速排序是排序算法中的一種經典算法。和快速排序一樣,合並排序是另外一種經常使用的排序算法。那麼合並排序算法有什麼不同呢?關鍵之處就體現在這個合並上面。

    合並算法的基本步驟如下所示:

    1)把0~length-1的數組分成左數組和右數組

    2)對左數組和右數組進行迭代排序

    3)將左數組和右數組進行合並,那麼生成的整個數組就是有序的數據數組

 

 

    下面就開始實踐操作:

    a)創建函數,判斷參數的合法性

 

 

 

void merge_sort(int array[], int length) 

    if(NULL == array || 0 == length) 

        return ; 

    _merge_sort(array, 0, length-1); 

void merge_sort(int array[], int length)

{

       if(NULL == array || 0 == length)

              return ;

       _merge_sort(array, 0, length-1);

}

    b)進行merge函數迭代操作

 

 

 

void _merge_sort(int array[], int start, int end) 

    if(start >= end) 

        return; 

 

    int middle = start + ((end - start) >> 1); 

    _merge_sort(array, start, middle); 

    _merge_sort(array, middle + 1, end); 

    _merge_data_in_array(array, start, middle, end); 

void _merge_sort(int array[], int start, int end)

{

       if(start >= end)

              return;

 

       int middle = start + ((end - start) >> 1);

       _merge_sort(array, start, middle);

       _merge_sort(array, middle + 1, end);

       _merge_data_in_array(array, start, middle, end);

}

    c)對合並後的隊列進行合並操作

 

 

 

void _merge_data_in_array(int array[], int start, int middle, int end) 

    int length = end - start + 1; 

    int* pData = NULL; 

    int left = start; 

    int right = middle + 1; 

    int all = 0; 

 

    /* allocate new memory to the space */ 

    pData = (int*) malloc(sizeof(int) * length); 

    assert(NULL != pData); 

    memset(pData, 0, length); 

 

    /* begin to move data */ 

    while(right <= end){ 

        while(array[left] <= array[right] && left <= middle){ 

            pData[all] = array[left]; left ++; all ++; 

        } 

 

        if(left > middle)  { 

            break; 

        } 

 

        while(array[left] > array[right] && right <= end){ 

            pData[all] = array[right]; right ++; all ++; 

        } 

    } 

 

    /* move the left data */ 

    if(left <= middle) 

        memmove(&pData[all], &array[left], sizeof(int) * (middle -left +1)); 

 

    if(right <= end) 

        memmove(&pData[all], &array[right], sizeof(int) * (end - right + 1)); 

     

    memmove(&array[start], pData, sizeof(int) * length); 

    free(pData); 

void _merge_data_in_array(int array[], int start, int middle, int end)

{

       int length = end - start + 1;

       int* pData = NULL;

       int left = start;

       int right = middle + 1;

       int all = 0;

 

       /* allocate new memory to the space */

       pData = (int*) malloc(sizeof(int) * length);

       assert(NULL != pData);

       memset(pData, 0, length);

 

       /* begin to move data */

       while(right <= end){

              while(array[left] <= array[right] && left <= middle){

                     pData[all] = array[left]; left ++; all ++;

              }

 

              if(left > middle)  {

                     break;

              }

 

              while(array[left] > array[right] && right <= end){

                     pData[all] = array[right]; right ++; all ++;

              }

       }

 

       /* move the left data */

       if(left <= middle)

              memmove(&pData[all], &array[left], sizeof(int) * (middle -left +1));

 

       if(right <= end)

              memmove(&pData[all], &array[right], sizeof(int) * (end - right + 1));

      

       memmove(&array[start], pData, sizeof(int) * length);

       free(pData);

}    注: 文中使用的pData動態內存不是一種最優的處理辦法,實際開發中可以由其他形式的數據類型代替。

 

 

 

 

    d)編寫測試用例

 

 

static void test1() 

    int array[] = {1}; 

    merge_sort(array, sizeof(array)/sizeof(int)); 

 

static void test2() 

    int array[] = {2, 1}; 

    merge_sort(array, sizeof(array)/sizeof(int)); 

    assert(1 == array[0]); 

    assert(2 == array[1]); 

 

static void test3() 

    int array[] = {3, 2, 1}; 

    merge_sort(array, sizeof(array)/sizeof(int)); 

    assert(1 == array[0]); 

    assert(2 == array[1]); 

    assert(3 == array[2]); 

 

static void test4() 

    int array[] = {4, 3, 5, 1}; 

    merge_sort(array, sizeof(array)/sizeof(int)); 

    assert(1 == array[0]); 

    assert(3 == array[1]); 

    assert(4 == array[2]); 

    assert(5 == array[3]); 

static void test1()

{

       int array[] = {1};

       merge_sort(array, sizeof(array)/sizeof(int));

}

 

static void test2()

{

       int array[] = {2, 1};

       merge_sort(array, sizeof(array)/sizeof(int));

       assert(1 == array[0]);

       assert(2 == array[1]);

}

 

static void test3()

{

       int array[] = {3, 2, 1};

       merge_sort(array, sizeof(array)/sizeof(int));

       assert(1 == array[0]);

       assert(2 == array[1]);

       assert(3 == array[2]);

}

 

static void test4()

{

       int array[] = {4, 3, 5, 1};

       merge_sort(array, sizeof(array)/sizeof(int));

       assert(1 == array[0]);

       assert(3 == array[1]);

       assert(4 == array[2]);

       assert(5 == array[3]);

}

分析快速排序和合並排序的相同點和不同點:

    相同點: 都是迭代操作

    不同點: 快速排序,先分類再迭代;合並排序,先迭代再合並

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved