排序算法的实现与比较 编程实现直接插入排序、希尔、冒泡排序、快速、选择排序算法，并计算每种排序算法的

Answer 1

void BubbleSort(int Array[],int n)
{//输入数组进行冒泡排序

bool exchange=true;
for(int i=0;i<n;i++)
{
if(exchange==false)
return;
exchange=false;
for (int j=n-1;j>i;j--)
{
if(Array[j]<Array[j-1])
{
int temp=Array[j];
Array[j]=Array[j-1];
Array[j-1]=temp;
exchange=true;
}
}
}
}

void InsertSort(int Arrauy[],int n)
{//直接插入排序
for (int i=0;i<n-15 ;i++)
{
for (int j=i;j>=0;j--)
{
if (Arrauy[i+1]>Arrauy[j])
{//找到插入位置,在j之后
int temp=Arrauy[i+1];
for(int k=i;k>j;k--)
Arrauy[i]=Arrauy[i+1];
Arrauy[j+1]=temp;
break;
}
}
}
}

void BinaryInsertSort(int Arrary[],int n)
{//二分插入排序
for (int i=0;i<n-1;i++)
{
int temp=Arrary[i+1];
int left=0,right=i;
int mid=(left+right)/2;
while(left<right)
{
if(temp>Arrary[mid])
left=mid+1;
else
right=mid-1;
mid=(left+right)/2;
}
for(int j=i;j>mid;j--)
Arrary[j]=Arrary[j+1];
Arrary[mid+1]=temp;
}
}

void ShellSort(int Array[],int n)
{
//希尔插入排序
int gap=n;
do
{
gap=gap/3+1;
for (int i=gap;i<n;i++)
{//对子序列进行插入排序
int temp=Array[i];
int j=i-gap;
while(j>=0)
{
if (temp<Array[j])
{
Array[j+gap]=Array[j];
j=j-gap;
}
else
{
Array[j+gap]=temp;
break;
}
}
}
}while(gap>1);
}

void QuickSort(int Array[],const int n)
{//快速排序
QuickSort(Array,0,n-1);
}
void QuickSort(int Array[],const int left,const int right)
{//快速排序子过程
if(left<right)
{
int pivotpos= Partition(Array,left,right);
QuickSort(Array,left,pivotpos-1);
QuickSort(Array,pivotpos+1,right);
}

}

int Partition(int Array[],const int left,const int right)
{//划分过程
int pivot=left;
for (int i=left+1;i<=right;i++)
{
if(Array[i]<Array[left])
{
pivot++;
int temp=Array[i];Array[i]=Array[pivot];Array[pivot]=temp;
}
}
int temp=Array[left];Array[left]=Array[pivot];Array[pivot]=temp;
return pivot;
}

void SelectSort(int Array[],int n)
{
//直接选择排序
for (int i=0;i<n;i++)
{
int min=i;
for (int j=i;j<n;j++)
{
if(Array[j]<Array[min])
min=j;
}
if(min!=i)
{
int temp=Array[min];Array[min]=Array[i];Array[i]=temp;
}
}
}

时间复杂度 ：
插入，冒泡，选择 O（n×n）
快速O（nlogn）
希尔 不确定

Answer 2

给分才做

Answer 3

好难，不会！

Answer 4

没分。。。