《Java数据结构和算法》第二版 Robert lafore 编程作业 第三章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第三章
3.1 bubbleSort.java程序（清单3.1）和BubbleSort专题applet中，in索引变量都是从左到 右移动的，直到找到最大数据项并把它移动到右边的out变量外。修改bubbleSort()方法， 使它成为双向移动的。这样，in索引先像以前一样，将最大的数据项从左移到右，当它到 达out变量位置时，它掉头并把最小的数据项从右移到左。需要两个外部索引变量，一个在 右边（以前的out变量），另一个在左边。
3.2 在isertSort.java程序(清单3.3)中给ArrayIns类加一个median()方法.这个方法将返回 数组的中间值.(回忆一下,数组中一半数据项比中间值大,一半数据项比中间值小。)
3.3 在insertSort.java程序（清单3.3）中增加一个名为noDups()的方法，这个方法从已经有 序的数组中删掉重复的数据项而不破坏有序性。（可以用insertionSort()方法对数据排序， 或者也可以简单地用main()方法将数据有序地插入到表中。）一种解决方法是每发现一个重 复的数据，就从这个位置开始到数组结尾都向前移动一个位置，但这样就导致消耗很长的 O(N2)的时间级，起码在有很多重复数据项的情况下是这样的。在设计的算法中，不论有多 少重复数据，要确保数据项最多只能移动一次。这样算法只消耗O(N)数量级的时间。
3.4 还有一种简单排序算法是奇偶排序。它的思路是在数组中重复两趟扫描。第一趟扫描选择所有 的数据项对，a[j]和a[j+1]，j是奇数(j=1,3,5,……)。如果它们的关键字的值次序颠倒，就交 换它们。第二趟扫描对所有的偶数数据项进行同样的操作（j=2,4,6,……）。重复进行这样两趟 的排序直到数组全部有序。用oddEvenSort()方法替换bubbleSort.java程序（清单3.1）中的 bubbleSort()方法。确保它可以在不同数据量的排序中运行，还需要算出两趟扫描的次数。奇 偶排序实际上在多处理器环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时 处理偶数对。因为奇数对是彼此独立的，每一对都可以用不同的处理器比较和交换。这样可以非 常快速地排序。
3.5 修改insertSort.java程序（清单3.3）中的insertionSort()方法，使它可以计算排序过 程中复制和比较的次数并显示出总数。为计算比较的次数，要把内层while循环的两个条件分开。 用这个程序测量各种数量的逆序数据排序的复制和比较次数。结果满足O(N2)吗？与已经基本有 序的数据（仅有很少的数据无序）的情况一样吗？从对基本有序数据排序的表现中可得出关于这 个算法效率的什么结论？
3.6 有一个有趣的方法用来删除数组中相同的数据项。插入排序算法中用一个循环嵌套算法，将 数组中的每一个数据项与其他数据项一一比较。如果要删除相同的数据项，可以这样做（参见第 2章第2.6小节）。修改insertSort.java中的insertionSort()方法，使它可以在排序过程中 删除相同的数据项。方法如下：当找到一个重复数据项的时候，通常用一个小于任何值的关键值 来改写这个相同数据项（如果所有值都是正数，则可取-1）。于是，一般的插入排序算法就会像 处理其他数据项一样，来处理这个修改了关键值的数据项，把它移到下标为0的位置。从现在开 始，算法可以忽略这个数据项。下一个相同的数据项将被移到下标为1的位置，依此类推。排序 完成后，所有相同的数据项（现在关键值为-1）都在数组的开头部分。可以改变数组的容量并 把需要的数据前移动数组下标为0的位置。
/* 3.1 bubbleSort.java程序（清单3.1）和BubbleSort专题applet中，in索引变量都是从左到 右移动的，直到找到最大数据项并把它移动到右边的out变量外。修改bubbleSort()方法， 使它成为双向移动的。这样，in索引先像以前一样，将最大的数据项从左移到右，当它到 达out变量位置时，它掉头并把最小的数据项从右移到左。需要两个外部索引变量，一个在 右边（以前的out变量），另一个在左边。 3.2在isertSort.java程序(清单3.3)中给ArrayIns类加一个median()方法.这个方法将返回 数组的中间值.(回忆一下,数组中一半数据项比中间值大,一半数据项比中间值小。) 3.3在insertSort.java程序（清单3.3）中增加一个名为noDups()的方法，这个方法从已经有 序的数组中删掉重复的数据项而不破坏有序性。（可以用insertionSort()方法对数据排序， 或者也可以简单地用main()方法将数据有序地插入到表中。）一种解决方法是每发现一个重 复的数据，就从这个位置开始到数组结尾都向前移动一个位置，但这样就导致消耗很长的 O(N2)的时间级，起码在有很多重复数据项的情况下是这样的。在设计的算法中，不论有多 少重复数据，要确保数据项最多只能移动一次。这样算法只消耗O(N)数量级的时间。 3.4 还有一种简单排序算法是奇偶排序。它的思路是在数组中重复两趟扫描。第一趟扫描选择所有 的数据项对，a[j]和a[j+1]，j是奇数(j=1,3,5,……)。如果它们的关键字的值次序颠倒，就交 换它们。第二趟扫描对所有的偶数数据项进行同样的操作（j=2,4,6,……）。重复进行这样两趟 的排序直到数组全部有序。用oddEvenSort()方法替换bubbleSort.java程序（清单3.1）中的 bubbleSort()方法。确保它可以在不同数据量的排序中运行，还需要算出两趟扫描的次数。奇 偶排序实际上在多处理器环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时 处理偶数对。因为奇数对是彼此独立的，每一对都可以用不同的处理器比较和交换。这样可以非 常快速地排序。 3.5修改insertSort.java程序（清单3.3）中的insertionSort()方法，使它可以计算排序过 程中复制和比较的次数并显示出总数。为计算比较的次数，要把内层while循环的两个条件分开。 用这个程序测量各种数量的逆序数据排序的复制和比较次数。结果满足O(N2)吗？与已经基本有 序的数据（仅有很少的数据无序）的情况一样吗？从对基本有序数据排序的表现中可得出关于这 个算法效率的什么结论？ 3.6有一个有趣的方法用来删除数组中相同的数据项。插入排序算法中用一个循环嵌套算法，将 数组中的每一个数据项与其他数据项一一比较。如果要删除相同的数据项，可以这样做（参见第 2章第2.6小节）。修改insertSort.java中的insertionSort()方法，使它可以在排序过程中 删除相同的数据项。方法如下：当找到一个重复数据项的时候，通常用一个小于任何值的关键值 来改写这个相同数据项（如果所有值都是正数，则可取-1）。于是，一般的插入排序算法就会像 处理其他数据项一样，来处理这个修改了关键值的数据项，把它移到下标为0的位置。从现在开 始，算法可以忽略这个数据项。下一个相同的数据项将被移到下标为1的位置，依此类推。排序 完成后，所有相同的数据项（现在关键值为-1）都在数组的开头部分。可以改变数组的容量并 把需要的数据前移动数组下标为0的位置。 */package chap03;// bubbleSort.java// demonstrates bubble sort// to run this program: C>java BubbleSortApp////////////////////////////////////////////////////////////////class ArrayBub {private long[] a; // ref to array aprivate int nElems; // number of data items// --------------------------public ArrayBub(int max) // constructor{a = new long[max]; // create the arraynElems = 0; // no items yet}// --------------------------public void insert(long value) // put element into array{a[nElems] = value; // insert itnElems++; // increment size}// --------------------------public void display() // displays array contents{for (int j = 0; j < nElems; j++)// for each element,System.out.print(a[j] + " "); // display itSystem.out.println("");}// --------------------------public void bubbleSort() {int out, in;for (out = nElems - 1; out > 0; out--)// outer loop (backward) //这里必须是 out > 0 如果是 > 1的话，4321 会排成 2134for (in = 0; in < out; in++)// inner loop (forward)if (a[in] > a[in + 1]) // out of order?swap(in, in + 1); // swap them} // end bubbleSort()// --------------------------// ==============================================================// 编程作业3.1 P78(97)public void bubbleSort1() {int leftout = 0, rightout = nElems - 1, in; // leftout,rightout为左右两端指针for (; rightout > leftout; rightout--, leftout++) {for (in = leftout + 1; in < rightout; in++)if (a[in] > a[in + 1])swap(in, in + 1);for (in = rightout - 1; in > leftout; in--)if (a[in] < a[in - 1])swap(in, in - 1);}}// ==============================================================// 编程作业3.4 P79(98)// 奇偶排序的过程如下// 初始序列 4 3 2 1// 第1次// i为偶数比较 (4,3)和(2,1)对// 结果为 3 4 1 2// i为奇数比较 (4,1)对// 结果为 3 1 4 2// 第2次// i为偶数比较 (3,1)和(4,2)对// 结果为1 3 2 4// i为奇数比较 (3,2)对// 结果为1 2 3 4// 第3次// i为偶数比较 (1,2)和(3,4)对// 结果为1 2 3 4// i为奇数比较(2,3)// 结果为1 2 3 4// 此次比较没有交换，所以排序结束public void oddEvenSort() {boolean change = true;while (change) {// 当不再有交换时，排序完成change = false;for (int i = 0; i < nElems - 1; i += 2) { // i为偶数if (a[i] > a[i + 1]) {swap(i, i + 1);change = true;}}for (int i = 1; i < nElems - 1; i += 2) { // i为奇数if (a[i] > a[i + 1]) {swap(i, i + 1);change = true;}}}}// ==============================================================// 使用一个独立的方法不一定好，因为方法调用会增加一些额外的消耗。自己的程序里将交// 换操作这段代码直接放到程序中。private void swap(int one, int two) {long temp = a[one];a[one] = a[two];a[two] = temp;}// --------------------------} // end class ArrayBub// //////////////////////////////////////////////////////////////public class BubbleSortApp {public static void main(String[] args) {int maxSize = 100; // array sizeArrayBub arr; // reference to arrayarr = new ArrayBub(maxSize); // create the arrayarr.insert(77); // insert 10 itemsarr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display(); // display itemsarr.bubbleSort(); // bubble sort themarr.display(); // display them again// ======================================// 编程作业3.1 P78(97)arr = new ArrayBub(maxSize); // create the arrayarr.insert(4);arr.insert(3);arr.insert(2);arr.insert(1);arr.display(); // display itemsarr.bubbleSort1(); // bubble sort themarr.display(); // display them again// ======================================// //编程作业3.4 P79(98)ArrayBub arr1 = new ArrayBub(maxSize);arr1.insert(8);arr1.insert(7);arr1.insert(6);arr1.insert(5);arr1.display();arr1.oddEvenSort(); // 奇偶排序arr1.display();// ======================================} // end main()} // end class BubbleSortApp// //////////////////////////////////////////////////////////////package chap03;// insertSort.java// demonstrates insertion sort// to run this program: C>java InsertSortApp//--------------------------class ArrayIns {private long[] a; // ref to array aprivate int nElems; // number of data items// --------------------------public ArrayIns(int max) // constructor{a = new long[max]; // create the arraynElems = 0; // no items yet}// --------------------------public void insert(long value) // put element into array{a[nElems] = value; // insert itnElems++; // increment size}// --------------------------public void display() // displays array contents{for (int j = 0; j < nElems; j++)// for each element,System.out.print(a[j] + " "); // display itSystem.out.println("");}// --------------------------public void insertionSort() {int in, out;for (out = 1; out < nElems; out++) // out is dividing line{long temp = a[out]; // remove marked itemin = out; // start shifts at outwhile (in > 0 && a[in - 1] >= temp) // until one is smaller,//这里 a[in-1]= temp的时候，可以不用移动,可以改成 a[in-1] > temp{a[in] = a[in - 1]; // shift item to right--in; // go left one position}a[in] = temp; // insert marked item} // end for} // end insertionSort()// --------------------------// ==========================================================// 编程作业3.5 P79(98)public int insertionSort1() {int in, out;int compare = 0; // 比较次数int copy = 0; // 复制次数for (out = 1; out < nElems; out++) // out is dividing line{long temp = a[out]; // remove marked itemin = out; // start shifts at outwhile (in > 0) // until one is smaller,{if (a[in - 1] > temp) {a[in] = a[in - 1]; // shift item to right--in; // go left one positioncompare++;copy++;} else {compare++;break;}}a[in] = temp; // insert marked item} // end forreturn compare + copy;} // end insertionSort()// ==========================================================// 编程作业3.6 P79(98)public void insertionSort2() {int in, out, count = 0;for (out = 1; out < nElems; out++) // out is dividing line{long temp = a[out]; // remove marked itemin = out; // start shifts at outwhile (in > 0 && a[in - 1] >= temp && a[in - 1] != -1) // until one is smaller,{if (a[in - 1] == temp) {temp = -1;count++;}a[in] = a[in - 1]; // shift item to right--in; // go left one position}a[in] = temp; // insert marked item} // end fornElems -= count;for (int i = 0; i < nElems; i++) {a[i] = a[i + count]; // 把排好序的元素向前移动count个位置}} // end insertionSort()// ===========================================================// 编程作业3.2 P78(97) //数组的中间值，到底是位置上的中间，还是大小上的中间？public long median() {this.insertionSort(); // 先排序，再取中间值 //这个中间值是大小上的中间值.return a[nElems / 2];}// ===========================================================// 编程作业3.3 P78(97)// 方法一public void noDups() {this.insertionSort();// 先排序int holenumber = 0;final int FLAG = -1; // 标记为空，假设用户不会输入负数for (int i = 0; i < nElems; i++) { // 把重复的都标记出来for (int j = i + 1; j < nElems; j++) {// 从i+1开始if (a[i] == a[j] && a[j] != FLAG) {a[j] = FLAG;holenumber++;}}}int firsthole = -1; // 第一个空位的索引for (int i = 0; i < nElems; i++) {if (a[i] == FLAG && firsthole == -1) { // 遇到第一个空位时,则这个空位为firstholefirsthole = i;} else if (a[i] != FLAG && firsthole != -1) {// 当有空位时，遇到一个非空值，就把这个非空值复制到firsthole的位置a[firsthole++] = a[i]; // 同时，firthole++，空位往后移一位}}nElems -= holenumber;}// 方法二public void noDups1() {this.insertionSort();// 先排序long NIL = Long.MIN_VALUE; // 标志位for (int i = 0; i < nElems - 1; i++) {if (a[i] == a[i + 1]) {a[i] = NIL; // NIL为标志位，相当于楼主的-1，使用的是Long.MIN_VALUE}}int order = 0;for (int temp = 0; temp < nElems;) {if (a[temp] != NIL) {// 因为a[0]不可能等于NIL所以才可以用这种方法if (temp > order) {a[order] = a[temp];}temp++;order++;} elsetemp++;}nElems = order;}// ===========================================================} // end class ArrayIns// //////////////////////////////////////////////////////////////public class InsertSortApp {public static void main(String[] args) {int maxSize = 100; // array sizeArrayIns arr; // reference to arrayarr = new ArrayIns(maxSize); // create the arrayarr.insert(77); // insert 10 itemsarr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display(); // display itemsarr.insertionSort(); // insertion-sort themarr.display(); // display them again// ======================================// 插入4321arr = new ArrayIns(maxSize); // create the arrayarr.insert(4);arr.insert(3);arr.insert(2);arr.insert(1);arr.display(); // display itemsarr.insertionSort(); // insertion-sort themarr.display(); // display them again// ======================================// 编程作业3.3 P78(97)arr = new ArrayIns(maxSize); // create the arrayarr.insert(2);arr.insert(3);arr.insert(4);arr.insert(3);arr.insert(3);arr.insert(1);arr.insert(2);arr.insert(1);arr.insert(1);arr.insert(1);System.out.println("插入重复值后：");arr.display();arr.noDups();System.out.println("删除重复值后：");arr.display();// ======================================// 编程作业3.5 P79(98)arr = new ArrayIns(maxSize); // create the arrayint count;for (int i = 19; i >= 0; i--) {// 初始化为逆序数组arr.insert(i);}arr.insert(19);arr.insert(9);arr.insert(0);arr.display();count = arr.insertionSort1();arr.display();System.out.println("逆序数组比较复制总数:" + count); // 满足O(N^2)arr = new ArrayIns(maxSize); // create the arrayfor (int i = 0; i <= 19; i++) {// 初始化为顺序数组arr.insert(i);}arr.insert(19);arr.insert(9);arr.insert(0);arr.display();count = arr.insertionSort1();arr.display();System.out.println("顺序数组比较复制总数:" + count); // 满足O(N)// ======================================// 编程作业3.6 P79(98)arr = new ArrayIns(maxSize); // create the arrayarr.insert(2);arr.insert(3);arr.insert(4);arr.insert(3);arr.insert(3);arr.insert(1);arr.insert(2);arr.insert(1);arr.insert(1);arr.insert(1);System.out.println("插入重复值后：");arr.display();arr.insertionSort2();System.out.println("删除重复值后：");arr.display();// ======================================} // end main()} // end class InsertSortApp