Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3624838
  • 博文数量: 880
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 6155
  • 用 户 组: 普通用户
  • 注册时间: 2016-11-11 09:12
个人简介

To be a better coder

文章分类

全部博文(880)

文章存档

2022年(5)

2021年(60)

2020年(175)

2019年(207)

2018年(210)

2017年(142)

2016年(81)

分类: C/C++

2016-11-11 09:19:20

在交换类排序算法中,有冒泡排序和快速排序。
冒泡排序:
这个算法大家估计很熟悉了,不做介绍了。
这里有一个算法优化的地方,那就是设置标志位,如果在上一趟的比较当中,没有进行交换的话,就说明已经排好序了,不需要再进行排序了。
演练程序:
  1. #include <stdio.h>

  2. #define N 10

  3. int main()
  4. {
  5.     int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
  6.     int tmp, i, j, flag;

  7.     for(i = 0; i < N; i++) {
  8.         printf("%d ", a[i]);
  9.     }
  10.     printf("\n");

  11.     flag = 1;
  12.     /*控制比较的趟数,总共比较N-1趟*/
  13.     for(i=0; i < N-1 && flag==1; i++) {
  14.         flag = 0;
  15.         /*相邻的两个元素进行比较,把泡泡冒到最底*/
  16.         for(j=0; j < N-i-1; j++) {
  17.             if(a[j] > a[j+1]) {
  18.                 tmp = a[j+1];
  19.                 a[j+1] = a[j];
  20.                 a[j] = tmp;
  21.                 flag = 1;
  22.             }
  23.         }
  24.     }

  25.     for(i = 0; i < N; i++) {
  26.         printf("%d ", a[i]);
  27.     }
  28.     printf("\n");
  29.     return 0;
  30. }
执行结果:
  1. 62 48 35 77 55 14 35 98 22 10
  2. 10 14 22 35 35 48 55 62 77 98
快速排序:
对于快速排序,一般是这么来设计的:首先保存第一个元素到一个变量x中,让它当作一个枢纽值,然后设置low和high下标分别指向最低处和最高处,总之,在一趟排序之后,x所放的位置要保证x前面的元素比x都小,x之后的元素都比x大就行了。
演练程序:
  1. #include <stdio.h>

  2. #define N 10

  3. int sort(int *a, int low, int high)
  4. {
  5.     int pos, x;

  6.     x = a[low];
  7.     while(low < high) {
  8.         while(low<high && a[high] >= x) {
  9.             high--;
  10.         }
  11.         if(low < high) {
  12.             a[low] = a[high];
  13.             low++;
  14.         }
  15.         while(low<high && a[low] <= x) {
  16.             low++;
  17.         }
  18.         if(low < high) {
  19.             a[high] = a[low];
  20.             high--;
  21.         }
  22.     }
  23.     a[low] = x;
  24.     pos = low;
  25.     return pos;
  26. }

  27. void quicksort(int *a, int low, int high)
  28. {
  29.     int pos;

  30.     if(low < high) {
  31.         pos = sort(a, low, high);
  32.         quicksort(a, low, pos-1);
  33.         quicksort(a, pos+1, high);
  34.     }
  35. }

  36. int main()
  37. {
  38.     int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
  39.     int i, j;

  40.     for(i = 0; i < N; i++) {
  41.         printf("%d ", a[i]);
  42.     }
  43.     printf("\n");

  44.     quicksort(a, 0, N-1);

  45.     for(i = 0; i < N; i++) {
  46.         printf("%d ", a[i]);
  47.     }
  48.     printf("\n");
  49.     return 0;
  50. }
执行结果:
  1. 62 48 35 77 55 14 35 98 22 10
  2. 10 14 22 35 35 48 55 62 77 98




阅读(850) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~