| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 766 人关注过本帖
标题:呵呵,超全的排序代码+诠释!和大家分享!
取消只看楼主 加入收藏
风致
Rank: 1
等 级:新手上路
帖 子:42
专家分:0
注 册:2007-9-22
收藏
 问题点数:0 回复次数:0 
呵呵,超全的排序代码+诠释!和大家分享!

呵呵,发现了超全的排序代码!!和大家分享!关于排序的认识
排序总的可以分为插入排序,交换排序,选择排序,归并排序,基数排序等。

其中插入排序又可以细分为直接插入排序,折半排序,希尔排序。
直接排序的基本思想是:当插入第i (i>=1)个对象时,前面的v[0],v[1],…….v[i-1]已经排好序,这时,用v[i]的关键码与v[i-1],v[i-2]……的关键码顺序进行比较,找到插入位置即将v[i]插入,原来位置上的对象向后顺移。直接插入排序的时间复杂度为n2,直接插入排序是一种稳定的排序方法。
折半排序的基本思想是:设在顺序表中有一个对象序列v[0],v[1],….v[n-1],其中,v[0],v[1],….v[i-1]是已经排好序的对象。在插入v[i]时,利用折半查找法寻找v[i]的插入位置。折半插入是一种稳定的排序方法。
希尔排序:当待排序的数列很长时,(即n很大时),关键码平均比较次数和对象平均移动次数大约在n1.25(即n的1.25次方,以下同样)到1.6n1.25范围内。

交换排序又可细分为冒泡排序,快速排序。
冒泡排序的基本思想是:设待排序的数列的大小为n,首先比较v[n-2]和v[n-1]的大小,如果v[n-2]>v[n-1],则交换v[n-2]和v[n-1],然后对v[n-2]和v[n-3]作相同的处理,如此处理, 直到处理完v[0]和v[1],这个称为一趟冒泡,所以只要经过n-1 趟冒泡就可以排好所有对象。 在最坏情况下总的关键码比较次数为0.5n(n-1),对象移动次数为1.5n(n-1)
快速排序的基本思想是:取待排序的数列的某个对象(例如第一个对象)作为基准,将对象分为左右两个数列,左边的全都小于基准,右边的全都大于基准,然后对左右两个树列重复以上操作,直到全部完成。它是一种不稳定的方法,对于待排序的数列很大时,快速排序的确很快,但当待排序的数列很小时,它往往比其它简单的排序方法还要慢。

选择排序又可以细分为直接选择排序,堆排序。
直接选择排序的最坏情况是每一趟都要进行交换,总的对象移动次数是3(n-1)。
堆排序可以分为两个步骤:首先,根据初始输入数据,利用堆的调整算法FilterDown()形成初始堆, 第二步通过一系列的对象交换和重新调整堆进行排序。堆排序的是一个不稳定的排序方法,并且当待排序的数列很大时,堆排序不可取。

归并排序就是将两个或两个以上的有序表合并成一个新的有序表。

基数排序的基本思想是:待排序的对象按m个关键码key[0],…..key[m-1]排序,每个对象的关键码域用一个数组key[m]表示,对各关键码的排序采用箱排序。

从上面可以得出结论(本人观点),当待排序的数列很小时,可以采取直接插入排序,折半排序,希尔排序,直接选择排序,堆排序,归并排序,基数排序等众多排序方法,但当待排序的数列很大时,采用快速排序为优。

就平均性能而言,我认为快速排序最好。
冒泡排序:
void CSortDlg::bubble_sort(int x[]){
//对数组x[]逐趟进行比较 ,遇到逆序即交换
int i =1;int exchange=1;//当exchange为0时,则停止排序
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[align=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;
}

搜索更多相关主题的帖子: 代码 诠释 分享 
2007-09-23 20:13
快速回复:呵呵,超全的排序代码+诠释!和大家分享!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017609 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved