#include <stdlib.h> #include <stdio.h> //插入排序 void main() { int a[]={0,2,3,7,5,2,9,3,1,98,29}; int t; for(int i=1;i<sizeof(a)/sizeof(*a);i++) { //将赋值移除内循环进行加速 t = a[i]; int j; //从右向左检查元素是否有序, //如果具有前驱且元素小于前驱就交换位子 for(j=i; j>0 && a[j-1] > t; j--) { a[j] = a[j-1]; } //在进行了交换之后j的值发生变化等于其前驱, //如果没有交换,j没有变化,就是i的值 a[j] = t; } for(int i=0;i<sizeof(a)/sizeof(*a);i++) { printf("%d ", a[i]); } printf("\n"); }
对动态分配内存的插入排序
#include <stdlib.h> #include <stdio.h> #include <time.h> #define MAX 10000 //插入排序 void main() { int *a, rand_num; a = (int*)malloc((size_t)(MAX*sizeof(int))); if (a == NULL) { printf("%s", "Memory alloc error"); exit(EXIT_FAILURE); } printf("%ld\n", sizeof(a)); srand(time(0)); for(int i=0;i<MAX;i++) { rand_num = rand()/MAX; a[i] = rand_num; } int t; for(int i=1;i<MAX;i++) { //将赋值移除内循环进行加速 t = a[i]; int j; //从右向左检查元素是否有序, //如果具有前驱且元素小于前驱就交换位子 for(j=i; j>0 && a[j-1] > t; j--) { a[j] = a[j-1]; } //在进行了交换之后j的值发生变化等于其前驱, //如果没有交换,j没有变化,就是i的值 a[j] = t; } for(int i=0;i<MAX;i++) { printf("%d\n ", a[i]); } printf("\n"); free(a); }
使用插入排序和快速排序的速度比较
10000个整数的数组,使用linux系统time命令
real 0m0.291s
user 0m0.140s
sys 0m0.044s
使用qsort进行快速排序
real 0m0.153s
user 0m0.004s
sys 0m0.032s