Chinaunix首页 | 论坛 | 博客
  • 博客访问: 550400
  • 博文数量: 66
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1810
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-23 13:53
个人简介

linux

文章分类

全部博文(66)

文章存档

2016年(1)

2015年(14)

2014年(32)

2013年(19)

分类: C/C++

2014-11-16 15:41:06

1.起泡排序
起泡排序的原理非常的简单,它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
算法描述
    1.比较相邻的元素。如果第一个比第二个大,就交换他们两个;
    2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的元素;
    3.针对所有元素重复以上的步骤,除了最后一个;
    4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较;
算法演示:
  1. /*
  2. **起泡排序 时间复杂度O(n^2)
  3. */
  4. void BubbleSort(int a[], int len)
  5. {
  6.     int i, j;
  7.     for(i = 0; i < len; ++i){
  8.         for(j = i+1; j < len; ++j){
  9.             if(a[i] > a[j]){
  10.                 int temp = a[i];
  11.                 a[i] = a[j];
  12.                 a[j] = temp;
  13.             }
  14.         }
  15.     }
  16. }
2.快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法描述:
    1.从数列中挑出一个元素(通常第一个元素)作为基准数;
    2.分区过程,将比基准数大的放到右边,小于或等于它的数放到左边;
    3.在对左右区间递归执行第二步,直至各区间只有一个数
动画演示:


算法演示:
  1. /*
  2. **快速排序实现
  3. */
  4. int Partition(int a[], int low, int high)
  5. {
  6.     int pivotkey = a[low];
  7.     while(low<high){
  8.         if(low<high && a[high]>=pivotkey)
  9.             --high;
  10.         a[low] = a[high];
  11.         if(low<high && a[low]<=pivotkey)
  12.             ++low;
  13.         a[high] = a[low];
  14.     }
  15.     a[low] = pivotkey;
  16.     return low;
  17. }

  18. void QSort(int a[], int low, int high)
  19. {
  20.     if(low < high){
  21.         int position = Partition(a, low, high);
  22.         QSort(a, low, position-1);
  23.         QSort(a, position+1, high);
  24.     }
  25. }
3.example code:

  1. int main()
  2. {
  3.     int i;
  4.     int a[] = {80, 93, 60, 12, 42, 30, 68, 85, 10};

  5.     printf("起泡排序:\n");
  6.     BubbleSort(a, sizeof(a)/sizeof(a[0]));
  7.     for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
  8.         printf("%d ", a[i]);
  9.     printf("\n");

  10.     printf("快速排序:\n");
  11.     QSort(a, 0, sizeof(a)/sizeof(a[0]));
  12.     for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
  13.         printf("%d ", a[i]);
  14.     printf("\n");

  15.     return 0;
  16. }
4.下面为七种经典排序算法指标对比情况:
阅读(1953) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~