原帖地址 http://kongec.blog.sohu.com/85141353.html

附  六分钟演示15中算法

http://www.guokr.com/post/482666/

一、插入排序(Insertion Sort)
1. 基本思想:
每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。
2. 排序过程:  
【示例】:
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]

void sort(int *p) //添加监视哨
{
int b[11]={0};
for(int i=0;i<10;i++)
b[i+1]=p[i];
int j=0;
for(int i=2;i<11;++i)
{
b[0]=b[i];
j=i-1;
while(b[0]<b[j])
{
b[j+1]=b[j];
--j;
}
b[j+1]=b[0];
}
for(int i=0;i<10;i++)
p[i]=b[i+1];
}
void sort(int *p)//不添加监视哨
{
int b[10]={0};
int temp=0;
for(int i=1;i<10;i++)
{
int index=i;
while(index)
{
if(p[index]<p[index-1])
{
temp=p[index];
p[index]=p[index-1];
p[index-1]=temp;
}
index--;
}
}
}

  

int _tmain(int argc, _TCHAR* argv[])
{
int a[10]={2,4,3,1,7,5,6,9,8,0};
sort(a);
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}

二、选择排序
1. 基本思想:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
2. 排序过程:
【示例】:
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

void sort(int *p)
{
int temp=0;
int temp1=0;
for(int i=0;i<10;++i)
{
temp=p[i];
for(int j=i;j<10;++j)
{
if(p[j]<temp)
{
temp1=p[j];
p[j]=temp;
temp=temp1; }
}
p[i]=temp;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[10]={2,4,3,1,7,5,6,9,8,0};
sort(a);
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}

三、冒泡排序(BubbleSort)
1. 基本思想:
两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。
2. 排序过程:
设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。
【示例】:
49 13 13 13 13 13 13 13 
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

void sort(int *p)
{
int temp=0;
for(int i=0;i<10;++i)
{
for(int j=i+1;j<10;++j)
{
if(p[j]<p[i])
{
temp=p[j];
p[j]=p[i];
p[i]=temp;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[10]={2,4,3,1,7,5,6,9,8,0};
sort(a);
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}

  

四、快速排序(Quick Sort)
1. 基本思想:
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I- 1]和R[I 1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R [1..I-1]≤X.Key≤R[I 1..H](1≤I≤H),当R[1..I-1]和R[I 1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。
1. 排序过程:
初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13] 49 [76 97 65 49] 
二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
最后的排序结果 13 27 38 49 49 65 76 97

void sort(int *a,int i,int j)
{
int m=i;
int n=j;
int k=0;
int temp=0;
k=a[(i+j)/2];
do
{
while(a[m]<k&&m<j) m++;
while(a[n]>k&&n>i) n--;
if(m<=n)
{
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) sort(a,m,j);
if(n>i) sort(a,i,n);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[10]={2,4,3,1,7,5,6,9,8,0};
sort(a,0,9);
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}

  

05-25 23:12