今天接到电话面试的时候提到了一个归并排序,之前用的比较少,于是完了之后参照 http://blog.csdn.net/morewindo… 写了一个归并排序
#include <stdio.h> #include <stdlib.h> void merge(int n[], int first, int mid, int last, int temp[]) { int i=first, j=mid+1, k=0; while (i<=mid && j<=last) { if (n[i] < n[j]) { temp[k++] = n[i++]; } else { temp[k++] = n[j++]; } } while (i <= mid) { temp[k++] = n[i++]; } while (j <= last) { temp[k++] = n[j++]; } for (i=0; i<k; i++) { n[first+i] = temp[i]; } } void m_sort(int n[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; m_sort(n, first, mid, temp); m_sort(n, mid+1, last, temp); merge(n, first, mid, last, temp); } } int main() { int k; scanf("%d", &k); int *n = (int *)malloc(k*sizeof(int)); int *temp = (int *)malloc(k*sizeof(int)); if (!n || !temp) { exit(1); } int i; for (i=0; i<k; i++) { scanf("%d", &n[i]); } m_sort(n, 0, k-1, temp); for (i=0; i<k; i++) { printf("%d ", n[i]); } printf("n"); free(n); free(temp); }
输入输出:
5 3 1 2 4 0 0 1 2 3 4
归并排序的时间复杂度是 O(n*log(n)),数据是稳定的