布置让写一个n^2的排序算法和一个nlogn的排序算法。
刚好把排序算法整理一下。
首先是最基本的直接插入排序。
直接插入排序
原理：把待排序的数插入到已经排序好的有序序列中。
比如 V[0]V[1]...V[N-1]是一个有序序列，现在插入 V[N];
那么需要逐个比较与V[N]的大小，大的向后移。
总的来说就是不断的交换。
时间复杂度为 O（n^2）.
void swap(int &a,int & b)
{
int t=a;
a=b;
b=t;
}
void InsertSorting()
{
for(int i=0;i<MAX;i++)
{
for(int j=i;j>0;j--)
{
if(b[j]<b[j-1])
swap(b[j],b[j-1]);
else
break;
}
}
print();
}
二分插入排序
对于上面的排序可以进行优化，比如因为前面的数是有序的单调的所以
在比较的时候加入可以加入二分查找。
那么看起来好像优化到了 nlogn，但其实因为移动的次数是一样的
所以时间复杂度还是 O（n^2）
int binarysearch(int aim,int l,int r) //二分查找
{
while(l<=r)
{
int mid=(l+r)>>1;
if(b[mid]>=aim)
r=mid-1;
else
l=mid+1;
}
return r+1;
}
void InsertSorting_binarysearch() //插入排序
{
for(int i=0;i<MAX;i++)
{
int j=i;
int t=b[i];
int f=binarysearch(t,0,j);
while(j>f)
{
b[j]=b[j-1];
j--;
}
b[j]=t;
}
print();
}
希尔插入排序
这个还是这次整理才知道的插入排序的方法。 其实平时有些题目会用到其中的想法， 1 先把待排序的数分成m个子序列 2 分别对这m个子序列进行插入排序操作 3 缩小m，再次重复上面 直到m==1。 不过希尔排序并不是一个稳定的排序，因为如果a[i]==a[j]但是被分到了不同的组 会有发生交换的可能。void ShellSorting()
{
int gap=MAX/2;
while(gap>0)
{
for(int i=0;i<gap;i++)
{
for(int j=i+gap;j<MAX;j+=gap)
{
for(int k=j;k>i;k-=gap)
{
if(b[k]<b[k-gap])
{
swap(b[k],b[k-gap]);
}
else
break;
}
}
}
gap/=2;
}
print();
}
附上完整的代码用16个随机数做的实验
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#define MAX 16
int a[20];
int b[20];
void init()
{
for(int i=0;i<MAX;i++)
b[i]=a[i];
}
void print()
{
for(int i=0;i<MAX;i++)
printf("%d ",b[i]);
printf("\n");
}
// 直接插入排序--------------------------
void swap(int &a,int & b)
{
int t=a;
a=b;
b=t;
}
void InsertSorting()
{
for(int i=0;i<MAX;i++)
{
for(int j=i;j>0;j--)
{
if(b[j]<b[j-1])
swap(b[j],b[j-1]);
else
break;
}
}
print();
}
//二分插入排序---------------------------
int binarysearch(int aim,int l,int r)
{
while(l<=r)
{
int mid=(l+r)>>1;
if(b[mid]>=aim)
r=mid-1;
else
l=mid+1;
}
return r+1;
}
void InsertSorting_binarysearch()
{
for(int i=0;i<MAX;i++)
{
int j=i;
int t=b[i];
int f=binarysearch(t,0,j);
while(j>f)
{
b[j]=b[j-1];
j--;
}
b[j]=t;
}
print();
}
// 希尔插入排序----------------------
void ShellSorting()
{
int gap=MAX/2;
while(gap>0)
{
for(int i=0;i<gap;i++)
{
for(int j=i+gap;j<MAX;j+=gap)
{
for(int k=j;k>i;k-=gap)
{
if(b[k]<b[k-gap])
{
swap(b[k],b[k-gap]);
}
else
break;
}
}
}
gap/=2;
}
print();
}
int main()
{
srand(time(0));
for(int i=0;i<MAX;i++)
{
a[i]=10+(rand()%90);
printf("%d ",a[i]);
} //10-99
printf("\n");
init();
InsertSorting(); //插入排序
init();
InsertSorting_binarysearch(); //二分插入排序
init();
ShellSorting(); //希尔插入排序
}