加载中…九种排序方法实现过程图解
(2013-11-09 15:37:02)
标签：
排序方法实现过程源程序图解 |
分类： 设计心得 |
1、插入排序
#include
using namespace std;
void insertionsort(int A[],int size){
for(int i=1;i
{
int value=A[i];
int j=i-1;
while(j>=0&&A[j]>value)
{
A[j+1]=A[j];
j--;
}
A[j+1]=value;
}
}
int main()
{
int A[]={1,4,7,8,5,2,0,3,6,9};
insertionsort(A,sizeof(A)/sizeof(int));
for(int i=0;i
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、凡是在当前循环中未参与的连续数据都以“……”代替.
2、冒泡排序
#include
using namespace std;
void swap(int &a,int&b)
{
int temp=a;
a=b;
b=temp;
}
void Msort(int A[],int size)
{
for(int i=0;i
{
for(int j=0;j
{
if(A[j]>A[j+1])
{
swap(A[j],A[j+1]);
}
}
}
}
int main()
{
int A[]={1,4,7,8,5,2,0,3,6,9};
Msort(A,sizeof(A)/sizeof(int));
for(int i=0;i
{
cout<<A[ i
]<<" ";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、“□”框住的数为当前循环处于比较状态的数。每次循环最后组数表示本次循环结束后数组数据，即下次循环开始前数组。
3、分治排序（1分治法）（即将两个排好序的数组合并为一个排好序的数组）
#include
using namespace std;
void MERGE(int A[],int p,int q,int r)
//p为A数组起始位置，q正好将A数组一分为两个排好序的数组。r为
//A数组结束位置。
{
int n1=q-p+1; //n1，n2确定分割后数组大小
int n2=r-q;
int *B=new int[n1+1]; //A数组分割为B[4]和C[7]
int *C=new int[n2+1];
int j=0;
int i;
for(i=p;i<=q;i++) //为B数组元素赋值
{
B[j++]=A[i];
}
B[j]=0xffff;
j=0;
for(i=q+1;i<=r;i++) //为C数组元素赋值
{
C[j++]=A[i];
}
C[j]=0xffff;
i=0;
j=0;
for(int k=p;k<=r;k++) //分治排序
{
if(B[i]
{
A[k]=B[i];
i++;
}
else
{
A[k]=C[j];
j++;
}
}
delete []B;
delete []C;
}
int main()
{
int A[]={1,4,7,8,0,2,3,5,6,9};
MERGE(A,0,3,9);
for(int i=0;i<10;i++)
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、A为原始数组,B,C为分割后的排好序的数组，其中B[4]=C[6]=0xffff=65535，这两个多出来的数据就是为了最后的比较准备的。
4.合并排序
#include
using namespace std;
void MERGE(int A[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *B=new int[n1+1];
int *C=new int[n2+1];
int j=0;
int i;
for(i=p;i<=q;i++)
{
B[j++]=A[i];
}
B[j]=0xffff;
j=0;
for(i=q+1;i<=r;i++)
{
C[j++]=A[i];
}
C[j]=0xffff;
i=0;
j=0;
for(int k=p;k<=r;k++)
{
if(B[i]
{
A[k]=B[i];
i++;
}
else
{
A[k]=C[j];
j++;
}
}
delete []B;
delete []C;
}
void mergesort(int A[],int p,int r)
//采用递归的方法，将排好序的数组每次与未排序数组中一个元素进行
//比较。层层推进，达到分而治之的目的。
{
if(p
{
int q =(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
MERGE(A,p,q,r);
}
}
int main()
{
int A[]={1,4,7,8,5,2,0,3,6,9};
mergesort(A,0,9);
for(int i=0;i<10;i++)
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、此程序建立在分治排序法基础上，将A数组不断分割成B和C两有序数组，然后利用分治法进行排序，每次排好序的数组A作为下一次进行排序的B。
5、堆排序
1）堆排序的基本思想：将待排序的数组构造成一个大顶堆，从而获得数组最大的元素，即当前的根节点。将其移走之后，再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行，最后得到一个有序序列。
2）堆分为大根堆(每个节点的值都不大于其父节点的值)和小根堆(每个节点的值都不小于其父节点的值)，是完全二叉树。堆排序核心操作就在于建堆过程和调堆过程，分别对应下面程序的buildmaxheap函数和maxheapify函数。
#include
using namespace std;
void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void maxheapify(int A[],int heapsize,int i) //调整堆
{
int L=2*i+1; //左节点
int R=2*i+2; //右节点
int largest; //记录左右节点与其父节点的较大值
if(LA[i]) //比较左节点与其父节点值
{
largest=L;
}
else
{
largest=i;
}
if(RA[largest]) //比较右节点与其父节点值
{
largest=R;
}
if(largest!=i) //当当前最大值不属于父节点时
{
swap(A[i],A[largest]); //将左右节点中的较大值与父节点交换位置
maxheapify(A,heapsize,largest);
//判断子节点是否仍存在子节点，循环过滤，将最大数滤至堆顶
}
}
void buildmaxheap(int A[],int &heapsize,int
size) //建立大根堆
{
heapsize=size;
for(int i=(size-1)/2;i>=0;i--)
{
maxheapify(A,heapsize,i);
}
}
void heapsort(int A[],int size)
{
int heapsize;
buildmaxheap(A,heapsize,size); //建立大根堆
for(int i=size-1;i>0;i--) //调堆过程
{
swap(A[i],A[0]);
heapsize--;
maxheapify(A,heapsize,0);
}
}
int main()
{
int A[]={1,4,7,8,5,2,0,3,6,9};
heapsort(A,10);
for(int i=0;i<10;i++)
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、初始图为数组A构成的一个二叉树，建堆就在于调整这个初始二叉树A，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。从最后一个非叶子节点开始，对于本数组A = {1, 4,
7, 8, 5, 2, 0, 3, 6, 9}。调堆从A[4] =
5开始。分别与左孩子和右孩子比较大小，如果A[4]最大，则不用调整，否则和孩子中的值最大的一个交换位置。依次转换，最后建立的堆为图1-7.
2、调整堆过程：
6、随机化快速排序
随机化快速排序的基本思想： 产生一个随机数(范围在0~length(A)-1)，通过一躺排序将要排序的数据按此随机数分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小,然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
#include
#include
using namespace
std;
void swap(int
&a,int &b)
{
int temp=a;
a=b;
b=temp;
}
int partition(int A[],int
p,int r) //按随机产生的数的值将A数组分成两个部分
{
int x=A[r];
int i=p-1;
for(int j=p;j
{
if(A[j]<=x)
{
i++;
swap(A[j],A[i]);
}
}
swap(A[r],A[i+1]);
return i+1;
}
int random(int a,int b)
//产生a~b-1随机数
{
time_t t;
srand((unsigned)time(&t));
return
rand()%(b-a)+a;
}
int randompartition(int
A[],int p,int r) //随机分割
{
int
i=random(p,r);
swap(A[i],A[r]);
return
partition(A,p,r);
}
void randomquicksort(int
A[],int p,int r)
{
if(p
{
int
q=randompartition(A,p,r);
randomquicksort(A,p,q-1);
randomquicksort(A,q+1,r);
}
}
int main()
{
int
A[]={1,4,7,8,5,2,0,3,6,9};
randomquicksort(A,0,9);
for(int
i=0;i<10;i++)
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：1、图中列出了五趟排序，细心的会发现第四趟排序其实并没有起到什么作用，这就是因为是随机排序的原因，取到的随机数不一定能满足后面排序的要求，只是重复之前的操作。
7、计数排序
①输入的线性表的元素属于有限偏序集S；
②设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。
2）计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
3）算法的步骤如下：
①找出待排序的数组中最大和最小的元素
②统计数组中每个值为i的元素出现的次数，存入数组C的第i项
③对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
④反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
#include<iostream>
using namespace std;
void countingsort(int A[],int B[],int size,int max)
{
int *C=new
int[max+1];
for(int
i=0;i<=max;i++)
{
C[i]=0;
}
for(int i=0;i
{
++C[A[i]];
}
for(int
i=1;i<=max;i++)
{
C[i]=C[i]+C[i-1];
}
for(int
i=size-1;i>=0;i--)
{
B[C[A[i]]-1]=A[i];
C[A[i]]--;
}
}
int main()
{
int
A[]={1,4,7,8,5,2,3,6,9};
int B[9];
countingsort(A,B,9,9);
for(int
i=0;i<9;i++)
{
cout<<B[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
using namespace std;
void countingsort(int A[],int B[],int size,int max)
{
}
int main()
{
}
程序图解：
8、基数排序
1）基数排序(Radix
Sort)的基本思想：借助于多关键字排序的思想对单逻辑关键字进行排序的方法，先将关键字分解成若干部分，然后通过对各部分关键字的分别排序，最终完成对全部记录的排序。
#include<iostream>
#include<ctime>
using namespace std;
void counting(int A[],int count,int size)
{
int *C=new int[10];
int *D=new int[size];
for(int i=0;i<10;i++)
{
C[i]=0;
}
int *B=new int[size];
for(int i=0;i<size;i++)
{
B[i]=(A[i]/(int)pow(10.0,count));
C[B[i]]++;
}
for(int i=1;i<10;i++)
{
C[i]=C[i]+C[i-1];
}
for(int i=size-1;i>=0;i--)
{
D[C[B[i]]-1]=A[i];
C[B[i]]--;
}
for(int i=0;i<size;i++)
{
A[i]=D[i];
}
}
void radixsort(int A[],int count,int size)
{
for(int i=0;i<count;i++)
{
counting(A,i,size);
}
}
int main()
{
int A[10] = {278, 109, 63, 930, 589, 184, 505, 269, 8
,83};
radixsort(A,3,10);
for(int i=0;i<10;i++)
{
cout<<A[i]<<"
";
}
cout<<endl;
system("pause");
return 0;
}
程序图解：
注：如果细心可以发现，如果将基数排序的数组换成计数排序的数组，那么图解的过程和计数排序是一样的，因为这个时候就不需要多次按照基数去循环，这也就是说明为什么基数排序和计数排序一样是一个非基于比较的排序算法。其排序速度快于任何比较排序算法。
第一轮排序：
http://s4/mw690/002UMOy3gy6E5wXxQXf11&690
http://s4/mw690/002UMOy3gy6E5wYJpCE58&690
第二轮排序：
http://s7/mw690/002UMOy3gy6E5x0wgeY00&690http://s11/mw690/002UMOy3gy6E5x4wcq6e2&690
9、桶排序
1）桶排序的基本思想：将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
2）桶排序以下列程序进行：
①根据给定数组构建一定量的空桶。
②遍历数组，并且把元素一个一个放到对应的桶子去。
③对每个不是空的桶子进行排序（本程序选用的是插入排序）。
④从不是空的桶子里把排好序的元素再依次输出。
#include<iostream>
{
{
喜欢
0
赠金笔
前一篇：单链表指定元素删除