掌握好常用的排序算法，在实际的项目开发中可以节省很多的时间。每一种排序算法在执行的效率上是存在差别的，这些微小的时间差，也许在平常的联系当中感觉不到，但是涉及到数据量比较大或者是在资源比较紧张的系统中就显得尤其的重要，比如嵌入式系统。下面简要介绍三种常用的排序算法以及他们的执行效率的比较。
冒泡排序：
思路：将相邻的两个数比较，将较小的数调到前头；有n个数就要进行n-1趟比较，第一次比较中要进行n-1次两两比较，在第j趟比较中，要进行n-j次两两比较。
实现代码：
- void BublleSort (int arr [], int count)
- {
- int i, j, temp;
- for(j=0; j<count-1; j ) /* 冒泡法要排序n-1次*/
- for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
- {
- if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
- {
- temp=arr[i 1];
- arr[i 1]=arr[i];
- arr[i]=temp;
- }
- }
- }
插入排序：
思路：在得到要排序的数组以后，讲数组分为两个部分，数组的第一个元素为一个部分，剩下的元素为一部分，然后从数组的第二个元素开始，和该元素以前的所有元素比较，如果之前的元素没有比该元素大的，那么该元素的位置不变，如果有元素的值比该元素大，那么记录相爱他所在的位置；例如I，该元素的位置为k，则将从i到k位置上的所有元素往后移动一位，然后将k位置上的值移动到i位置上。这样就找到了K所在的位置。每一个元素都这样进行，最终就会得到排好顺序的数组。
实现代码：
- void InsertSort ( int arr[],int count)
- {
- int i,j,temp;
- for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
- {
- temp = arr[i];//操作当前元素，先保存在其它变量中
- for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
- {
- arr[i] = arr[j];
- arr[j] = temp;
- }
- }
- }
选择排序：
思路：
首先以一个元素为基准，从一个方向开始扫描，比如从左到右扫描，以A[0]为基准，接下来从A[0]….A[9]中找出最小的元素，将其与A[0]交换。然后将其基准位置右移一位，重复上面的动作，比如，以A[1]为基准，找出A[1]~A[9]中最小的，将其与A[1]交换。一直进行到将基准位置移到数组最后一个元素时排序结束。
实现代码：
- void SelectSort(int arr[], int count)
- {
- int i,j,min,temp;
- for(i=0; i<count; i )
- {
- min = arr[i];//以此元素为基准
- for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
- {
- if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
- {
- temp = arr[j];
- arr[j] = min;
- min = temp;
- }
- }
- }
- }
效率比较：
为了能够更加明显的查看其效果，将每个排序算法执行10000次。下面是测试程序主函数：
- #include <stdio.h>
- #include<stdlib.h>
- #include <sys/time.h>
- #include <unistd.h>
- #define MAX 6
- int array[MAX];
- int count = MAX;
- /********创建数组，并输入元素************/
- void BuildArray()
- {
- int a,i=0;
- printf("请输入数组元素: ");
- for(; i<count; i )
- {
- scanf("%d", &a);
- array[i] = a;
- }
- printf("\n");
- }
- /**********遍历输出数组元素*************/
- void Traverse(int arr[], int count)
- {
- int i;
- printf("数组输出: ");
- for(i=0; i<count; i )
- printf("%d\t", arr[i]);
- printf("\n");
- }
- void BublleSort(int arr[], int count)
- {
- int i,j,temp;
- for(j=0; j<count-1; j ) /* 气泡法要排序n-1次*/
- for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
- {
- if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
- {
- temp=arr[i 1];
- arr[i 1]=arr[i];
- arr[i]=temp;
- }
- }
- }
- void InsertSort(int arr[],int count)
- {
- int i,j,temp;
- for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
- {
- temp = arr[i];//操作当前元素，先保存在其它变量中
- for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
- {
- arr[i] = arr[j];
- arr[j] = temp;
- }
- }
- }
- void SelectSort(int arr[], int count)
- {
- int i,j,min,temp;
- for(i=0; i<count; i )
- {
- min = arr[i];//以此元素为基准
- for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
- {
- if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中
- {
- temp = arr[j];
- arr[j] = min;
- min = temp;
- }
- }
- }
- }
- int main()
- {
- int i;
- struct timeval tv1,tv2;
- struct timezone tz;
- BuildArray();//创建数组
- Traverse(array, count);//输出最初数组
- gettimeofday(&tv1,&tz);
- for(i=0;i<10000;i++)
- BublleSort(array, count);//冒泡排序
- gettimeofday(&tv2,&tz);
- printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
- Traverse(array, count);//输出排序后的数组
-
- gettimeofday(&tv1,&tz);
- for(i=0;i<10000;i++)
- InsertSort(array, count);//插入排序
- gettimeofday(&tv2,&tz);
- printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
- Traverse(array, count);//输出排序后的数组
-
- gettimeofday(&tv1,&tz);
- for(i=0;i<10000;i++)
- SelectSort(array, count);//插入排序
- gettimeofday (&tv2,&tz);
- printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
- Traverse(array, count);//输出排序后的数组
- return 0;
- }
编译：gcc –g –Wall sort_test.c –o sort_test
运行：./sort_test
结果如下：
通过多次测试，插入排序的速度最快。
阅读(872) | 评论(0) | 转发(0) |
