§10.3.1冒泡排序 设初始记录集为 2030104533225550 则第一趟冒泡的过程为: 2030104533225550/20与30比较,未交换 2010304533225550/30与10比较,交换 2010304533225550∥30与45比较,未交换 2010303345225550/45与33比较,交换 2010303322455550/45与22比较,交换 2010303322455550/45与55比较,未交换 2010303322455055/5与50比较,交换
11 §10.3.1 冒泡排序 • 设初始记录集为 20 30 10 45 33 22 55 50 • 则第一趟冒泡的过程为： 20 30 10 45 33 22 55 50 //20与30比较，未交换 20 10 30 45 33 22 55 50 //30与10比较，交换 20 10 30 45 33 22 55 50 //30与45比较，未交换 20 10 30 33 45 22 55 50 //45与33比较，交换 20 10 30 33 22 45 55 50 //45与22比较，交换 20 10 30 33 22 45 55 50 //45与55比较，未交换 20 10 30 33 22 45 50 55 //55与50比较，交换
§1031冒泡排序 ·每趟的结果 1020302233455055〃第2趟 02022303345505〃第3趟 020223033455055第4趟 1020223033455055第5趟 020223033455055第6趟 1020223033455055∥第7趟 1020223033455055∥第8趟 12
12 §10.3.1 冒泡排序 •每趟的结果 10 20 30 22 33 45 50 55 //第2趟 10 20 22 30 33 45 50 55 //第3趟 10 20 22 30 33 45 50 55 //第4趟 10 20 22 30 33 45 50 55 //第5趟 10 20 22 30 33 45 50 55 //第6趟 10 20 22 30 33 45 50 55 //第7趟 10 20 22 30 33 45 50 55 //第8趟
§1033快速排序 (-)基本思想 基本思想是:在待排序的n个记录中任取一个记录(例如就 取第一个记录),以该记录的键值为标准,将所有记录分为 两组(一般都是无序的),使得第一组中各记录的键值均小 于或等于该键值,第二组中各记录的键值均大于该键值。然 后把该记录就排在这两组的中间(这也是该记录最终的位 置)。此称为一趟分割,对所分成的两组再分别重复上述方 法,直到所有记录都排在适当位置为止 13
13 §10.3.3 快速排序 (一)基本思想 •基本思想是：在待排序的n个记录中任取一个记录（例如就 取第一个记录），以该记录的键值为标准，将所有记录分为 两组（一般都是无序的），使得第一组中各记录的键值均小 于或等于该键值，第二组中各记录的键值均大于该键值。然 后把该记录就排在这两组的中间（这也是该记录最终的位 置）。此称为一趟分割，对所分成的两组再分别重复上述方 法，直到所有记录都排在适当位置为止
§1033快速排序 (二)分割算法 一趟快速排序的具体做法是:设两个指针i和j,它们的初值 分别为0、n-1,且把a[o送入工作单元x中保存(选第一个记 录为标准),然后比较a和x,若a[j>x,则j减1后继续与x比 较,直至r<=x,然后,将a[订移至a[的位置,令加1,接 着进行a[和x的比较,若a[i<x,则令x加1,然后继续比较, 直至满足a>=x,此时,将a移至r订的位置,令j减1,之 后,重复上述过程,直至ij。此时便是记录x所应在的位置
14 §10.3.3 快速排序 (二)分割算法 •一趟快速排序的具体做法是：设两个指针i和j，它们的初值 分别为0、n-1，且把a[0]送入工作单元x中保存（选第一个记 录为标准），然后比较a[j]和x，若a[j]>x，则j减1后继续与x比 较，直至r[j]＜=x，然后，将a[j]移至a[i]的位置，令i加1，接 着进行a[i]和x的比较，若a[i]<x，则令x加1，然后继续比较， 直至满足a[i]＞=x，此时，将a[i]移至r[j]的位置，令j减1，之 后，重复上述过程，直至i==j。此时i便是记录x所应在的位置
§1033快速排序 (二)分割算法 long SortPartition (in al], long pl, long p2) /对a[pl]-a[p2]进行分割,返回分割点 long 1,J, lntⅩ D j→p2; X=a 15
15 §10.3.3 快速排序 (二)分割算法 long SortPartition (in a[], long p1, long p2); {//对a[p1]—a[p2]进行分割，返回分割点 long i, j; int x; i =p1; j =p2; x =a[i];