elva

C 语言常用的排序算法

转自：http://blog.csdn.net/chenqiang35/archive/2009/02/19/3909699.aspx

view plaincopy to clipboardprint?
  1. /******************************************************************************************** 
  2.                                 平方阶(O(n2))排序 
  3.                 一般称为简单排序，例如直接插入、直接选择和冒泡排序 
  4.      
  5.  ********************************************************************************************/  
  6.   
  7. /*插入排序*/  
  8. extern int InsertSort(int source[], int array_size)  
  9. {  
  10.     int index = 1; //插入排序  
  11.     int i, j;  
  12.     for (i = 1; i < array_size; i++)  
  13.     {  
  14.         index = source[i];  
  15.         j = i;  
  16.         while ((j > 0) && (source[j - 1] > index))  
  17.         {  
  18.             source[j] = source[j - 1];  
  19.             j--;  
  20.         }  
  21.         source[j] = index;  
  22.     }  
  23.     return 1;  
  24. }  
  25.   
  26. /*冒泡排序*/  
  27. extern int BubbleSort(int source[], int array_size)  
  28. {  
  29.     int i, j;  
  30.     int temp;  
  31.     for (i = 0; i < array_size; i++)  
  32.     {  
  33.         for (j = 0; j < array_size - i - 1; j++)  
  34.             if (source[j] > source[j + 1])  
  35.             {  
  36.                 temp = source[j];  
  37.                 source[j] = source[j + 1];  
  38.                 source[j + 1] = temp;  
  39.             }  
  40.     }  
  41.     return 1;  
  42. }  
  43.   
  44. /*选择排序*/  
  45. extern int SelectSort(int source[], int array_size)  
  46. {  
  47.     int temp, min;  
  48.     int i, j;  
  49.     for (i = 0; i < array_size; i++)  
  50.     {  
  51.         min = i;//先假设最小下标为i  
  52.         for (j = i + 1; j < array_size; j++)  
  53.             if (source[j] < source[min])  
  54.                 min = j;//把i之后的最小值附给min  
  55.             if (min != i)  
  56.             {  
  57.                 temp = source[i];  
  58.                 source[i] = source[min];  
  59.                 source[min] = temp;  
  60.             }//判断min与i是否相等,若相等则说明原假设正确,反之:交换数值  
  61.     }  
  62.     return 1;  
  63. }  

 

view plaincopy to clipboardprint?
  1. /*********************************************************************************************   
  2.                                 线性对数阶(O(nlgn))排序 
  3.                             如快速、堆和归并排序 
  4.      
  5.  ********************************************************************************************/  
  6.   
  7. /*快速排序接口*/  
  8. static int Partition(int source[], int left, int right)  
  9. {  
  10.     int x = source[left];  
  11.     while (left < right)  
  12.     {  
  13.         while (left < right && x <= source[right])  
  14.             right--;  
  15.         source[left] = source[right];  
  16.         while (left < right && x >= source[left])  
  17.             left++;  
  18.         source[right] = source[left];  
  19.     }  
  20.     source[left] = x;  
  21.     return left;  
  22. }  
  23.   
  24. extern int QuickSort(int source[], int left, int right)  
  25. {  
  26.     int iPos;  
  27.     if (left >= right)  
  28.         return 1;  
  29.     iPos = Partition(source, left, right);  
  30.     QuickSort(source, left, iPos - 1); //   左边划分  
  31.     QuickSort(source, iPos + 1, right); //   右边划分  
  32.     return 1;  
  33. }  
  34.   
  35.   
  36. /*堆排序*/  
  37. static void HeapAdjust(int source[], int root, int node)/*root根节点, node节点总数*/  
  38. {  
  39.     //已知source[root..node]中除source[root]之外均满足堆的定义,本函数调整source[root]  
  40.     //使source[root..node]成为一个大顶堆  
  41.     int j, rc;  
  42.     rc = source[root];  
  43.     for (j = 2 * root; j <= node; j *= 2) //沿关键字叫大的结点向下筛选  
  44.     {  
  45.         if (j < node && source[j] < source[j + 1])  
  46.             ++j; //j为关键字较大的记录的下标  
  47.         if (rc >= source[j])  
  48.             break; //rc应插入在位置root上  
  49.         source[root] = source[j];  
  50.         root = j;  
  51.     }  
  52.     source[root] = rc; //插入  
  53. }  
  54. extern int HeapSort(int source[], int array_size)  
  55. {  
  56.     int i, t;  
  57.     for (i = array_size / 2; i > 0; --i)  
  58.         //把a[1..L.length]建成大顶堆  
  59.         HeapAdjust(source, i, array_size);  
  60.     for (i = array_size; i > 1; --i)  
  61.     {  
  62.         t = source[1]; //将堆顶记录和当前未经排序子序列a[1..i]  
  63.         source[1] = source[i]; //中的最后一个记录相互交换  
  64.         source[i] = t;  
  65.         HeapAdjust(source, 1, i - 1); //将r[1..i-1]重新调整为大顶堆  
  66.     }  
  67.     return 1;  
  68. }  

 

view plaincopy to clipboardprint?
  1. /********************************************************************************************** 
  2.                                     O(n1+￡)阶排序 
  3.                         ￡是介于0和1之间的常数，即0<￡<1，如希尔排序 
  4.  
  5.  ********************************************************************************************/  
  6.   
  7. /*希儿排序*/  
  8. extern int ShellSort(int source[], int array_size)  
  9. {  
  10.     int increament;  
  11.     int e, i, j;  
  12.       
  13.     /*初始步长设为n/2*/  
  14.     for (increament = array_size / 2; increament > 0; increament = increament / 2)  
  15.         for (j = increament; j < array_size; j++)  
  16.         {  
  17.             if (source[j] < source[j - increament])  
  18.             {  
  19.                 e = source[j];  
  20.                 for (i = j - increament; i >= 0 && source[i] > e; i = i - increament)  
  21.                     source[i + increament] = source[i];  
  22.                 source[i + increament] = e;  
  23.                   
  24.             }  
  25.         }  
  26.         return 1;  
  27. }  

 

posted on 2009-10-26 18:05 叶子 阅读(440) 评论(0)  编辑 收藏 引用 所属分类: C\C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理