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

伯纳乌の夢

可以挽回么?我们按“ Ctrl+Z”撤销掉吧。对不起啦~~

 
 
 

日志

 
 
 
 

几种排序算法的源代码  

2008-11-25 21:31:48|  分类: 数据结构与算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

冒泡排序:

void CSortDlg::bubble_sort(int x[]){

//对数组x[]逐趟进行比较 ,遇到逆序即交换

int i =1;int exchange=1;      //exchange0时,则停止排序

while((i<10 )&&exchange){//

BubbleExchange( x, i, exchange);

i++;

}

}

void CSortDlg::BubbleExchange(int x[],int i,int exchange){

exchange = 0;  //假定元素未交换

for(int j =9;j>=i;j--){

if(x[j-1]>x[j])   //发生了逆序

{

int temp = x[j-1];   //交换

x[j-1]=x[j];

x[j] = temp;

exchange = 1;  //做“发生了交换”的标志

}

}

}


直接插入排序:

void CSortDlg::InsertionSort(int x[])

{

for(int i=1;i<10;i++)

{

Insert(x,i);

}

}


void CSortDlg::Insert(int x[],int i)

{

int temp=x[i]; int j=i;

while (j>0&&temp<x[j-1])

{

x[j]=x[j-1];

j--;

}

x[j]=temp;

}


希尔排序:

void CSortDlg::Shellsort(int x[])

{

int gap=10/2;  //增量的初始值

while (gap)  //循环条件是gap>=1

{

ShellInsert(x,gap);  //按增量gap划分子序列,分别进行插入排序

gap=gap==2?1:(int)(gap/2);  //缩小增量gap

}

}


void CSortDlg::ShellInsert(int x[],const int gap)

{

for(int i=gap;i<10;i++)  //各子序列轮流执行插入排序

{

int temp=x[i];int j=i;  //暂存待插入对象

while (j>=gap&&temp<x[j-gap]) {  //当前插入元素比位于j-gap的元素小,则位于j-gap的元素后移

x[j]=x[j-gap];

j-=gap;  //后移到第j个位置,j指标前指

}

x[j]=temp;  //插入

}

}


归并排序:

void CSortDlg::MergeSort(int x[])

{

int temp_array[10];

int len=1;

while (len<10) {    //归并排序

MergePass(x,temp_array,len);  //一趟两路归并后归并项长度加倍

len*=2;

MergePass(temp_array,x,len);

len*=2;

}

// delete[] temp_array;

}


void CSortDlg::MergePass(int init_array[],int merge_array[],const int len)

{   //一趟归并排序

int i=0;

while (i+2*len<=9) {  //对长度为len的子表两两归并,直到表中剩余元素个数不足2*len为止

merge(init_array,merge_array,i,i+len-1,i+2*len-1);

i+=2*len;

}

if (i+len<=9)

merge(init_array,merge_array,i,i+len-1,9);

else

for (int j=i;j<=9;j++) {  //若不能做归并,就复制

merge_array[j]=init_array[j];

}

}


void CSortDlg::merge(int init_array[],int merge_array[],const int l,const int m,const int n)

{

int i=l,j=m+1,k=l;

while (i<=m&&j<=n)

if (init_array[i]<=init_array[j]) {

merge_array[k]=init_array[i];

i++;k++;

}

else

{

merge_array[k]=init_array[j];

j++;k++;

}


if (i<=m)

for (int n1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) {

merge_array[n1]=init_array[n2];

}

else

for (int n1=k, n2=j;n1<=n&&n2<=n;n1++,n2++) {

merge_array[n1]= init_array[n2];

}

}


折半插入排序:

void CSortDlg::BinaryInsertSort(int x[])

{

for (int i=1;i<10;i++)

{

BinaryInsert(x,i);

}

}


void CSortDlg::BinaryInsert(int x[],int i)

{

int left=0,right=i-1;

int temp=x[i];

while (left<=right)   //利用折半查找找插入位置

{

int middle=(left+right)/2;  //取中点

if (temp<x[middle])   //插入值小于中点值

{

right=middle-1;  //向左缩小区间

}

else   //否则向右缩小区间

left=middle+1;

}

for (int k=i-1;k>=left;k--)  //成块移动,空出插入位置

{

x[k+1]=x[k];

}

x[left]=temp;  //插入

}


直接选择排序:

void CSortDlg::SelectSort(int x[])

{

for (int i=0;i<9;i++) {

SelectExchange(x,i);

}

}


void CSortDlg::SelectExchange(int x[],const int i)

{

int k=i;

for (int j=i+1;j<10;j++)

if(x[j]<x[k])

k=j;

if(k!=i)

{

int temp=x[i];

x[i]=x[k];

x[k]=temp;

}

}


基数排序:

int CSortDlg::digit(int data,int n)

{

int i = -1;

for (int k = 0; k <= n;++k)

{

i = data % RADIX;

data = data / RADIX;

}

return i;

}


void CSortDlg::SortOnDigit(int* data,int d,int left,int right)

{

int c[RADIX] = {0};   //c[i]记录d位上为i的元素个数

for (int i = left; i <= right ;i++ )

{

++c[digit(data[i],d)];   //记录d位上相同的数据个数

}

for (int j = 1;j < RADIX ;++j )

{

c[j] += c[j-1];   //很明显,d位上较大(就是j的值),元素越大

                     //c[j]记录d位上小于等于j的元素的个数

}

int len = right - left +1;

int* tmp = new int[len];

//知道了有多少元素在d位置上比自己小,则可以确定d位上的值的元素位置

for (int k = right; k >= left; k--)

{

tmp[--c[digit(data[k],d)]] = data[k];

}

for (int m = left;m <= right ;++m )

{

data[m] = tmp[m - left];

}

delete[] tmp;

}


void CSortDlg::RadixSort(int* data,int left,int right)

{

for (int i = 0;i < WIDTH; ++i)

{

SortOnDigit(data,i,left,right);

}

}


快速排序:

void CSortDlg::quick_sort(int x[], int low, int high)   //快速排序函数的实现过程

{

int pivotkey;

if(low<high)

{

pivotkey=partition(x,low,high);

quick_sort(x,low,pivotkey-1);

quick_sort(x,pivotkey+1,high);

}

}


int CSortDlg::partition(int x[],int low,int high)

{

int pivotkey;

pivotkey=x[low];

while(low<high)

{

while(low<high&&x[high]>pivotkey)

--high;

x[low]=x[high];

while(low<high&&x[low]<pivotkey)

++low;

x[high]=x[low];

}

// x[low]=x[0];

x[low]=pivotkey;

return low;

}


堆排序:

void CSortDlg::HeapSort(int*list,int num)

{

for(int i=(num-2)/2;i>=0;i--)

FiltDown(list,i,num-1);

for(i=num-1;i>=1;i--)

{

int temps=list[0];

list[0]=list[i];

list[i]=temps;

FiltDown(list,0,i-1);

// if(m_mark==1)

// show(list);

}

}


void CSortDlg::FiltDown(int*list,int i,int end)

{

int c=i;int ch=2*i+1;

int temp=list[i];

while(ch<=end)

{

if(ch<end&&list[ch]<list[ch+1])

ch++;

if(temp>=list[ch])break;

else

{

list[c]=list[ch];

c=ch;ch=2*ch+1;

}

}

list[c]=temp;

}


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

历史上的今天

评论

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

页脚

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