注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HongMain 的博客

关注编程技术: Linux, Windows, C/C++

 
 
 

日志

 
 
 
 

一些排序函数模板(C++)  

2011-08-05 23:04:44|  分类: 编程语言(主要是 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

// 一些排序函数模板


#include <iostream>
using namespace System;

// 排序算法 函数模板

// 直接插入排序函数模板
template <class T>
void InsertionSort(T A[], int n)
{  int i, j;
   T   temp;
   for (i = 1; i < n; i++)
   {  j = i;
      temp = A[i];
      while (j > 0 && temp < A[j-1])
      {  A[j] = A[j-1];   
         j--;
      }
     A[j] = temp;
   }
}

// 交换位置函数模板
template <class T>
void Swap (T &x, T &y)
{
 T temp;
 temp = x;
 x = y;
 y = temp;
}


// 直接选择排序函数模板
template <class T>
void SelectionSort(T A[], int n)
{  int smallIndex;   
   int i, j;
   for (i = 0; i < n-1; i++)
   {  smallIndex = i;   
      for (j = i+1; j < n; j++)
         if (A[j] < A[smallIndex])
            smallIndex = j;
      Swap(A[i], A[smallIndex]);
   }
}

// 交换排序方法——起泡排序
template <class T>
void BubbleSort(T A[], int n)

 int i,j;            
 int lastExchangeIndex;
 i = n-1;     
 while (i > 0)
 { 
  lastExchangeIndex = 0; 
  for (j = 0; j < i; j++)
  {
   if (A[j+1] < A[j])
   {
    Swap(A[j],A[j+1]);
    lastExchangeIndex = j;    
   }
  }
  i = lastExchangeIndex;
 }
}

// 比较函数指针
// 返回值
//     负值: 第一个参数小于第二个参数
//    0   : 相等
//    正值: 第一个参数大于第二个参数
typedef int (*CFT)(const void*, const void*);

// **************************************
// 对向量base的n个元素按照递增顺序排序
// 用由cmp所指的函数做比较
// 元素的大小是sz
// Shell排序
// **************************************
void ssort(void* base, size_t n, size_t sz, CFT cmp)
{
 for (int gap=n/2; 0<gap; gap/=2)
 {
  for (int i=gap; i<n; i++)
  {
   for (int j=i-gap; 0<=j; j-=gap)
   {
    char* b = static_cast<char*>(base);  // 必须强制
    char* pj = b+j*sz;      // &base[j]
    char* pjg = b+(j+gap)*sz;    // &base[j+gap]
    if (cmp(pjg, pj) < 0)
    {
     // 交换base[j]与base[j+gap]
     for (int k=0; k<sz; k++)
     {
      char temp = pj[k];
      pj[k] = pjg[k];
      pjg[k] = temp;
     }
    }
   }
  }
 }
}

// 比较函数
int compare_int(const void* arg1, const void* arg2)
{
 if (*(int*)arg1 < *(int*)arg2) return -1;
 if (*(int*)arg1 == *(int*)arg2) return 0;
 if (*(int*)arg1 > *(int*)arg2) return 1;
}

void main()
{
 const int MAXSIZE = 20;
 int* iA = new int[MAXSIZE];
 Random* random = new Random;
 for (int i=0; i<MAXSIZE; i++)
 {
  iA[i] = random->Next(100);
 }
 //InsertionSort(iA, 8);
 ssort(iA, MAXSIZE, sizeof(int), compare_int);
 for (int i=0; i<MAXSIZE; i++)
 {
  std::cout<< iA[i] << " ";
 }


 int x;
 std::cin>>x;

}

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017