插入和归并排序

算法导论：主要关注的是程序的性能；速度令人渴望！！！

排序算法是经典算法

1、插入排序

  (1)、算法模型

  (2)、代码实现

#include<stdio.h> void insertSort(int *a, int count); void showArray(int *a, int count); void showArray(int *a, int count){     int i;          for(i = 0; i < count; i++){         printf("%d ", a[i]);     }     printf("\n");  } void insertSort(int *a, int count){     int i;     int j;     int n;     int tmp;     for(i = 1; i < count; i++){         tmp = a[i];         for(j = 0; a[i]>a[j] && j<i; j++){             ;         }         if(i != j){             for(n = i; n > j; n--){                 a[n] = a[n-1];             }             a[j] = tmp;         }     } } void main(void){     int a[] = {2, 5, 7, 1, 11, 0, 6, 9};     int count = sizeof(a)/sizeof(int);     printf("排序前输出如下: ");     showArray(a, count);     insertSort(a, count);     printf("排序后输出如下: ");     showArray(a, count); }

  (3)、结果截图

  (4)、算法分析

插入排序最坏的情况：数组中所有元素全部逆序排列；

时间复杂度：O(n^2);

2、归并排序

  (1)、算法思想：

  i、if n = 1; done

  ii、递归排序，分2部分，在[0, n/2]和[n/2, n]

  iii、将2部分归并排序

  (2)、核心代码实现

#include<stdio.h> #include<malloc.h> void mergerSort(int *a1, int *a2, int **a3, int count1, int count2, int *count3); void showArray(int *a3, int count); void showArray(int *a3, int count){     int i;     for(i = 0; i < count; i++){         printf("%d ", a3[i]);     }     printf("\n"); } void mergerSort(int *a1, int *a2, int **a3, int count1, int count2, int *count3){     int count;     int i = 0;     int j = 0;     int n = 0;     count = *count3 = count1 + count2;     *a3 = (int *)malloc(sizeof(int) * count);     //以下的都是<，因为传过来的是数组长度；     while(i < count1 && j < count2){         if(a1[i] < a2[j]){             (*a3)[n++] = a1[i];             i++;         }else if(a1[i] == a2[j]){             (*a3)[n++] = a1[i];             (*a3)[n++] = a2[j];             i++;             j++;         }else{       //刚才写程序else(a1[i] > a2[j]),后发现else语句后面是没有条件的!!!             (*a3)[n++] = a2[j];             j++;         }     }     while(i < count1){         (*a3)[n++] = a1[i];         i++;     }     while(j < count2){         (*a3)[n++] = a2[j];         j++;     } } /*  归并排序核心算法就是：将已经排好序的2个数组进行最终的排序过程； */ void main(void){     int a1[] = {1, 3, 5, 7};     int a2[] = {0, 2, 4, 6, 8, 9, 10};     int count1 = sizeof(a1)/sizeof(int);     int count2 = sizeof(a2)/sizeof(int);     int *a3 = NULL;     int count3 = 0;     mergerSort(a1, a2, &a3, count1, count2, &count3);     showArray(a3, count3);     free(a3); }

  (3)、结果截图

  (4)、完整代码实现

#include<stdio.h> #include<malloc.h> void mergeSort(int *a, int low, int high); void merge(int *a, int low, int mid, int high); void merge(int *a, int low, int mid, int high){     int i = low;     int j = mid+1;     int n = 0;     int *a2;     a2 = (int *)malloc(sizeof(int) * (high-low+1));     if(a2 == NULL){         return;     }     //以下都是<=,因为传过来的都是下标；     while(i <= mid && j <= high){         if(a[i] < a[j]){             a2[n++] = a[i];             i++;         }else if(a[i] == a[j]){             a2[n++] = a[i];             i++;             j++;         }else{             a2[n++] = a[j];             j++;         }     }     while(i <= mid){         a2[n++] = a[i];         i++;     }     while(j <= high){         a2[n++] = a[j];         j++;     }     for(n = 0, i = low; i <= high; n++, i++){  //将a2中的元素复制回a中;         a[i] = a2[n];     }     free(a2); } void mergeSort(int *a, int low, int high){     int mid;     if(low < high){         mid = (low + high) / 2;         mergeSort(a, low, mid);         mergeSort(a, mid+1, high);         merge(a, low, mid, high);     } } void main(void){     int a[] = {2, 4, 1, 7, 5, 6, 9, 10};     int count = sizeof(a)/sizeof(int);     int i;     mergeSort(a, 0, count-1);     for(i = 0; i < count; i++){         printf("%d ", a[i]);     }     printf("\n"); }

(5)、结果截图

(6)、算法分析

归并排序的时间复杂度:树高度log(n)，一共要对n个元素进行排序，所以为：O(nlogn);

在30个元素以内，插入排序性能更好，超过30个元素之后归并排序的性能更加优秀；