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

C言語 完成歸並排序算法

編輯:關於C++

C言語 完成歸並排序算法。本站提示廣大學習愛好者:(C言語 完成歸並排序算法)文章只能為提供參考,不一定能成為您想要的結果。以下是C言語 完成歸並排序算法正文


C言語 完成歸並排序算法

歸並排序(Merge sort)是創立在歸並操作上的一種無效的排序算法。該算法是采用分治法(Divide and Conquer)的一個十分典型的使用。

一個歸並排序的例子:對一個隨機點的鏈表停止排序

算法描繪

歸並操作的進程如下:

    請求空間,使其大小為兩個曾經排序序列之和,該空間用來寄存兼並後的序列 設定兩個指針,最初地位辨別為兩個曾經排序序列的起始地位 比擬兩個指針所指向的元素,選擇絕對小的元素放入到兼並空間,並挪動指針到下一地位 反復步驟3直到某一指針抵達序列尾 將另一序列剩下的一切元素直接復制到兼並序列尾

特點:歸並排序是波動的排序.即相等的元素的順序不會改動,  速度僅次於疾速排序,但較波動。

歸並操作

歸並操作(merge),也叫歸並算法,指的是將兩個順序序列兼並成一個順序序列的辦法。

如:設無數列 [6,202,100,301,38,8,1]

初始形態:6, 202, 100, 301, 38, 8, 1

第一次歸並後:[6, 202], [100, 301], [8, 38], [1],比擬次數:3;

第二次歸並後:[6, 100, 202, 301],[1, 8, 38],比擬次數:4;

第三次歸並後:[1, 6, 8, 38, 100, 202, 301],比擬次數:4;

總的比擬次數為:3+4+4=11,;

逆序數為14;

算法完成

// Completed on 2014.10.11 17:20
// Language: C99
//
// 版權一切(C)codingwu  (mail: [email protected]) 
// 博客地址:http://www.cnblogs.com/archimedes/
#include<stdio.h>
#include<stdlib.h>void merge_sort(int *list, const int first, const int last)
{
  int len= last-first+1; 
  int left_min,left_max;  //左半區域邊界 
  int right_min,right_max; //右半區域邊界 
  int index;
  int i;
  int *tmp;
  tmp = (int *)malloc(sizeof(int)*len);
  if( tmp == NULL || len <= 0 )
    return;
  
  for( i = 1; i < len; i *= 2 )
  {
    for( left_min = 0; left_min < len - i; left_min = right_max)
    {
      int j;
      right_min = left_max = left_min + i;
      right_max = left_max + i;
      j = left_min;
      if ( right_max > len )
        right_max = len;
      index = 0;
      while( left_min < left_max && right_min < right_max )
      {
        tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]);
      }
      while( left_min < left_max )
      {
        list[--right_min] = list[--left_max];
      }
      while( index > 0 )
      {
        list[--right_min] = tmp[--index];
      }
    }
  }
  free(tmp);
}
int main()
{
  int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
  int n, mid;
  n = sizeof(a) / sizeof(a[0]);
  mid = n / 2;
  merge_sort(a, 0, n - 1);
  for(int k = 0; k < n; k++)
    printf("%d ", a[k]);
  printf("\n");
  return 0;
}

運用遞歸完成:

// Completed on 2014.10.11 18:20
// Language: C99
//
// 版權一切(C)codingwu  (mail: [email protected]) 
// 博客地址:http://www.cnblogs.com/archimedes/
#include<stdio.h>
#include<stdlib.h>
void merge(int *array,const int first, const int mid, const int last)
{
  int i,index;
  int first1,last1;
  int first2,last2;
  int *tmp;
  tmp = (int *)malloc((last-first+1)*sizeof(int));
  if( tmp == NULL )
    return;
  first1 = first;
  last1 = mid;
  first2 = mid+1;
  last2 = last;
  index = 0;
  while( (first1 <= last1) && (first2 <= last2) )
  {
    if( array[first1] < array[first2] )
    {
      tmp[index++] = array[first1];
      first1++;
    }
    else{
      tmp[index++] = array[first2];
      first2++;
    }
  }
  while( first1 <= last1 )
  {
    tmp[index++] = array[first1++];
  }
  while( first2 <= last2 )
  {
    tmp[index++] = array[first2++];
  }
  for( i=0; i<(last-first+1); i++)
  {
    array[first+i] = tmp[i];
  }
  free(tmp);
}
void merge_sort(int *array, const int first, const int last)
{
  int mid = 0;
  if(first < last)
  {
    mid = (first + last) / 2;
    merge_sort(array, first, mid);
    merge_sort(array, mid + 1, last);
    merge(array, first, mid, last);
  }
}
int main()
{
  int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
  int n, mid;
  n = sizeof(a) / sizeof(a[0]);
  mid = n / 2;
  merge_sort(a, 0, n - 1);
  for(int k = 0; k < n; k++)
    printf("%d ", a[k]);
  printf("\n");
  return 0;
}

感激閱讀,希望能協助到大家,謝謝大家對本站的支持!

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