数据结构与算法系列（2）基础排序算法

数据结构与算法系列（2）基础排序算法2014-04-26 博客园追忆前言

在计算机中实现存储数据最普遍的两种操作就是排序和查找。这是从计算机产业初始就已经确认的了。这意味着排序和查找也是计算机科学领域最值得研究的两种操作。本书提到的许

多数据结构的主要设计目的就是为了使排序和/或查找更加简单，同时也是为了数据在结构内的存储更加有效。

本章会介绍有关数据排序和查找的基础算法。这些算法仅依赖数组作为数据结构，而且所采用的 “高级”编程技术只是递归。本章还介绍了用来非正式分析不同算法之间速度与效率的方法，此方法贯穿全书。

1.排序算法

人们在日常生活中所接触到的绝大多数数据都是经过排序的。比如，按照字母顺序查询字典中的定义。或者按照名字的字母顺序在电话本中查询电话号码。再或者邮局会按照下列几个

步骤对邮件进行排序分发：即首先按照邮政编码，然后再按照街道名称，最后还要按照姓名。排序在数据处理中是十分基础的过程，因而值得认真学习研究。正如先前提到的那样，这里对不同排序算法的操作有非常少量的分析研究。尽管已经对一些非常古老的算法做了改进，但是仍然应该先学习几种简单的排序算法。这些简单算法就是插入排序算法、冒泡排序算法以及选择排序算法。这些算法的每一种都很容易理解和实现。对于任意情况而言这些算法不是最好的全面算法，但是对于少量数据集合或者其他特殊情况而言，它们是可用的最好算法。

1.1数组类测试环境

为了检验这些算法，首先需要构造一个可以实现并测试算法的测试环境。这里将构造一个类来封装数组处理的一些常规操作，即元素插入操作，元素存取访问操作，以及显示数组内容的操组。下面就是程序的代码：

在保留CArray 类以便开始检测排序和查找算法之前，还是先来讨论一下如何在CArray 类对象内实际存储数据的问题。为了更有效地说明不同排序算法是如何运行的，数组内数据需

要随机放置。最好的实现方法就是使用随机数生成器来给数组的每个元素进行赋值。在C#中用 Random 类可以产生随机数。这种类型的对象可以产生随机数。为了实例化Random 对象，需要给这个类的构造器传递一个种子。这里把这个种子看作是随机数生成器所能产生的随机数范围的上界。

下面另外看一个用CArray 类来存储数的程序，而且采用了随机数生成器来选择存储到数组内的数据：

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks; namespace Chapter2{class Program{static void Main（string[] args）{CArray nums = new CArray（10）; Random rnd = new Random（100）; for （int i = 0; i <10; i++）{nums.Insert（rnd.Next（0,100））;} nums.DisplayElements（）; Console.ReadKey（）;}}}