本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分，共16章。书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。

本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分，共16章。第一部分“基础知识” (第1~2章) 介绍基本算法分析原理。第二部分“数据结构” (第3~5章) 讲解算法分析中必须掌握的数据结构知识，主要包括基本数据结构、抽象数据结构、递归和树。第三部分“排序” (第6~11章) 按章节顺序分别讨论基本排序方法 (如选择排序、插入排序、冒泡排序、希尔排序等) 、快速排序方法、归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊目的排序方法，并比较了各种排序方法的性能特征。第四部分“搜索” (第12~16章) 在进一步讲解符号表、树等抽象数据类型的基础上，重点讨论哈希方法、基数搜索以及外部搜索方法。

书中提供了用C语言描述的完整算法源程序，并且配有丰富的插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。

本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。

Fundamentals

Chapter I~ Introduction

Algorithms~ 4

A Sample Problem--Connectivity ~ 6

Union-Find Algorithms~ 11

Perspective~ 22

Summary of Topics ~ 23

Chapter 2~ Principles of Algorithm Analysis

Implementation and Empirical Analysis~ 28

Analysis of Algorithms~ 33

Growth of Functions~ 36

Big-Oh notation ~ 44

Basic Recurrences ~ 49

Examples of Algorithm Analysis~ 53

Guarantees, Predictions, and Limitations ~ 59

Chapter 3~ Elementary Data Structures

Building Blocks~ 70

Arrays~ 82

Linked Lists ~ 90

Elementary List Processing~ 96

Memory Allocation for Lists ~ 105

Strings~ 109

Compound Data Structures ~ 115

Chapter 4~ Abstract Data Types

Abstract Objects and Collections of Objects~ 131

Pushdown Stack ADT ~ 135

Examples of Stack ADT Clients ~ 138

Stack ADT Implementations ~ 144

Creation of a New ADT~ 149

FIFO Queues and Generalized Queues ~ 153

Duplicate and Index Items ~ 161

First-Class ADTs ~ 165

Application-Based ADT Example ~ 178

Perspective~ 184

Chapter 5~ Recursion and Trees

Recursive Algorithms ~ 188

Divide and Conquer ~ 196

Dynamic Programming ~ 208

Trees ~ 216

Mathematical Properties of Trees ~ 226

Tree Traversal~ 230

Recursive Binary-Tree Algorithms~ 235

Graph Traversal ~ 241

Perspective ~ 247

Chapter 6~ Elementary Sorting Methods

Rules of the Game~ 255

Selection Sort~ 261

Insertion Sort ~ 262

Bubble Sort~ 265

Performance Characteristics of Elementary Sorts ~ 267

Shellsort ~ 273

Sorting Other Types of Data ~ 281

Index and Pointer Sorting ~ 287

Sorting of Linked Lists ~ 294

Key-Indexed Counting~ 298

Chapter 7~ Quicksort

The Basic Algorithm ~ 304

Performance Characteristics of Quicksort~ 309

Staik Size ~ 313

Small Subfiles~ 316

Median-of-Three Partitioning ~ 319

Duplicate Keys ~ 324

Strings and Vectors ~ 327

Selection ~ 329

Chapter 8~ Merging and Mergesort

Two-Way Merging~ 336

Abstract In-place Merge~ 339

Top-Down Mergesort ~ 341

Improvements to the Basic Algorithm~ 344

Bottom-Up Mergesort~ 347

Performance Characteristics of Mergesort ~ 351

Linked-List Implementations of Mergesort ~ 354

Recursion Revisited~ 357

Chapter 9~ Priority Queues and Heapsort

Elementary Implementations ~ 365

Heap Data Structure~ 368

Algorithms on Heaps ~ 371

Heapsort~ 376

Priority-Queue ADT~ 383

Priority Queues for Index Items ~ 389

Binomial Queues~ 392

Chapter 10~ Radix Sorting

Bits, Bytes, and Words ~ 405

Binary Quicksort ~ 409

MSD Radix Sort ~ 413

Three-Way Radix Quicksort~ 421

LSD Radix Sort~ 425

Performance Characteristics of Radix Sorts ~ 428

Sublinear-Time Sorts ~ 433

Chapter 11~ Special-Purpose Sorts

Batcher's Odd-Even Mergesort ~ 441

Sorting Networks ~ 446

External Sorting~ 454

Sort-Merge Implementations~ 460

Parallel Sort/Merge~ 466

Searching

Chapter 12~ Symbol Tables and BSTs

Symbol-Table Abstract Data Type ~ 479

Key-Indexed Search~ 485

Sequential Search~ 489

Binary Search ~ 497

Binary Search Trees (BSTs) ~ 502

Performance Characteristics of BSTs ~ 508

Index Implementations with Symbol Tables ~ 511

Insertion at the Root in BSTs~ 516

BST Implementations of Other ADT Functions~ 519

Chapter 13~ Balanced Trees

Randomized BSTs ~ 533

Splay BSTs ~ 540

Top-Down 2-3-4 Trees ~ 546

Red-Black Trees ~ 551

Skip Lists ~ 561

Performance Characteristics ~ 569

Chapter 14~ Hashing

Hash Functions ~ 574

Separate Chaining ~ 583

Linear Probing ~ 588

Double Hashing ~ 594

Dynamic Hash Tables ~ 599

Perspective~ 603

Chapter 15~ Radix Search

Digital Search Trees~ 610

Tries ~ 614

Patricia Tries~ 623

Multiway Tries and TSTs ~ 632

Text String Index Algorithms~ 648

Chapter 16~ External Searching

Rules of the Game ~ 657

Indexed Sequential Access~ 660

B Trees ~ 662

Extendible Hashing ~ 676

Perspective~ 688

Index