现在的位置: 首页 > 综合 > 正文

八大排序算法的实现

2013年08月20日 ⁄ 综合 ⁄ 共 11805字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 来亚嵌一个多月了，感觉进步挺大，但是其他同学进步更是飞速，压力很大，很怕他们马上超过啊，所以这些天一直惶恐的想着提升自己，左想右想，把数据结构拿出来复习来了，看到那些排序，动手实现了一遍，看到几个同学居然也写了几篇关于排序的笔记，拿我就先贴出来和大家一起分享，有些地方我感觉自己实现的效率不高，各位有想法的交流一下~~

我在linux下也的，但是我的系统发不了笔记，所以传到windows下面来发，但是注释全变乱码了，各位将就一下

 1.第一个自然是常用的冒泡，不说了，这个简单

Code:
  1. /*-----------鏀硅繘鍐掓场鎺掑簭-----------------*/  
  2. /*濡傛灉鏌愯稛鏈彂鐢熶氦鎹紝鍒欏彲璁や负鏁版嵁宸茬粡鏈夊簭*/  
  3. #include<stdio.h>   
  4.   
  5. /*-----------鍐掓场鎺掑簭---------------------*/  
  6. void sort(int array[],int n)   
  7. {   
  8.     int i,j,flag,temp;   
  9.     for(i = 0; i < n; i++)   
  10.     {   
  11.         flag = 1;   
  12.   
  13.         for(j = 0; j < n-i-1; j++)   
  14.         {   
  15.             if(array[j] > array[j+1])   
  16.             {   
  17. /*              array[j] ^=  array[j+1];  
  18.                 array[j+1] ^= array[j];  
  19.                 array[j] ^= array[j+1];  
  20. */              temp  = array[j];   
  21.                 array[j] = array[j+1];   
  22.                 array[j+1] = temp;   
  23.                 flag = 0;   
  24.             }   
  25.         }   
  26.            
  27.         if(flag == 1) break;   
  28.         printf("%d ",i);   
  29.     }   
  30.     return;   
  31. }   
  32.   
  33. int main(void)   
  34. {   
  35.     int a[] = {1,34,1,3,312,65,341,423,432,312,6,53,5,323,3,36,46,74,7,47,35,1,45,14,12};   
  36.     int i;   
  37.     sort(a,25);   
  38.     printf("/n");   
  39.     for(i = 0; i < 25;i++)   
  40.         printf("%d ",a[i]);   
  41.     return 0;   
  42. }   

2.也是很简单的，插入排序，不解释

Code:
  1. /*æ?’å…¥æ?’åº?*/ 
  2. #include<stdio.h>   
  3.   
  4. /*数组方å¼?çš„æ?’å…¥æ?’åº?*/  
  5.   
  6. void move(int a[], int i ,int n)   
  7. {   
  8.     for(; n > i; n--)   
  9.         a[n] = a[n-1];   
  10. }   
  11.   
  12. void array_insert(int a[], int n, int item)   
  13. {   
  14.     int i;   
  15.   
  16.     if(item <= a[0])   
  17.     {   
  18.         move(a, 0, n);   
  19.         a[0] = item;   
  20.     }   
  21.     else if(item >= a[n-1])   
  22.     {   
  23.         a[n] = item;   
  24.     }   
  25.     else  
  26.     {   
  27.         for(i = 0; i < n-1; i++)   
  28.         {   
  29.             if(item > a[i] && item <= a[i+1])   
  30.             {   
  31.                 move(a, i+1, n);   
  32.                 a[i+1] = item;   
  33.             }   
  34.         }   
  35.     }   
  36. }   
  37.   
  38. int main(void)   
  39. {   
  40.     int a[]={1,4,5,6,9,2,3,6,8,10};   
  41.     int i;   
  42.   
  43.     for(i = 0; i < 10; i++)   
  44.     {   
  45.         array_insert(a, i, a[i]);   
  46.     }   
  47.   
  48.     for(i = 0; i< 10; i++)   
  49.         printf("%d ", a[i]);   
  50.   
  51.     printf("/n");   
  52.   
  53.     return 0;   
  54. }   

3.还是比较简单的，选择排序

Code:
  1. /*选择æ?’åº?*/ 
  2. #include<stdio.h>   
  3.   
  4. void select(int a[], int n)   
  5. {   
  6.     int i, j, min, k;   
  7.   
  8.     for(i = 0; i < n; i++)   
  9.     {      
  10.         min = 0x7fffffff;   
  11.   
  12.         for(j = i; j < n; j++)   
  13.         {   
  14.             if(a[j] < min)   
  15.             {   
  16.                 min = a[j];   
  17.                 k = j;   
  18.             }   
  19.         }   
  20.            
  21.         a[k] = a[i];   
  22.         a[i] = min;   
  23.     }   
  24.   
  25. }   
  26.   
  27. int main(void)   
  28. {   
  29.     int a[]= {0,34,313,45,123,123,12,23,4};   
  30.     int i;   
  31.   
  32.     select(a, sizeof(a)/sizeof(a[0]));   
  33.        
  34.     for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)   
  35.         printf("%d ",a[i]);   
  36.   
  37.     printf("/n");   
  38.     return 0;   
  39. }   
  40.   

4.快速排序，这个说下，原理就是，用一个数作为分割，大的放左边，小的放右边，这样就分成了两个部分，而且一部分最大的数会比另一部分小，然后递归！

Code:
  1. /*快速æ?’åº?çš„å®?ç?°*/ 
  2. #include<stdio.h>  
  3. #define M 10  
  4. #define SWAP  mid = a[high]; a[high] = a[low]; a[low] = mid   
  5.   
  6. /*一趟æ?’åº?*/  
  7. int partition(int a[], int low, int high)   
  8. {   
  9.     int temp = a[low];   
  10.     int mid;   
  11.   
  12.     while(low < high)   
  13.     {   
  14.         while( (low < high) && (a[high] >= temp) )   
  15.             high--;   
  16.            
  17.         SWAP;   
  18.   
  19.         while( (low < high) && (a[low] <= temp) )   
  20.             low++;   
  21.            
  22.         SWAP;   
  23.     }   
  24.   
  25.     return low;/*è¿”å›?当å‰?的临界å??æ ‡*/  
  26. }   
  27.   
  28. /*递归对数组进行快速æ?’åº?*/  
  29. void quik(int a[],int low, int high)   
  30. {   
  31.     int temp ;   
  32.     if(low < high)   
  33.     {   
  34.         temp = partition(a, low, high);   
  35.   
  36.         quik(a, low, temp - 1);   
  37.         quik(a, temp + 1, high);   
  38.     }   
  39. }   
  40.   
  41. int main(void)   
  42. {   
  43.     int i;   
  44.     int a[]={1,4,6,32,5,3,5,66,341,43,3};   
  45.   
  46.     quik(a, 0, sizeof(a)/sizeof(int) - 1);   
  47.   
  48.     for(i = 0; i < sizeof(a)/sizeof(int); i++)/*sizeof(a)是常数*/  
  49.         printf("%d ",a[i]);   
  50.   
  51.     printf("/n");   
  52.   
  53.     return  0;   
  54. }   

5.希尔排序，就是直接插入排序的改进版，通过增量的方式减少插入数据后数组元素移动的次数以提高效率

Code:
  1. /*希尔æ?’åº?*/ 
  2. #include<stdio.h>   
  3.   
  4. void shell(int a[], int dk,int n)   
  5. {   
  6.     int i, j, temp;   
  7.     for(i = dk; i< n; i++)   
  8.     {   
  9.         if(a[i] < a[i-dk])   
  10.         {   
  11.             temp = a[i];   
  12.   
  13.             for(j = i-dk; j>0 && temp<a[j]; j -= dk)   
  14.                 a[j+dk] = a[j];   
  15.             a[j+dk] = temp;   
  16.         }   
  17.     }   
  18. }   
  19.   
  20. void shellsort(int a[], int n, int dlta[], int t)   
  21. {   
  22.     int i;   
  23.     for(i = 0; i < t; i++)   
  24.         shell(a, dlta[i], n);   
  25. }   
  26.   
  27. int main(void)   
  28. {   
  29.     int a[] = {1,42,42,46,63,33,22,3234,234,5234};   
  30.     int dlta[] = {5,3,1};   
  31.     int i;   
  32.   
  33.     shellsort(a, sizeof(a)/sizeof(a[0]), dlta, sizeof(dlta)/sizeof(dlta[0]));   
  34.   
  35.     for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)   
  36.         printf("%d ", a[i]);   
  37.   
  38.     printf("/n");   
  39.   
  40.     return 0;   
  41. }   
  42.   

6.归并，效率达到理论极限，但是需要额外的空间。原理就是将原本有序的数列两两合并，最后合并成一个数列。时间复杂度是nlogn

Code:
  1. #include<stdio.h>  
  2. #include<malloc.h>   
  3.   
  4. void merge(int a[], int p, int q, int r)   
  5. {   
  6.     int i,j,k = 0;   
  7.     int *buf = (int *)malloc( (r-p+1) * sizeof(int) );   
  8.   
  9.     i = p;   
  10.     j = q+1;   
  11.        
  12.     while((i <= q) && (j <= r))   
  13.     {   
  14.         if(a[i] < a[j])   
  15.             buf[k++] = a[i++];   
  16.         else  
  17.             buf[k++] = a[j++];/*ä»?å°?到大æ?’åº?*/  
  18.   
  19.     }   
  20.   
  21.     if(q+1 == i)/*i==q+1时，q以内无剩余*/  
  22.     {   
  23.         for(j; j <= r; j++)   
  24.             buf[k++] = a[j];   
  25.     }   
  26.     else  
  27.     {   
  28.         for(i; i <= q; i++)   
  29.             buf[k++] = a[i];   
  30.     }   
  31.   
  32.     for(i = p; i <= r; i++)   
  33.         a[i] = buf[i-p];   
  34.     free(buf);   
  35. }   
  36.   
  37. void merge_sort(int a[], int n)   
  38. {   
  39.     int start,end = 1,i;   
  40.   
  41.     while(end < n)   
  42.     {   
  43.         start = end;   
  44.         end  = 2 * start;   
  45.         i = 0;   
  46.   
  47.         while((i + end) < n)   
  48.         {   
  49.             merge(a, i, i+start-1, i+end-1);   
  50.             i += end;   
  51.         }   
  52.   
  53.         if((i + start) < n)/*当i+end>n&&i+start<n时，说æ˜?还有一个è?½å?•çš„没有归并*/  
  54.         {   
  55.             merge(a, i, i+start-1, n-1);   
  56.         }   
  57.     }   
  58. }   
  59.   
  60. int main(void)   
  61. {   
  62.     int i;   
  63.     int a[] = {50,34,41,61,4,2,3,13,3,14,1,4,1};   
  64.     merge_sort(a, 13);   
  65.     for(i = 0; i < 13; i++)   
  66.         printf("%d ",a[i]);   
  67.     printf("/n");   
  68.     return 0;   
  69. }   
  70.   

7.堆排序，以前感觉这个很神秘，但是实现了，其实也就是那么回事，不过确实非常巧妙，时间复杂度是nlogn而且不需要额外空间，堆和归并，应该是大型的排序里首选的算法

Code:
  1. /*----------------å †--------------------------*/  
  2. /*堆为最大堆，既满足k(i)>=k(2i)&&k(i)>=k(zi+1)*/ 
  3. #include<stdio.h>  
  4. #include<malloc.h>  
  5. #include<math.h>  
  6.  
  7. #define M 20/*åˆ?始数组元素个数*/  
  8. #define INC 5/*æ¯?次申请内存å¢?é‡?*/  
  9. #define FALSE 0  
  10. #define TRUE 1   
  11.   
  12. /*-------------交æ?¢æ•°æ?®--------------*/  
  13. void swap(int *a, int *b)   
  14. {   
  15.     int c;   
  16.     c = *a;   
  17.     *a = *b;   
  18.     *b = c;   
  19. }   
  20.   
  21. int * max(int *a, int *b)   
  22. {   
  23.     if(*a > *b)   
  24.         return a;   
  25.     else    
  26.         return b;   
  27. }   
  28.   
  29. /*----------- å †çš„上移æ“?作-----------*/  
  30. /*把h堆中的第i个元素上移             */  
  31. void sift_up(int h[], int i)   
  32. {   
  33.     int done = FALSE;   
  34.        
  35.     if(i > 0)   
  36.     {   
  37.         while(!done && i>0)   
  38.         {   
  39.             if(h[i] > h[i/2])   
  40.                 swap(&h[i],&h[i/2]);   
  41.             else  
  42.                 done = TRUE;   
  43.             i /= 2;   
  44.         }   
  45.     }   
  46. }   
  47.   
  48. /*-----------堆的下移æ“?作------------------*/  
  49. /*把h堆中的第i个元素下移 , n是h中的元素个数*/  
  50. void sift_down(int h[], int n, int i)   
  51. {   
  52.     int done = FALSE, j, *max_i;   
  53.   
  54.     if(i < n)   
  55.     {   
  56.         while(!done && i < n)   
  57.         {   
  58.             j = 2 * i + 1;   
  59.                
  60.             if(j >= n)    
  61.                 break;   
  62.   
  63.             if(j+1 < n)    
  64.                 max_i = max(&h[j],&h[j+1]);   
  65.             else  
  66.                 max_i = &h[j];   
  67.             if(h[i] < *max_i)   
  68.             {   
  69.                 swap(&h[i], max_i);   
  70.             }   
  71.             else  
  72.             {   
  73.                 done = TRUE;   
  74.             }   
  75.   
  76.             i = j;   
  77.         }   
  78.     }   
  79. }   
  80.   
  81. /*---------堆的æ?’å…¥æ“?作---------------------*/  
  82. /*将元素xæ?’入堆中                           */  
  83. void insert(int h[], int *n, int x)   
  84. {   
  85.     (*n)++;   
  86.     h[*n-1] = x;   
  87.     sift_up(h, *n-1);   
  88. }   
  89.   
  90. /*----------堆的删除æ“?作------------------------*/  
  91. /*将堆中元素下标为i的元素删除，但ä¸?ç ´å??堆的结æ?„ */  
  92. void delete(int h[],int *n, int i)   
  93. {   
  94.     int temp = h[i];   
  95.        
  96.     swap(&h[i], &h[*n-1]);   
  97.     (*n)--;   
  98. /*最å??一个元素ä¸?一定是最å°?的数，故è¦?判断是上移还是下移*/     
  99.     if(temp > h[i])   
  100.     {   
  101.         sift_down(h, *n, i);   
  102.     }   
  103.     else  
  104.     {   
  105.         sift_up(h, i);   
  106.     }   
  107. }   
  108.   
  109. void heap_sort(int h[], int n)   
  110. {   
  111.     while(n > 0)   
  112.     {   
  113.         delete(h, &n, 0);   
  114.     }   
  115. }   
  116.   
  117. int main(void)   
  118. {   
  119.     int a[M], n = 0, temp, i;   
  120.     char buf;   
  121.        
  122.     while(buf != '/n')   
  123.     {   
  124.         scanf("%d%c", &temp, &buf);   
  125.         insert(a, &n, temp);   
  126.     }/* åˆ?始化一个堆*/  
  127.   
  128.     for(i = 0; i < n; i++)   
  129.         printf("%d ", a[i]);   
  130.     printf("/n");   
  131.        
  132.     heap_sort(a, n);   
  133. /*  delete(a, &n, 0);*/  
  134.     for(i = 0; i < n; i++)   
  135.         printf("%d ", a[i]);   
  136.     printf("/n");   
  137.     return 0;   
  138. }   

8.基数排序，时间复杂度居然是n。但是使用时一般需要知道最大的元素，这是这些算法里唯一一个基于链表实现的，我感觉我这个基数排序做的不怎么样，效率不高，急待高手改善。

基数排序的原理：

每个数的每位数是0-9，所以我们可以申请10个链表，从个位开始，个位是0的放到L0,1放L1,每个数都放一遍以后作为一趟，将这一趟的结果开始按十位再存放，依次类推，最后可以得到有序的数，假如所有的数都不超过4位，那么循环需要的次数就是4*n，常数去掉，时间复杂度为n,~~~~

Code:
  1. /*---基数æ?’åº?å®?ç?°------*/ 
  2. #include<stdio.h>  
  3. #include<malloc.h>  
  4.  
  5. #define BIT 4   
  6.   
  7. typedef struct List{   
  8.     int data;   
  9.     struct List * next;   
  10. }L;   
  11.   
  12. /*------基数æ?’åº?-----------*/  
  13. /*list éœ€è¦?æ?’åº?的链表头节点*/  
  14. /*k:链表中数的ä½?æ•°         */  
  15. void radix_sort(L *list, int k)   
  16. {   
  17.     L *link[10], *head = list, *lhead[10], *p;   
  18.     int i, pow = 1, bit, flag[10];   
  19.   
  20.     for(i = 0; i < 10; i++)   
  21.      lhead[i] = link[i] = NULL;   
  22.        
  23.     while(k--)   
  24.     {   
  25.         list = head;   
  26.   
  27.         for(i = 0; i < 10; i++)   
  28.             flag[i] = 0;   
  29.   
  30.         while( list != NULL )   
  31.         {   
  32.             bit = (list->data / pow) % 10;   
  33.   
  34.             if(link[bit] != NULL)   
  35.                 link[bit] = link[bit]->next  = /   
  36.                             (L*)malloc(sizeof(L));   
  37.             else  
  38.                 link[bit] = (L*)malloc(sizeof(L));   
  39.             if(flag[bit] == 0)   
  40.             {   
  41.                 lhead[bit] = link[bit];   
  42.                 flag[bit] = 1;   
  43.             }   /*第1次分é…?地å?€æ—¶è®°å½•é¦–地å?€*/  
  44.   
  45.             link[bit]->data = list->data;   
  46.             link[bit]->next = NULL;   
  47.   
  48.             list = list->next;   
  49.         }   
  50.   
  51.         for(i = 0; i < 10; i++)   
  52.             link[i] = lhead[i];/*10个链表指å›?头结点*/  
  53.   
  54.         list = head;   
  55.   
  56.         for(i = 0; i< 10; i++)   
  57.         {   
  58.             while(link[i] != NULL)   
  59.             {   
  60.                 list->data = link[i]->data;   
  61.                 link[i] = link[i]->next;   
  62.                 list = list->next;   
  63.             }   
  64.         }   
  65.   
  66.         for(i = 0; i < 10; i++)   
  67.         {   
  68.             while(lhead[i] != NULL)   
  69.             {   
  70.                 p = lhead[i];   
  71.                 lhead[i] = lhead[i] ->next;   
  72.                 free(p);   
  73.             }   
  74.         }   
  75.         pow *= 10;   
  76.     }   
  77.   
  78.     list = head;   
  79.     for(i = 0; i< 10; i++)   
  80.     {   
  81.         while(lhead[i] != NULL)   
  82.         {   
  83.             list->data = lhead[i]->data;   
  84.             lhead[i] = lhead[i]->next;   
  85.             list = list->next;   
  86.         }   
  87.     }   
  88. }   
  89.   
  90. int main(void)   
  91. {   
  92.     L *list, *p, *head;   
  93.     char buf;   
  94.        
  95.     head = list = NULL;   
  96.   
  97.     while(buf != '/n')   
  98.     {   
  99.         p =(L *)malloc(sizeof(L));   
  100.            
  101.         if(list == NULL)       
  102.         {   
  103.             head = list = p;   
  104.             list->next = NULL;   
  105.         }   
  106.   
  107.         else  
  108.         {   
  109.             list->next = p;   
  110.             list = list->next;   
  111.             list->next = NULL;   
  112.         }   
  113.         scanf("%d%c", &list->data, &buf);   
  114.     }   
  115.        
  116.     radix_sort(head, BIT);   
  117.   
  118.     while(head != NULL)   
  119.     {   
  120.         printf("%d ", head->data);   
  121.         head = head->next;   
  122.     }   
  123.   
  124.     printf("/n");   
  125.   
  126.     return 0;   
  127. }   

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞