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

学习linux

文章分类
文章存档

2014年(7)

2013年(33)

我的朋友

分类: C/C++

2014-03-31 19:22:18

今天没事又看了一遍算法书的排序一章,所以就顺便把书上讲的自己写了一下,当做练习。

程序里包括了四种排序算法,分别是:插入排序,希尔排序,归并排序,快速排序。
主函数想用哪一种,就把函数指针指向那个算法。


点击(此处)折叠或打开

  1. #include <stdio.h>

  2. void insert_sort(int A[],int left,int right);
  3. void shell_sort(int A[],int left,int right);
  4. void merge_sort(int A[],int left,int right);
  5. void quick_sort(int A[],int left,int right);

  6. void out(int A[],int left,int right)
  7. {
  8.     int i;
  9.     for(i=left;i<=right;i++) {
  10.         printf("%d ",A[i]);
  11.     }
  12.     printf("\n");
  13. }

  14. int main(int argc,char *argv[])
  15. {
  16.     void (*sort)(int *,int,int);

  17.     int A[10] = {2,6,8,12,23,19,15,21,6,13};

  18. //    sort = insert_sort;
  19. //    sort = shell_sort;
  20. //    sort = merge_sort;
  21.     sort = quick_sort;

  22.     sort(A,0,9);

  23.     out(A,0,9);
  24.     return 0;
  25. }

  26. //insert_sort
  27. void insert_sort(int A[],int left,int right)
  28. {
  29.     int i,j;
  30.     int tmp;

  31.     for(i=left+1;i<=right;i++) {

  32.         tmp = A[i];

  33.         for(j=i;j>0&&A[j-1]>tmp;j--) {
  34.             A[j] = A[j-1];
  35.         }
  36.         A[j] = tmp;
  37.     }
  38. }

  39. //shell_sort
  40. void shell_sort(int A[],int left,int right)
  41. {
  42.     int i,j,increment;
  43.     int tmp;
  44.     int n = right - left + 1;

  45.     for(increment=n/2;increment>0;increment/=2) {
  46.         for(i=increment;i<n;i++) {
  47.             tmp = A[i];
  48.             for(j=i;j>=increment;j-=increment) {
  49.                 if(tmp<A[j-increment])
  50.                     A[j] = A[j-increment];
  51.                 else
  52.                     break;
  53.             }
  54.             A[j] = tmp;
  55.         }
  56.     }
  57. }

  58. //merge_sort
  59. int A_tmp[10];

  60. void merge(int A[],int left,int center,int right)
  61. {
  62.     int i=left,j=center+1,k=left;

  63.     while(i<=center&&j<=right) {
  64.         if(A[i]<A[j]) {
  65.             A_tmp[k++] = A[i++];
  66.         }
  67.         else {
  68.             A_tmp[k++] = A[j++];
  69.         }
  70.     }

  71.     while(i<=center) {
  72.         A_tmp[k++] = A[i++];
  73.     }
  74.     
  75.     while(j<=right) {
  76.         A_tmp[k++] = A[j++];
  77.     }
  78.     
  79.     for(i=left;i<=right;i++) {
  80.         A[i] = A_tmp[i];
  81.     }        
  82. }

  83. void merge_sort(int A[],int left,int right)
  84. {
  85.     int center;

  86.     if(left<right) {
  87.         center = (left + right)/2;
  88.         merge_sort(A,left,center);
  89.         merge_sort(A,center+1,right);
  90.         merge(A,left,center,right);
  91.     }
  92. }

  93. //quick_sort
  94. #define cutoff    3
  95. void swap(int *a,int *b)
  96. {
  97.     int tmp = *a;
  98.     *a = *b;
  99.     *b = tmp;
  100. }

  101. void quick_sort(int A[],int left,int right)
  102. {
  103.     int i,j,pivot,center;
  104.     
  105.     if(left+cutoff<=right) {
  106.         center = (left+right)/2;
  107.         pivot = A[center];
  108.         swap(&A[center],&A[right]);

  109.         j = left;

  110.         for(i=left;i<=right-1;i++) {
  111.             if(A[i]<=A[right]) {
  112.                 swap(&A[i],&A[j++]);
  113.             }
  114.         }
  115.         swap(&A[j],&A[right]);    
  116.                 
  117.         quick_sort(A,left,j-1);
  118.         quick_sort(A,j+1,right);
  119.     }
  120.     else
  121.         insert_sort(A,left,right);
  122. }


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