1、插入排序
a、 取排序的第二个数据与前一个比较
b、 若比前一个小，则赋值给哨兵
c、 从后向前比较，将其插入在比其小的元素后
d、 循环排序
2、希尔排序
a、 将数组分成两份
b、 将第一份数组的元素与哨兵比较
c、 若其大与哨兵，其值赋给哨兵
d、 哨兵与第二份数组元素比较，将较大的值赋给第二份数组
e、 循环进行数组拆分
3、对数据进行编码
a、 取数组元素与下一个元素比较
b、 若比下一个元素大，则与其交换
c、 后移，重复
d、 改变总元素值，并重复上述代码
4、快速排序
a、 选取标准值
b、 比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较
c、 否则后面元素赋给前面元素
d、 若后指针元素小于标准值，前指针后移，重新比较
e、 否则前面元素赋给后面元素
5、简单选择排序
a、 从数组中选择出最小元素
b、 若不为当前元素，则交换
c、 后移将当前元素设为下一个元素
3、程序实现
#include
using namespace std;
int Cnum = 0;
int Mnum = 0;
class LED
{private :
int compare;
int move;
public:
void InsertSort(int r[] , int n) ;//直接插入排序
void ShellInsert(int r[],int n) ;//希尔排序
void BubbleSort(int r[],int n);//冒泡排序
void Qsort(int r[],int i,int j);//快速排序
void SelectSort(int r[],int n);//选择排序
}
void LED::InsertSort(int r[] , int n) //插入排序
{ compare = 0;
move = 0;
for(int i=2;i<=n;i++)
{
if(r[i]<r[i-1])
{
r[0]=r[i];
move ++;
r[i]=r[i-1];
move ++;
int j;
for(j=i-2;r[0]<r[j];j–)
{compare++;
r[j+1]=r[j];
move ++;
}
++compare;
r[j+1]=r[0];
move ++;
}
++compare;
}
for(int i=1;i<=n;i++)
cout<<r[i]<<" “;
cout<<“比较次数为”<<compare <<” ; 移动次数为"<<move<<" ;";
}
void LED::ShellInsert(int r[],int n) //希尔排序
{compare = 0;
move = 0;
for(int d=n/2;d>=1;d=d/2)
{
for(int i=d+1;i<=n;i++)
{
if(r[i]<r[i-d])
{move++;
r[0]=r[i];
int j;
for(j=i-d;j>0&&r[0]<r[j];j=j-d)
{
r[j+d]=r[j];
move++;
}
compare++;
r[j+d]=r[0];
move++;
}
compare++;
}
}
for(int i=1;i<=n;i++)
cout<<r[i]<<" “;
cout<<“比较次数为”<<compare <<” ; 移动次数为"<<move<<" ;";
}
void LED::BubbleSort(int r[],int n) //冒泡排序
{
compare = 0;
move = 0;
int pos = n ;
while(pos != 0)
{
int bound = pos;
pos = 0;
for(int i =1;i <bound ; i++)
{
compare ++;
if(r[i]>r[i+1])
{
r[0] = r[i]; r[i] = r[i+1];r[i+1] = r[0];
pos = i;
move=move+3;
}
}
}
for(int i=1;i<=n;i++)
cout<<r[i]<<" “;
cout<<“比较次数为”<<compare <<” ; 移动次数为"<<move<<" ;";
}
void LED::SelectSort(int r[],int n) //简单选择排序
{
compare = 0;
move = 0;
for(int i =1 ; i <n ; i++) //n-1趟排序
{
int index = i; //查找最小记录的位置index
for(int j = i + 1;j<=n;j++)
{
compare++;
if(r[j]<r[index])
index = j;
}
if(index != i) //若第一就是最小元素，则不用交换
{
r[0] = r[i];
r[i] = r[index];
r[index] = r[0]; //利用r[0]，作为临时空间交换记录
move+=3;
}
}
for(int i=1;i<=n;i++)
cout<<r[i]<<" “;
cout<<“比较次数为”<<compare <<” ; 移动次数为"<<move<<" ;";
}
void LED::Qsort(int r[],int i,int j)
{
if(i < j)
{ Mnum ++;
int pivotloc = Partion(r,i,j);
Qsort (r,i,pivotloc -1); //左分区快速排序
Qsort (r,pivotloc +1,j); // 右分区快速排序
}
else
{
}
}
void main()
{
int r1[10000],r2[10000],r3[10000];int R[10000];
char y ;
int j=0;
cout<<“请输入元素个数：”<<endl;
cin>>j;
cout<<“请输入将要排序的元素(正序)：”<<endl;
for(int i=1;i<=j;i++)
{cin>>r1[i];
}
cout<<“请输入将要排序的元素(逆序)：”<<endl;
for(int i=1;i<=j;i++)
{cin>>r2[i];
}
cout<<“请输入将要排序的元素（乱序）：”<<endl;
for(int i=1;i<=j;i++)
{cin>>r3[i];
}
cout<<endl;
LED l;
for(int i= 1;i<=j;i++)
{R[i]=r1[i];
}
cout<<“直接插入排序正序输出结果：”;l.InsertSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r2[i];
}
cout<<“直接插入排序逆序输出结果：”;l.InsertSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r3[i];
}
cout<<“直接插入排序乱序输出结果：”;l.InsertSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r1[i];
}
cout<<“希尔排序正序输出结果：”;l.ShellInsert(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r2[i];
}
cout<<“希尔排序逆序输出结果：”;l.ShellInsert(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r3[i];
}
cout<<“希尔排序乱序输出结果：”;l.ShellInsert(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r1[i];
}
cout<<“冒泡排序正序输出结果：”;l.BubbleSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r2[i];
}
cout<<“冒泡排序逆序输出结果：”;l.BubbleSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r3[i];
}
cout<<“冒泡排序乱序输出结果：”;l.BubbleSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r1[i];
}
cout<<“快速排序正序输出结果：”;l.Qsort(R,1,j);
for(int k=1;k<=j;k++)
cout<<R[k]<<" “;
cout<<“比较次数为”<<Cnum <<” ; 移动次数为"<<Mnum<<" “;
Cnum = 0;Mnum = 0;
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r2[i];
}
cout<<“快速排序逆序输出结果：”;l.Qsort(R,1,j);
for(int k=1;k<=j;k++)
cout<<R[k]<<” “;
cout<<“比较次数为”<<Cnum <<” ; 移动次数为"<<Mnum<<" “;
Cnum = 0;Mnum = 0;
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r3[i];
}
cout<<“快速排序乱序输出结果：”;l.Qsort(R,1,j);
for(int k=1;k<=j;k++)
cout<<R[k]<<” “;
cout<<“比较次数为”<<Cnum <<” ; 移动次数为"<<Mnum<<" ";
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r1[i];
}
cout<<“简单选择排序正序输出结果：”;l.SelectSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r2[i];
}
cout<<“简单选择排序逆序输出结果：”;l.SelectSort(R,j);
cout<<endl;
for(int i= 1;i<=j;i++)
{R[i]=r3[i];
}
cout<<“简单选择排序乱序输出结果：”;l.SelectSort(R,j);
cout<<endl;
}
结果：