chapter3simplesorting中文

1、Data Structures and Algorithms with JavaChapter 3 Simple SortingSimple Sortingv一旦你创建了一个重要的数据库，你可能会想出各种各样的理由来解决它。你需要安排的名字按字母顺序排列的，学生的年级、邮编客户，房屋销售价格，在人口增长，城市，国家的国民生产总值，等等。overviewHow Would You Do It?Bubble Sort气泡排序Selection Sort选择排序Insertion Sort插入排序Sorting Objects分类对象Comparing the Simple Sorts比较简单的种类

2、How Would You Do It?v想象一下你的孩子联盟棒球队排在了场地上。该条例九名球员，外加一个额外的，已经显示出来的做法。你要安排的球员，以增加高度（在左边的最短的球员），为球队的图片。vThe three algorithms in this chapter all involve two steps, executed over and over until the data is sorted:v1. Compare two items.v2. Swap two items or copy one item.v这一章中的三种算法都涉及2个步骤，在数据被排序时执行：v1。比较2

3、项。v2。交换2项或复制一项。Bubble SortvThe bubble sort is notoriously slow, but its conceptually the simplest of the sorting algorithmsvHere are the rules youre following:1. Compare two players.2. If the one on the left is taller, swap them.3. Move one position right.4. When you reach the first sorted player, s

4、tart over at the left end of the line.APPLETv这种“泡沫排序”是众所周知的缓慢，但它的概念是最简单的排序算法以下是你的规则：v1。比较两家。v2。如果左边的一个更高，交换他们。v3。移动一个位置。v4。当你到达第一个排序的球员，开始在结束的路线。JAVA CODE FOR A BUBBLE SORTBook52INVARIANTSvIn many algorithms there are conditions that remain unchanged as the algorithm proceeds. These conditions are c

5、alled invariants.vIn the bubbleSort.java program, the invariant is that the data items to the right of outer are sorted. This remains true throughout the running of the algorithm.v在许多算法中，有条件保持不变，作为算法的收益。在许多算法中，有条件保持不变，作为算法的收益。这些条件被称为不变量。这些条件被称为不变量。v在在bubblesort.java程序，不变的是，外对数据项进程序，不变的是，外对数据项进行排序。这仍

6、然是真实的，在整个运行的算法。行排序。这仍然是真实的，在整个运行的算法。EFFICIENCY OF THE BUBBLE SORTthere will be about N2/2 comparisonsthere will be about N2/4 swaps大约有2个比较;大约有4个交换协议the bubble sort runs in O(N2) time.在阿（在阿（N）的时间内的气泡排序运行。）的时间内的气泡排序运行。当你看到那些在泡泡排序和其他排序算法中的嵌套循环时，当你看到那些在泡泡排序和其他排序算法中的嵌套循环时，你可能会怀疑一个算法在（你可能会怀疑一个算法在（2）时间内运行。

7、）时间内运行。Selection SortvThe selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2).v通过减少所需的交换数量（通过减少所需的交换数量（N），以减少的选择），以减少的选择排序的气泡排序上的选择排序减少了。不幸的是，排序的气泡排序上的选择排序减少了。不幸的是，比较的数量仍然是（比较的数量仍然是（N2）。）。A Br

8、ief Descriptionv所涉及的是通过所有的球员所涉及的是通过所有的球员和采摘（或选择，因此，该和采摘（或选择，因此，该名称的排序）最短的一个。名称的排序）最短的一个。这是最短的球员然后与左边这是最短的球员然后与左边的线端的球员交换，在位置的线端的球员交换，在位置0。现在最左边的玩家进行。现在最左边的玩家进行排序，而不需要再被移动。排序，而不需要再被移动。注意，在这个算法中，排序注意，在这个算法中，排序的玩家堆积在左边（较低的的玩家堆积在左边（较低的指标），而在泡沫排序他们指标），而在泡沫排序他们积累的权利。积累的权利。APPLETJAVA CODE FOR SELECTION SOR

9、TBook57INVARIANTvIn the selectSort.java program, the data items with indices less than or equal to outer are always sorted.v在在selectsort.java程序，数据项指标小于或等于程序，数据项指标小于或等于外总是排。外总是排。EFFICIENCY OF THE SELECTION SORTv选择排序执行相同数量的比较，作为泡沫排序：选择排序执行相同数量的比较，作为泡沫排序：N*（1）/ 2。v对于大的值，比较次将占主导地位，所以我们不对于大的值，比较次将占主导地位，所

10、以我们不得不说，选择排序运行在阿（得不说，选择排序运行在阿（N2）的时间，正如）的时间，正如泡沫般的。泡沫般的。v然而，这无疑是更快因为很少有互换。对于较小然而，这无疑是更快因为很少有互换。对于较小的值，它可能实际上是相当快，特别是如果交换的值，它可能实际上是相当快，特别是如果交换时间是远远大于比较时间。时间是远远大于比较时间。Insertion Sortv在大多数情况下，插入排序是本章中描述的基本在大多数情况下，插入排序是本章中描述的基本类型的最好的部分。它仍然执行在（类型的最好的部分。它仍然执行在（2）的时间，）的时间，但它的约两倍的速度快的泡沫排序和速度比正常但它的约两倍的速度快的泡沫排

11、序和速度比正常情况下的选择排序。情况下的选择排序。APPLETJAVA CODE FOR INSERTION SORTBook62INVARIANTS IN THE INSERTION SORTvAt the end of each pass, following the insertion of the item from temp, the data items with smaller indices than outer are partially sorted.v每一关结束后，从临时性的项目的插入，数据项每一关结束后，从临时性的项目的插入，数据项与较小的指标比外部部分排序。与较小的指

12、标比外部部分排序。EFFICIENCY OF THE INSERTION SORTvHow many comparisons and copies does this algorithm require?拷贝数与比较的数量大致相同。然而，一个拷贝并不是一个拷贝数与比较的数量大致相同。然而，一个拷贝并不是一个交换，所以对于随机数据，该算法运行的速度快两倍的泡沫交换，所以对于随机数据，该算法运行的速度快两倍的泡沫排序和更快的选择排序。排序和更快的选择排序。comparisons :bubble sort: N*(N1)/2selection sort : N*(N1)/2vIn any case,

13、 like the other sort routines in this chapter, the insertion sort runs in O(N2) time for random data.vFor data that is already sorted or almost sorted, the insertion sort does much better.In this case the algorithm runs in O(N) time.vHowever, for data arranged in inverse sorted order, every possible

14、 comparison and shift is carried out, so the insertion sort runs no faster than the bubble sort.v在任何情况下，像其他排序例程，在本章中，插入排序在任何情况下，像其他排序例程，在本章中，插入排序运行在阿（运行在阿（N）的随机数据的时间。）的随机数据的时间。v对于已排序或几乎排序的数据，插入排序会更好。在这对于已排序或几乎排序的数据，插入排序会更好。在这种情况下，该算法在运行种情况下，该算法在运行O（N）时间。）时间。v然而，对于按顺序排列的数据，每一个可能的比较和移然而，对于按顺序排列的数据，每一个

15、可能的比较和移位都进行了，所以插入排序的运行速度比不快。位都进行了，所以插入排序的运行速度比不快。Sorting ObjectsvFor simplicity weve applied the sorting algorithms weve looked at thus far to a primitive data type: double. However, sorting routines will more likely be applied to objects than primitive types.v为简单起见，我们已经应用了排序算法，我们已为简单起见，我们已经应用了排序算法，

16、我们已经看到了迄今为止的原始数据类型：双。然而，经看到了迄今为止的原始数据类型：双。然而，排序例程将更容易被应用于对象比原始类型。排序例程将更容易被应用于对象比原始类型。Book66STABILITYvYou want the algorithm to sort only what needs to be sorted, and leave everything else in its original order. Some sorting algorithms retain this secondary ordering; theyre said to be stable.v你需要该算法来

17、排序，只有需要进行排序，并把你需要该算法来排序，只有需要进行排序，并把一切都在它的原始顺序。一些排序算法保留此二一切都在它的原始顺序。一些排序算法保留此二次排序，他们说是稳定的。次排序，他们说是稳定的。Comparing the Simple Sortsv 如果你没有使用该算法的书，那就可能是没有用的。这个如果你没有使用该算法的书，那就可能是没有用的。这个泡泡排序很简单，你可以把它写在内存中。即使如此，它泡泡排序很简单，你可以把它写在内存中。即使如此，它的实际应用，只有当数据量小。的实际应用，只有当数据量小。v 该选择排序减少了交换的数量，但是比较的数量仍然很高。该选择排序减少了交换的数量，但

18、是比较的数量仍然很高。它可能是有用的，当数据量是小的和交换数据的项目是非它可能是有用的，当数据量是小的和交换数据的项目是非常耗时的比较，比较它们。常耗时的比较，比较它们。v 插入排序是最通用的三个，是最好的赌注在大多数情况下，插入排序是最通用的三个，是最好的赌注在大多数情况下，假设数据量小或数据几乎排序。对于大数据量，快速排序假设数据量小或数据几乎排序。对于大数据量，快速排序通常被认为是最快的方法；通常被认为是最快的方法；v我们比较了排序算法的速度。对任何算法的另一我们比较了排序算法的速度。对任何算法的另一个考虑是，它需要多少内存空间。本章中的所有个考虑是，它需要多少内存空间。本章中的所有三个

19、算法都进行了它们的排序，这意味着，在初三个算法都进行了它们的排序，这意味着，在初始阵列的旁边，很少需要额外的内存。所有的类始阵列的旁边，很少需要额外的内存。所有的类需要一个额外的变量来存储一个项目暂时当它被需要一个额外的变量来存储一个项目暂时当它被换。换。Summaryv本章中的排序算法均假定一个数组作为数据存储本章中的排序算法均假定一个数组作为数据存储结构。结构。v排序包括比较数组中的数据项的键和移动的项目排序包括比较数组中的数据项的键和移动的项目（实际上是引用的项目），直到他们的排序顺序。（实际上是引用的项目），直到他们的排序顺序。v本章中的所有算法都在本章中的所有算法都在O（N2）时间内

20、执行。尽）时间内执行。尽管如此，一些人可能比其他人快。不变的是一个管如此，一些人可能比其他人快。不变的是一个在算法运行时保持不变的情况在算法运行时保持不变的情况.v泡沫排序是最有效的，但最简单的排序。泡沫排序是最有效的，但最简单的排序。v插入排序是本章所描述的最常用的（插入排序是本章所描述的最常用的（N）类型的）类型的插入类型。插入类型。v一种是稳定的，如果元素的顺序与相同的密钥被一种是稳定的，如果元素的顺序与相同的密钥被保留。保留。v在本章中，没有一个比一个单一的临时变量，除在本章中，没有一个比一个单一的临时变量，除了原来的数组了原来的数组v1 1 计算机排序算法与人类排序相比较，它的局限计

21、算机排序算法与人类排序相比较，它的局限性是性是：vA A 人类擅长发明新算法。人类擅长发明新算法。vB B 计算机只能处理数量固定的数据。计算机只能处理数量固定的数据。vC C 人类知道什么需要排序，而计算机不知道人类知道什么需要排序，而计算机不知道vD D 计算机一次只能比较两件东西。计算机一次只能比较两件东西。v2 2 冒泡排序算法在哪两者之间交替进行：冒泡排序算法在哪两者之间交替进行：vA A 比较和交换比较和交换vB B 移动和复制移动和复制vC C 移动和比较移动和比较vD D 复制和比较复制和比较v3 3 选择排序中选择排序中vA A 最大的关键字聚集到左边最大的关键字聚集到左边(

22、 (较小的下标较小的下标) )。vB B 最小的关键字被重复的发现。最小的关键字被重复的发现。vC C 为了将每个数据项插入到正确排序的位置，很为了将每个数据项插入到正确排序的位置，很多数据项将被移动多数据项将被移动vD D 有序的数据项聚集到右边。有序的数据项聚集到右边。v4 4 插入排序中，文中描述的插入排序中，文中描述的“被标记的队员被标记的队员”对对应于应于insertSort.avainsertSort.ava中的哪个变量中的哪个变量vA inA invB outB outvC tempC tempvD aoutD aoutv5.5.在插入排序中，在插入排序中，“局部有序局部有序”是

23、指：是指：vA A 一些数据项已经排好序了一些数据项已经排好序了, ,但它们可能需要被移但它们可能需要被移动。动。vB B 大部分数据项已在它们最终排序的位置了，但大部分数据项已在它们最终排序的位置了，但仍有一些需要排序仍有一些需要排序vC C 只有一些数据项有序。只有一些数据项有序。vD D 组内的数据项已经排好序，而组外面的数据项组内的数据项已经排好序，而组外面的数据项需要插入到组中来需要插入到组中来v6 6在插入排序中，一个数据项被插入到局部有序在插入排序中，一个数据项被插入到局部有序的组合后，它将的组合后，它将vA A 永远不会再移动。永远不会再移动。vB B 永远不会向左边移动。永远不会向左边移动。vC C 经常被移出这个组。经常被移出这个组。vD D 发现这组的数据项不断减少发现这组的数据项不断减少。v7 稳定性是指：稳定性是指：vA 在排序中排除有次关键字的项。在排序中排除有次关键字的项。vB 在对州进行排序时，每个州的城市还要求按人在对州进行排序时，每个州的城市还要求按人口递增有序口递增有序vC 让相同的名配相同的姓。让相同的名配相同的姓。vD 数据项按照主关键字有序，不考虑次关键字。数据项按照主关键字有序，不考虑次关键字。v8 简单排序算法中的两个基本操作是简单排序算法中