Java网络程序设计 课件 单元3-06 排序算法

控制结构、方法与数组应用单元三if语句switch语句循环语句目录CONTENTS123方法一维数组目录CONTENTS45排序算法二维数组673.6排序算法所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。排序的算法有很多，各种算法对空间的要求及时间效率也各有差别。其中插入排序和冒泡排序又被称作简单排序，它们对空间的要求不髙，但时间效率不稳定。而其他一些排序相对于简单排序来说对空间的要求稍高一点，但时间效率却能稳定在很高的水平。从实际编程的角度看，很少需要自己编写算法实现排序，Java的一些工具类中提供了一些静态方法可以实现排序的功能。3.6.1冒泡排序由于在排序过程中总是小数往前放，大数往后放，类似于小的气泡往上升，所以称作冒泡排序。通过上面的分析可以看出，假设需要排序的序列的个数是n，则需要经过n-l轮，最终完成排序。在第一轮中，比较的次数是n-1次，之后每轮减少1次。冒泡排序就是依次比较相邻的两个数，将小数放在前面，大数放在后面。第一轮：先比较第1个和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后；至此第一轮结束，将最大的数放到了最后。第二轮：仍从第一对数开始比较，将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的数），第二轮结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。3.6.1冒泡排序用Java语言实现冒泡排序，可以用双重for循环实现，其核心代码如下。staticvoidbubbleSort(int[]a){//引用传递inttemp;//数组的长度可以通过“数组名.length”获得for(inti=0;i<a.length-1;i++){//需要比较n-1轮for(intj=0;j<a.length-i-1;j++){//根据a.length-i-1，每轮需要比较的次数逐轮减少1次if(a[j]>a[j+l]){ //相邻数进行比较，符合条件进行替换temp=a[j];a[j]=a[j+1];a[j+l]=temp;}}}}3.6.2插入排序插入排序包括直接插入排序、二分插入排序、链表插入排序和希尔排序。接下来介绍最简单的直接插入排序。直接插入排序存在两个表，一个是有序表，另一个是无序表。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一轮：比较无序表中前两个数，然后按顺序插入到有序表中，剩下的数仍在无序表中。第二轮：把无序表中剩下的第一个数与有序表的两个数进行比较，然后把这个数插入到合适位置。按此规律操作，直至无序表中的数全部插入到有序表，完成排序。3.6.2插入排序用Java语言实现直接插入排序的核心代码如下。staticvoidinsertSort(int[]a){//引用传递for(inti=1;i<a.length;i++){intj=-1;while(j<=i&&a[i]>a[++j]);//找到a[i]应该摆放的位置if(j<i){//将j之后的数据移动一位，然后把a[i]移动到j处inttemp=a[i];for(intk=i-1;k>=j;k--){a[k+1]=a[k];}a[j]=temp;}