Java进阶：排序、搜索与合并

需积分: 10 113 浏览量更新于2024-07-23 收藏 7.7MB PDF 举报

"《Advanced Topics in Java》是Apress在2014年出版的一本深入探讨Java编程的书籍，核心内容围绕数据结构展开。本书旨在深入理解Java中的排序、搜索、合并等核心概念，并逐步扩展到对象、链表、栈、队列、递归、随机数、游戏模拟、文件操作、二叉树、高级排序和哈希等高级主题。" 在《Advanced Topics in Java》中，作者首先介绍了排序、搜索和合并的基础知识： 1. **排序**： - **选择排序**（Selection Sort）：这是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 - **插入排序**（Insertion Sort）：同样是一种简单的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 - **如何在保持排序的情况下向列表添加新元素**：这涉及在正确的位置插入新元素，以确保列表始终保持排序状态。 - **字符串数组排序**：对包含字符串的数组进行排序，可能需要用到特定的比较逻辑，例如按字典顺序。 - **相关（平行）数组的排序**：当处理多个相关的数组时，需要确保它们的元素在排序后依然对应。 2. **搜索**： - **二分查找**（Binary Search）：在有序列表中搜索元素，通过不断将搜索区间减半来提高效率，适用于大型数据集。接着，书中还涵盖了其他关键话题： - **对象**（Chapter 2）：包括面向对象编程的基本概念，如类、对象、封装、继承和多态性。 - **链表**（Chapter 3）：详细讲解链表的数据结构，如单链表、双链表以及它们的操作。 - **栈和队列**（Chapter 4）：栈的后进先出（LIFO）和队列的先进先出（FIFO）特性，以及它们在实际问题中的应用。 - **递归**（Chapter 5）：递归函数的概念、如何编写和理解递归算法，以及解决各种问题（如计算阶乘、遍历树结构等）的递归方法。 - **随机数、游戏与模拟**（Chapter 6）：生成随机数、实现简单的游戏机制以及使用模拟方法解决实际问题。 - **文件操作**（Chapter 7）：学习如何在Java中读写文件，处理文件流和异常，以及文件I/O的各种技巧。 - **二叉树**（Chapter 8）：二叉树的定义、性质，以及遍历二叉树的不同方法。 - **高级排序**（Chapter 9）：如快速排序、归并排序等更高效的排序算法，以及在特定场景下的最佳选择。 - **哈希**（Chapter 10）：介绍哈希表的概念，哈希函数的设计，以及解决碰撞的方法，如开放寻址法和链地址法。这本书籍对于那些希望深入理解Java编程，尤其是数据结构和算法的开发者来说，是一本非常有价值的资源。通过学习这些内容，读者可以提升编程技能，更好地解决复杂问题，并优化程序性能。

Chapter 1 ■ Sorting, SearChing, and Merging

//n numbers are stored from num[0] to num[n-1]

insertionSort2(num, 0, n-1);

System.out.printf("\nThe sorted numbers are\n");

for (v = 0; v < n; v++) System.out.printf("%d ", num[v]);

System.out.printf("\n");

} //end main

public static void insertionSort2(int list[], int lo, int hi) {

//sort list[lo] to list[hi] in ascending order

for (int h = lo + 1; h <= hi; h++)

insertInPlace(list[h], list, lo, h - 1);

} //end insertionSort2

public static void insertInPlace(int newItem, int list[], int m, int n) {

//list[m] to list[n] are sorted

//insert newItem so that list[m] to list[n+1] are sorted

int k = n;

while (k >= m && newItem < list[k]) {

list[k + 1] = list[k];

--k;

}

list[k + 1] = newItem;

} //end insertInPlace

} //end class InsertSort2Test

1.4 Sorting a String Array

Consider the problem of sorting a list of names in alphabetical order. In Java, a name is stored in a String variable,

and we’ll need a String array to store the list. For the most part, we can work with String as if it were a primitive

type, but it is sometimes useful to remember that, strictly speaking, it is a class. Where necessary, we will point out

the distinction.

One difference that concerns us here is that we cannot use the relational operators (==, <, >, and so on) to

compare strings. We must use functions from the String class (or write our own). Common functions include equals,

equalsIgnoreCase, compareTo, and compareToIgnoreCase. We write a function to sort an array of strings using

insertion sort. We call it insertionSort3.

public static void insertionSort3(String[] list, int lo, int hi) {

//sort list[lo] to list[hi] in ascending order

for (int h = lo + 1; h <= hi; h++) {

String key = list[h];

int k = h - 1; //start comparing with previous item

while (k >= lo && key.compareToIgnoreCase(list[k]) < 0) {

list[k + 1] = list[k];

--k;

}

list[k + 1] = key;

} //end for

} //end insertionSort3

Chapter 1 ■ Sorting, SearChing, and Merging

Consider the problem of sorting the names in alphabetical order. At the end, we would want each name to have

its correct ID number. So, for example, after the sorting is done, name[0] should contain “Charles, Kandice” and id[0]

should contain 4455.

To achieve this, each time a name is moved during the sorting process, the corresponding ID number must also

be moved. Since the name and ID number must be moved “in parallel,” we say we are doing a “parallel sort” or we are

sorting “parallel arrays.”

We rewrite insertionSort3 to illustrate how to sort parallel arrays. We simply add the code to move an ID

whenever a name is moved. We call it parallelSort.

public static void parallelSort(String[] list, int id[], int lo, int hi) {

//Sort the names in list[lo] to list[hi] in alphabetical order,

//ensuring that each name remains with its original id number.

for (int h = lo + 1; h <= hi; h++) {

String key = list[h];

int m = id[h]; // extract the id number

int k = h - 1; //start comparing with previous item

while (k >= lo && key.compareToIgnoreCase(list[k]) < 0) {

list[k + 1] = list[k];

id[k+ 1] = id[k]; //move up id number when we move a name

--k;

}

list[k + 1] = key;

id[k + 1] = m; //store the id number in the same position as the name

} //end for

} //end parallelSort

We test parallelSort by writing Program P1.4.

Program P1.4

import java.util.*;

public class ParallelSort {

final static int MaxNames = 8;

public static void main(String[] args) {

String name[] = {"Graham, Ariel", "Perrott, Chloe",

"Charles, Kandice", "Seecharan, Anella", "Reyes, Aaliyah",

"Graham, Ashleigh", "Reyes, Ayanna", "Greaves, Sherrelle" };

int id[] = {3050,2795,4455,7824,6669,5000,5464,6050};

parallelSort(name, id, 0, MaxNames - 1);

name id

2 Charles, Kandice 4455

3 Seecharan, Anella 7824

4 Reyes, Aaliyah 6669

5 Graham, Ashleigh 5000

6 Reyes, Ayanna 5464

7 Greaves, Sherrelle 6050

3050

2795

Graham, Ariel

Perrott, Chloe

Figure 1-1. Two arrays with related information

Chapter 1 ■ Sorting, SearChing, and Merging

System.out.printf("\nThe sorted names and IDs are\n\n");

for (int h = 0; h < MaxNames; h++)

System.out.printf("%-20s %d\n", name[h], id[h]);

} //end main

// parallelSort goes here

} //end class ParallelSort

When Program P1.4 was run, it produced the following output:

The sorted names and IDs are

Charles, Kandice 4455

Graham, Ariel 3050

Graham, Ashleigh 5000

Greaves, Sherrelle 6050

Perrott, Chloe 2795

Reyes, Aaliyah 6669

Reyes, Ayanna 5464

Seecharan, Anella 7824

We note, in passing, that if we have several sets of related items to process, storing each set in a separate array

would not be the best way to proceed. It would be better to group the items in a class and work with the group as we

would a single item. We’ll show you how to do this in Section 2.14.

1.6 Binary Search

Binary search is a fast method for searching a list of items for a given one, providing the list is sorted (either ascending

or descending). To illustrate the method, consider a list of 13 numbers, sorted in ascending order and stored in an

array num[0..12].

Suppose we want to search for 66. The search proceeds as follows:

1. We find the middle item in the list. This is 56 in position 6. We compare 66 with 56. Since 66

is bigger, we know that if 66 is in the list at all, it must be after position 6, since the numbers

are in ascending order. In our next step, we confine our search to locations 7 to 12.

2. We find the middle item from locations 7 to 12. In this case, we can choose either item 9 or

item 10. The algorithm we will write will choose item 9, that is, 78.

3. We compare 66 with 78. Since 66 is smaller, we know that if 66 is in the list at all, it must be

before position 9, since the numbers are in ascending order. In our next step, we confine

our search to locations 7 to 8.

4. We find the middle item from locations 7 to 8. In this case, we can choose either item 7 or

item 8. The algorithm we will write will choose item 7, that is, 66.

5. We compare 66 with 66. Since they are the same, our search ends successfully, finding the

required item in position 7.

Chapter 1 ■ Sorting, SearChing, and Merging

Suppose we were searching for 70. The search will proceed as described above until we compare 70 with 66

(in location 7).

Since • 70 is bigger, we know that if 70 is in the list at all, it must be after position 7, since the

numbers are in ascending order. In our next step, we confine our search to locations 8 to 8.

This is just one location.

We compare • 70 with item 8, that is, 72. Since 70 is smaller, we know that if 70 is in the list at

all, it must be before position 8. Since it can’t be after position 7 and before position 8, we

conclude that it is not in the list.

At each stage of the search, we confine our search to some portion of the list. Let us use the variables lo and hi

as the subscripts that define this portion. In other words, our search will be confined to num[lo] to num[hi].

Initially, we want to search the entire list so that we will set lo to 0 and hi to 12, in this example.

How do we find the subscript of the middle item? We will use the following calculation:

mid = (lo + hi) / 2;

Since integer division will be performed, the fraction, if any, is discarded. For example, when lo is 0 and hi is 12,

mid becomes 6; when lo is 7 and hi is 12, mid becomes 9; and when lo is 7 and hi is 8, mid becomes 7.

As long as lo is less than or equal to hi, they define a nonempty portion of the list to be searched. When lo is

equal to hi, they define a single item to be searched. If lo ever gets bigger than hi, it means we have searched the

entire list and the item was not found.

Based on these ideas, we can now write a function binarySearch. To be more general, we will write it so that the

calling routine can specify which portion of the array it wants the search to look for the item.

Thus, the function must be given the item to be searched for (key), the array (list), the start position of the

search (lo), and the end position of the search (hi). For example, to search for the number 66 in the array num, above,

we can issue the call binarySearch(66, num, 0, 12).

The function must tell us the result of the search. If the item is found, the function will return its location. If not

found, it will return -1.

public static int binarySearch(int key, int[] list, int lo, int hi) {

//search for key from list[lo] to list[hi]

//if found, return its location; otherwise, return -1

while (lo <= hi) {

int mid = (lo + hi) / 2;

if (key == list[mid]) return mid; // found

if (key < list[mid]) hi = mid - 1;

else lo = mid + 1;

}

return -1; //lo and hi have crossed; key not found

}

If item contains a number to be searched for, we can write code as follows:

int ans = binarySearch(item, num, 0, 12);

if (ans == -1) System.out.printf("%d not found\n", item);

else System.out.printf("%d found in location %d\n", item, ans);

If we want to search for item from locations i to j, we can write the following:

int ans = binarySearch(item, num, i, j);

剩余321页未读，继续阅读

kooer

粉丝: 2
资源: 20

Java进阶：排序、搜索与合并

Advanced Topics in Java Core Concepts in Data Structures

Advanced_Topics_in_Java_Core_Concepts_in_Data_Structures

《Programming in Java Second Edition》高清完整英文PDF版

Java Concurrency In Practice

Java Concurrency in Practice

Core Java Volume II Advanced Features__10th edition

Java Concurrency in Practice JAVA并发编程实践(中英文版)

Java in Two Semesters Featuring JavaFX, 4th Edition

For Dummies. Java All-in-One Desk Reference(《傻瓜系列：Java完全桌面参考手册》)

Java - The Well-Grounded Java Developer

最新资源