数据结构——C语言描述第7章-排序.pptxVIP

数据结构——C语言描述（慕课版）;;待排序数据可以全部一次性载入内存，排序操作只和内存打交道。;;内排序算法;;;第一趟比较：最大元素移到序列尾部;voidbubbleSort(inta[],intn)

{inti,j,tmp;intchangeFlag=1;

for(j=n;j1;j--)

{if(!changeFlag)break;//上一轮无交换

changeFlag=0;

for(i=1;ij;i++)

if(a[i-1]a[i])

{tmp=a[i-1];a[i-1]=a[i];a[i]=tmp;changeFlag=1;}

}

}

;加changeFlag标志，当某趟比较无交换发生，表明序列有序，排序结束。;;相等不交换，保持排序前后相等元素相对先后不变，为稳定排序。;;;;voidinsert(intb[],intn,intx)

//n为有序表a中当前元素的个数，x为待插入新元素

{inti,j;

?for(i=n-1;i=0;i--)//从后往前找第一个不比x大的元素

if(b[i]=x)break;

for(j=n-1;ji;j--)//将所有大于x的元素后移一位

b[j+1]=b[j];

b[i+1]=x;//在腾出的位置上存x

};voidinsertSort(inta[],intn)

{inti;

//将前i个元素视作有序序列，将第i+1个元素插入到前面i个元素

//组成的有序序列中

for(i=1;in;i++)

insert(a,i,a[i]);

};;大于待插入的值的元素才后移，稳定排序。;插入排序改进——折半插入法：;第一趟排序：step=5;第二趟排序：step=2;;;;归并思路：两个有序序列归并为一个有序序列。;经过a[i]，b[j]比较后，c[k]取小者a[i]，i=i+1，k=k+1，j不变：;经过a[i]，b[j]比较后，c[k]取小者b[j]，i=i+1，k=k+1，j不变：;i越界，序列c抄下序列b中所有剩余元素：j=j+1，k=k+1：;;归并排序利用两个序列归并思想：分割+合并;;归并按照分割的逆序，因此可以用递归实现。

原始序列在一个数组中，处理时，将数组元素等分为二，前一序列下标范围[start,mid]；后一序列下标范围为[mid+1,end]。;voidmerge(inta[],intstart,intmid,intend)

{ inti,j,k;int*c;

? //创建实际空间存储合并后结果

c=(int*)malloc((end-start+1)*sizeof(int));

i=start;j=mid+1;k=0;

//两个有序序列中元素的比较合并

while((i=mid)(j=end))

{ if(a[i]=a[j])

{c[k]=a[i]; i=i+1; }; else {c[k]=a[j]; j=j+1; }

k=k+1;

}

?

//若序列1中i未越界，抄写剩余元素

while(i=mid)

{c[k]=a[i];i=i+1;k=k+1;}

//若序列2中j未越界，抄写剩余元素

while(j=end)

{c[k]=a[j];j=j+1;k=k+1;}

;//将合并结果写回原来的数组

for(i=0;ik;i++)

a[start+i]=c[i];

//释放临时数组

free(c);

};voidmergeSort(inta[],intstart,intend)

{intmid;

if(start==end)return;//只有1个元素，视作有序，结束分割

else

{