本文共 2509 字，大约阅读时间需要 8 分钟。

The two most common operations performed on data stored in a computer

are sorting and searching. This has been true since the beginning of the computing industry, which means that sorting and searching are also two of the most studied operations in computer science. Many of the data structures discussed in this book are designed primarily to make sorting and/or searching easier and more efficient on the data stored in the structure. This chapter introduces you to the fundamental algorithms for sorting and searching data. These algorithms depend on only the array as a data structure and the only “advanced” programming technique used is recursion. This chapter also introduces you to the techniques we’ll use throughout the book to informally analyze different algorithms for speed and efficiency.

在计算机中数据存取最常用的两个操作是查找和排序。从计算机工业最开始就是如此。

意思是说计算机科学中查找和排序是被研究最多的两种操作。本书中很多数据都是为使查找和排序更简单有效。

本章将介绍查找和排序算法的内涵，只有当数组作为一种数据结构并且使用了递归时才依赖这些算法。

本章还介绍了一种分析各种不同算法的速度和效率的技术。

SORTING ALGORITHMS

Most of the data we work with in our day-to-day lives is sorted. We look up definitions in a dictionary by searching alphabetically. We look up a phone number by moving through the last names in the book alphabetically. The post office sorts mail in several ways—by zip code, then by street address, and then by name. Sorting is a fundamental process in working with data and deserves close study. As was mentioned earlier, there has been quite a bit of research performed on different sorting techniques. Although some very sophisticated sorting algorithms have been developed, there are also several simple sorting algorithms you should study first. These sorting algorithms are the insertion sort, the bubble sort, and the selection sort. Each of these algorithms is easy to understand and easy to implement. They are not the best overall algorithms for sorting by any means, but for small data sets and in other special circumstances, they are the best algorithms to use.

排序算法

生活中日复一日的工作是有序的，我们在字典中按abc查找内容，在电话中按姓名查找号码，邮局按邮编发信。可见排序与人活息息相关。

前面提到过，关于排序技术的研究很多，尽管一些复杂的算法已经被开发出来，但是一些你得先学会简单的算法。

这些算法是 插入排序，冒泡排序，选择排序，这些都很容易理解，实现也很简单，但某种意义上不是最好的算法，

但在数据量很小的时候这些算法都挺不错的。

An Array Class Test Bed

To examine these algorithms, we will first need a test bed in which to implement and test them.We’ll build a class that encapsulates the normal operations performed with an array—element insertion, element access, and displaying the contents of the array. Here’s the code:

一个数组类的测试框架

我们需要用一个测试去检验这些算法。这里建立了一个类并且实现了一些常用的操作：插入，存取，显示元素

转载地址：http://lalgb.baihongyu.com/