直接插入算法

① 直接插入排序是固定那个算法吗

排序算法包括插入、交换、选择、归并等。
插入算法的共性（直接、二分、希尔插入算法）是移动数据并找到插入点，再交换数据以插入。
插入算法的特性体现在如何找到插入点。
应该说直接插入算法的思想是固定的，无论你具体怎么实现。
你那不是插入排序，算是交换吧。

② 谁能给我几种排序的具体算法（直接插入，折半插入，冒泡，简单选择，快速，堆，归并排序）

直接插入排序
说明：逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次

排序；直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个

序列的排序。时间复杂度为O(n2)。
void InsertSort(elemtype x[],int n)
/*用直接插入法对x[0]-x[n-1]排序*/
{
int i,j;
elemtype s;
for(i=0;i<n-1;i++)
{
s=x[i+1];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+1]=x[j];
j--;
}
x[j+1]=s;
}
}

－－－－－－－－－－－－－－－－－－－－－
希尔排序
说明：希尔排序又称缩小增量排序，增量di可以有各种不同的取法，但最后一次排序时的增量必须为1，最简

单可取di+1=di/2（取小）。时间复杂度为O(n(log2n)2)。

void ShellSort(elemtype x[],int n,intd[],int Number)
/*用希尔排序法对记录x[0]-x[n-1]排序，d为增量值数组*/
/*Number为增量值个数，各组内采用直接插入法排序*/
{
int i,j,k,m,Span;
elemtype s;
for(m=0;m<Number;m++)
{
Span=d[m];
for(k=0;k<Span;k++)
{
for(i=k;i<n-1;i+=Span)/*这个for之后的是“组内采用直接插入法排序”*/
{
s=x[i+Span];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+Span]=x[j];
j-=Span;
}
x[j+Span]=s;
}
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－
直接选择排序
说明：每次将后面的最小的找出来插入前面的已排好的序中。同理，具有n个记录的序列要做n-1次排序。
时间复杂度为O(n2)。
void SelectSort(elemtype x[],int n)
/*用直接选择排序法对x[0]-x[n-1]排序*/
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i++)
{
Small=i;
for(j=i+1;j<n;j++)
if(x[j].key<x[Small].key)
Small=j;

if(Small!=i)
{
Temp=x[i];
x[i]=x[Small];
x[Small]=Temp;
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－
冒泡排序
说明：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到

了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进

行n次冒泡排序。时间复杂度为O(n2)。

void BubbleSort(elemtype x[],int n)
/*用冒泡排序法对x[0]-x[n-1]排序*/
{
int i,j,flag=1;
elemtype Temp;
for(i=1;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(x[j].key>x[j+1].key)
{
flag=1;
Temp=x[j];
x[j]=x[j+1];
x[j+1]=Temp;
}
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
快速排序
说明：又叫分区交换排序，是对冒泡排序方法的一种改进。时间复杂度为O(nlog2n)。

void QuickSort(elemtype x[],int low,int high)
/*用递归方法对记录x[0]-x[n-1]进行快速排序*/
{
int i,j;
elemtype Temp;

i=low;
j=high;
Temp=x[low];

while(i<j)
{
/*在序列的右端扫描*/
while(i<j&&Temp.key<=x[j].key)j--;
if(i<j)
{
x[i]=x[j];
i++;
}

/*在序列的左端扫描*/
while(i<j&&x[i].key<Temp.key)i++;
if(i<j)
{
x[j]=x[i];
j--;
}
}
x[i]=Temp;

/*对子序列进行快速排序*/
if(low<i-1)QuickSort(x,low,i-1);
if(j+1<high)QuickSort(x,j+1,high);
}

－－－－－－－－－－－－－－－－－－－－－－－－－
归并排序
说明：所谓归并排序就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。
时间复杂度为O(nlog2n)。

void merge(r,l,m,h,r1,r2)/*r[l,m]及r[m+1,h]分别有序，归并后置于r2中*/
sqlist r,r2;
int l,m,h;
{
int i,j,k;
k=l;/*k是r2的指示器，i、j分别为s1、s2的指示器*/
i=l;
j=m+1;

while(i<=m&&j<=h)
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else
{
r2[k]=r[j];
j++;
}
k++;
}
if(i>m) /*s1结束*/
while(j<=h)
{
r2[k]=r[j];
j++;k++;
}
else
while(i<=m)
{
r2[k]=r[i];
i++;k++;
}
}

③ 直接插入排序算法实现问题

虽然没学过java但是你的算法错了
while(j>=0&&a[j]>a[i]){a[j+1]=a[j];j--;}

这里的a[i]没有存下来，应该是x=a[i];然后while(......a[j]>x);

④ 一道数据结构，直接插入算法的代码。

for(i=2;i<=n;i++)//循环从第2个元素开始
{ R[0]=R[i];
for(j=i-1;R[j]>R[0];j--)
R[j+1]=R[j];
R[j+1]=R[0];
}

⑤ Java 直接插入 排序算法 要怎么应用

直接插入排序流程如下：
1、首先比较数组的前两个数据，并排序；
2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；
......
4、直至把最后一个元素放入适当的位置。
举例说明：要排序数组：int[] arr = {7, 2, 6, 5, 9, 4};
第1趟后:[2, 7], 6, 5, 9, 4
第2趟后:[2, 6, 7], 5, 9, 4
第3趟后:[2, 5, 6, 7], 9, 4
第4趟后:[2, 5, 6, 7, 9], 4
第5趟后:[2, 4, 5, 6, 7, 9]
算法分析
空间复杂度O(1)
时间复杂度O(n2)
最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。

⑥ 编写程序用直接插入排序的算法进行排序。

#include<stdio.h>
#include<time.h>
#include<math.h>
#include<malloc.h>

void BubbleSort(int *L,int N)
{ //冒泡
int i,j;
int t;

for(i=1;i<=N;i++)
{
for(j=N;j>i;j--)
if(L[j]<L[j-1])
{
t=L[j];
L[j]=L[j-1];
L[j-1]=t;
}
}
}

int SelectMinKey(int *L,int N,int n)
{
int i,min=n;

for(i=n+1;i<=N;i++)
if(L[i]<L[min])
min=i;

return min;
}

void SelectSort(int *L,int N)
{ //选择
int i,j;
int t;

for(i=1;i<N;i++)
{
j=SelectMinKey(L,N,i);
if(i!=j)
{
t=L[i];
L[i]=L[j];
L[j]=t;
}
}
}

void InsertSort(int *L,int N)
{ //插入
int i,j;

for(i=2;i<=N;i++)
{
if(L[i]<L[i-1])
{
L[0]=L[i];
L[i]=L[i-1];
for(j=i-2;L[0]<L[j];j--)
L[j+1]=L[j];
L[j+1]=L[0];
}
}
}

void ShellInsert(int *L,int N, int dk)
{ // 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：
// 1. 前后记录位置的增量是dk，而不是1；
// 2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
int i,j;
for(i=dk+1;i<=N;++i)
if(L[i]<L[i-dk])
{ // 需将L.r[i]插入有序增量子表
L[0]=L[i]; // 暂存在L.r[0]
for(j=i-dk;(j>0&&L[0]<L[j]);j-=dk)
L[j+dk]=L[j]; // 记录后移，查找插入位置
L[j+dk]=L[0]; // 插入
}
} // ShellInsert

void ShellSt(int *L,int N, int dlta[], int t)
{ // 算法10.5
// 按增量序列dlta[0..t-1]对顺序表L作希尔排序。
for(int k=0;k<t;++k)
ShellInsert(L,N, dlta[k]); // 一趟增量为dlta[k]的插入排序
} // ShellSort

void ShellSort(int *L,int N)
{ //希尔
int t=(int)log(N);
int k,*dlta;

dlta=(int*)malloc(t*4); //产生增量序列
for(k=0;k<t;k++)
dlta[k]=(int)pow(2,t-k)-1;

ShellSt(L,N,dlta,t);
}

int main()
{
int N=250;
int i,j,k;
int t;
int ti[16];
int *L;

srand(time(NULL));

printf("长度\t|冒泡\t|选择\t|插入\t|希尔\n");
printf("--------+-------------------------------------------------------------");
for(j=0;N<100000;j++)
{
L=(int *)malloc((N+1)*4);

t=0;

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
BubbleSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
SelectSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
InsertSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
ShellSort(L,N);
ti[t++]=clock();

printf("\n%d\t",N);
for(k=0;k<4;k++)
printf("| %d\t",(ti[2*k+1]-ti[2*k]));

N*=5;
}
printf("\n\n");
}

//这是我们当年学数据结构时我自己写的，给你改了一下，输出是对随机产生一些数，对四种算法进行比较，有问题可以hi我啊

⑦ 直接插入算法排序问题150

选D
因为本来就有序了, 每个元素(除了第一个)和它前面的一个比较一下就行了, 一共(n-1)次

⑧ 关于直接插入排序算法

感觉你写的有点复杂了，这是我用pasical写的插入排序算法，你看看对比一下
for j:=2 to 5 do
begin
Temp := MyArr[j];
{注意如果不用i代替j的话，dec无法通过编译因为j的值即增有减是错误的}
i := j;
dec(i);
while MyArr[i] > Temp do
begin
MyArr[i+1] := MyArr[i];
Dec(i);
end;
MyArr[i+1] := Temp;
end;