排序算法一轮复习

1、排序算法一轮复习（一）安吉县昌硕高级中学 吴志成排序算法在高考中的典型考法由排序代码判断数据加工后的结果(2016.04,11)统计趟数、比较次数和交换次数(2015.09,12)跟踪指定数据的位置变化情况(2016.10,16)跟踪指定位置的数据变化情况(相关资料)双向排序(2017.04,12)排序的优化(2015.10,16)排序中剔除重复数据(2017.11,16)只对某些特征数据排序(2018.04,16)如何应对排序算法考点越来越高要求基本原则：重基础，重细节 应对措施：理解冒泡排序和选择排序的排序过程，能熟练运用两种排序方法对具体的数据序列进行排序掌握冒泡排序和选择排序的代码推导

2、方法，能通过阅读代码还原出具体的排序过程了解冒泡排序和选择排序的典型应用，能通过具体案例代码判断属于什么应用 从最基本入手，考察排序过程103672冒泡排序从右往左冒小泡：从左往右冒大泡：1036723627326710236710规律：1、n个元素，需要执行n-1趟2、比较次数：n(n-1)/23、交换次数：比较次数想一想：n个元素冒泡排序，执行的趟数，比较次数和交换次数？76310276103271063210763210276310如何更好地理解冒泡排序代码冒泡排序的算法实现，是一趟一趟重复执行的过程，因此，重点是实现第i趟执行的过程（从右往左冒小泡）a(1)a(2)a(i-1)a(i)

3、a(i+1)a(i+2)a(n-2)a(n-1)a(n)目前执行第i趟：a(n)-a(i)相邻数据两两比较：a(n)与a(n-1)a(n-1)与a(n-2)a(i+1)与a(i)a(j)a(j-1)ifthentemp=a(j)a(j)=a(j+1)a(j+1)=tempEnd ifFor j=1 to n-iNext jFor i=1 to n-1Next i12i-1从最基本入手，考察排序过程选择排序选出小值放左边：103726237106237106236107236710选出大值放右边：103726637210632710236710236710想一想：n个元素选择排序，执行的趟数，比

4、较次数和交换次数？规律：1、n个元素，需要执行n-1趟2、比较次数：n(n-1)/23、交换次数：执行趟数与冒泡排序效率的比较：就凭这一点，选择排序效率更高如何更好地理解选择排序代码选择排序的算法实现，是一趟一趟重复执行的过程，因此，重点是实现第i趟执行的过程（选出小值放左边）a(1)a(2)a(i-1)a(i)a(i+1)a(i+2)a(n-2)a(n-1)a(n)目前执行第i趟：a(i)-a(n)先假定当前第一个位置值最小p=i打擂台，后续元素依次与擂台上面的元素比较，小值留在擂台上，比完后，擂台上就是最小值（注意：擂台为p，表示小值位置）a(i+1)与a(p)a(i+2)与a(p)a(n

5、)与a(p)a(j)a(p)ifthenp=jEnd ifFor j=i+1 to nNext jpiifthentemp=a(p)a(p)=a(i)a(i)=tempEnd ifFor i=1 to n-1Next i擂台比武，选出所需，体现出“选”的特色趟数循环p=i假定当前第一个位置最小第i趟循环擂台上不是小值，易主第i趟选出真正最小值后，若不在当前第一个位置上，交换如何更好地理解选择排序代码选择排序的算法实现，是一趟一趟重复执行的过程，因此，重点是实现第i趟执行的过程（选出大值放右边）a(1)a(2)a(3)a(i-1)a(i)a(i+1)a(n-1)a(n)nn-1i+1目前执行第i趟：a(1)-a(i)i先假定当前最后一个位置值最小p=i打擂台，前面元素依次与擂台上面的元素比较，大值留在擂台上，比完后，擂台上就是最大值（注意：擂台为p，表示大值位置）a(i-1)与a(p)a(i-2)与a(p)a(1)与a(p)a(j)a(p)ifthenp=jEnd ifFor j=i-1 to 1 step -1Next jIfpithentemp=a(p)a(p)=a(i)a(i)=tempEnd ifp=iFor i=n to 2Next i小结冒泡排序与选择排序的过程（自己会排就了）冒泡排序与选择排序的规律、