Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3624853
  • 博文数量: 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:25

在插入类排序的算法中,有直接插入排序,折半插入排序,希尔排序。
直接插入排序:
程序代码演练:
  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;

  7.     for(= 0; i < N; i++) {
  8.         printf("%d ", a[i]);
  9.     }
  10.     printf("\n");
  11.     
  12.     /*插入排序算法*/
  13.     for(= 1; i < N; i++) {  //控制插入的次数
  14.         tmp = a[i];
  15.         j = i-1;
  16.         while(tmp < a[j]) {   //寻找插入位置;如果改为<=的话,就会是不稳定的排序
  17.             a[j+1] = a[j];
  18.             j = j-1;
  19.         }
  20.         a[j+1] = tmp;
  21.     }

  22.     for(= 0; i < N; i++) {
  23.         printf("%d ", a[i]);
  24.     }
  25.     printf("\n");
  26.     return 0;
  27. }
执行结果:
  1. 62 48 35 77 55 14 35 98 22 10 
  2. 10 14 22 35 35 48 55 62 77 98
折半插入排序:
折半插入排序其实是对直接插入排序的改进,是在寻找插入位置的时候把折半查找的算法加了进来。
程序代码演练:
  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, low, mid, high;

  7.     for(= 0; i < N; i++) {
  8.         printf("%d ", a[i]);
  9.     }
  10.     printf("\n");
  11.      /*折半排序算法*/
  12.     for(= 1; i < N; i++) {
  13.         tmp = a[i];
  14.         low = 0;
  15.         high = i-1;
  16.         while(low <= high) {    //使用折半查找算法进行查找插入位置
  17.             mid = (low+high)/2;
  18.             if(a[mid] > a[i]) {
  19.                 high = mid-1;
  20.             } else {
  21.                 low = mid+1;
  22.             }
  23.         }
  24.         for(j=i; j>low; j--) {
  25.             a[j] = a[j-1];
  26.         }
  27.         a[low] = tmp;
  28.     }

  29.     for(= 0; i < N; i++) {
  30.         printf("%d ", a[i]);
  31.     }
  32.     printf("\n");
  33.     return 0;
  34. }
执行结果:
  1. 62 48 35 77 55 14 35 98 22 10 
  2. 10 14 22 35 35 48 55 62 77 98
希尔排序:
对于这个排序算法,首先要清楚它的实现过程。
演练程序:
  1. #include <stdio.h>

  2. #define N 8

  3. void hillsort(int *a, int delta)
  4. {
  5.     int i, tmp, j;
  6. /*
  7.  *
  8.  *这里没有按照一趟插入排序就把当前子序列排序完毕,而是从第一个子序列的第二个元
  9.  *素开始进行插入排序,顺序遍历完整个待排序记录的序列
  10.  *
  11.  */
  12.     for(i=delta; i<N; i++) {
  13.         if(a[i] < a[i-delta]) {
  14.             tmp = a[i];
  15.             for(j=i; j>=delta && tmp<a[j-delta]; j=j-delta) {
  16.                 a[j] = a[j-delta];
  17.             }
  18.             a[j] = tmp;
  19.         }
  20.     }
  21. }

  22. int main()
  23. {
  24.     int a[N] = {62, 48, 35, 77, 55, 14, 35, 98};
  25.     int i;

  26.     for(i = 0; i < N; i++) {
  27.         printf("%d ", a[i]);
  28.     }
  29.     printf("\n");
  30.     
  31.     /*确定分割距离,每次为上次分隔距离的一半,并且最后一次距离是1,之后结束*/
  32.     for(i=N/2; i>=1; i=i/2) {
  33.         hillsort(a, i);
  34.     }

  35.     for(i = 0; i < N; i++) {
  36.         printf("%d ", a[i]);
  37.     }
  38.     printf("\n");
  39.     return 0;
  40. }
执行结果:
  1. 62 48 35 77 55 14 35 98 100 29
  2. 14 29 35 35 48 55 62 77 98 100




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