合并排序

2012-12-26 07:00:59   最后更新: 2015-08-06 16:18:23   访问数量:765




程序设计算法中有一个很常用的策略,那就是分治策略

 

分治策略一般递归的执行三个步骤:

  1. 分解问题
  2. 解决问题
  3. 合并结果

 

合并排序就是典型的分治策略下的排序算法,有两种实现方式,分别是自顶向下和自底向上的方法

 

 

合并排序中的merge函数的时间复杂度是O(n)的,因此算法的时间复杂度是O(nlogn)的,并且是稳定的,空间复杂度是O(n),需要动态开辟临时存储空间,不适合在低速存储器中使用

 

/* * file: main.c * author: 龙泉居士 * date: 2012-12-26 06:58 */ #include <stdio.h> #include "function/function.h" int merge_sort (int *array, int beg, int end) { if (array == NULL) { printf ("sort element error\n"); return -1; } if (beg < end) { int pos = (beg + end) / 2; merge_sort (array, beg, pos); merge_sort (array, pos+1, end); merge(array, beg, pos, end); } return 0; } int main () { int i, n=10; int array[10]; printf ("Please input 10 numbers:\n"); for (i=0; i!=n; ++i) scanf ("%d", &array[i]); if (merge_sort(array, 0, n-1)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

 

/* * file: function.h * author: 龙泉居士 * date: 2012-12-26 06:58 */ #ifndef FUNCTION_H #define FUNCTION_H int min (int *array, int *left, int *right, int pos, int end); int merge (int *array, int beg, int pos, int end); #endif

 

 

/* * file: function.c * author: 龙泉居士 * date: 2012-12-26 06:59 */ #include <stdio.h> #include <malloc.h> int min (int *array, int *left, int *right, int pos, int end) { if (*left == pos+1) { (*right)++; return array[*right-1]; } if (*right == end+1) { (*left)++; return array[*left-1]; } if (array[*left] < array[*right]) { ++(*left); return array[*left-1]; } ++(*right); return array[*right-1]; } int merge (int *array, int beg, int pos, int end) { if (array == NULL || beg > pos || pos > end) { printf ("merge element error\n"); return -1; } int *tmp = (int *)malloc((end - beg + 1)*sizeof(int)); int i, l=beg, r=pos+1; for (i=0; i<=end-beg; ++i) tmp[i] = min(array, &l, &r, pos, end); for (i=0; i<=end-beg; ++i) array[beg+i] = tmp[i]; free(tmp); return 0; }

 

 

/* * file: main.c * author: 龙泉居士 * date: 2012-12-26 06:59 */ #include <stdio.h> #include "function/function.h" int merge_sort (int *array, int n) { if (array == NULL) { printf ("sort element error\n"); return -1; } int k=1; while (k < n) { int i=0; while (1) { if (i+2*k >= n) { if (i+k < n) merge (array, i, i+k, n); break; } merge (array, i, i+k, i+2*k); i+=2*k; } k*=2; } return 0; } int main () { int i, n=0; int array[256]; printf ("Please input numbers, end by 9999:\n"); while (1) { scanf ("%d", &array[n]); if (array[n] == 9999) break; ++n; } if (merge_sort(array, n)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

 

/* * file: function.h * author: 龙泉居士 * date: 2012-12-26 07:00 */ #ifndef FUNCTION_H #define FUNCTION_H int min (int *array, int *left, int *right, int pos, int end); int merge (int *array, int i, int k, int n); #endif

 

 

/* * file: function.c * author: 龙泉居士 * date: 2012-12-26 07:00 */ #include <stdio.h> #include <malloc.h> #include "function.h" int min (int *array, int *left, int *right, int pos, int end) { if (*left == pos+1) { (*right)++; return array[*right-1]; } if (*right == end+1) { (*left)++; return array[*left-1]; } if (array[*left] < array[*right]) { ++(*left); return array[*left-1]; } ++(*right); return array[*right-1]; } int merge (int *array, int i, int k, int n) { if (array == NULL || i > k || k > n) { printf ("merge element error\n"); return -1; } int *tmp = (int *)malloc((n-i)*sizeof(int)); int j, l=i, r=k; for (j=0; j<n-i; ++j) tmp[j] = min (array, &l, &r, k-1, n-1); for (j=0; j<n-i; ++j) array[i+j] = tmp[j]; free(tmp); return 0; }

 

 






读书笔记      技术帖      算法      算法导论      c语言      数据结构      龙潭书斋      排序      sort      合并      mergesort     


京ICP备15018585号