数据结构之排序算法详解(含代码).doc

《数据结构之排序算法详解(含代码).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、C/C++版数据结构之排序算法      今天讨论下数据结构中的排序算法。排序算法的相关知识：（1）排序的概念：所谓排序就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。（2）稳定的排序方法：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的。相反，如果发生改变，这种排序方法不稳定。（3）排序算法的分类（分为5类）：插入排序、选择排序、交换排序、归并排序和分配排序。（4）排序算法两个基本操作：<1>比较关键字的大小。       

2、                              <2>改变指向记录的指针或移动记录本身。具体的排序方法：插入排序<1>插入排序（InsertionSort）的思想：每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子记录中的适当位置，直到全部记录插入完成为止。<2>常用的插入排序方法有直接插入排序和希尔排序。（1）直接插入排序<1>算法思路：把一个记录集（如一个数组）分成两部分，前半部分是有序区，后半部分是无序区；有序区一开始有一个元素r[0],无序区一开始是从r[1]到之后的所有元素；然后每次

3、从无序区按顺序取一个元素r[i],拿到有序区中由后往前进行比较，每次比较时，有序区中比r[i]大的元素就往后移动一位，直到找到小于r[i]的元素，这时r[i]插到小元素的后面，则完成一趟直接插入排序。如此反复，从无序区不断取元素插入到有序区，直到无序区为空，则插入算法结束。<2>算法演示：//直接插入排序：#includeusingnamespacestd;voidInsertSort(intr[],intn);intmain(){intr[]={24,1,56,2,14,58,15,89};I

4、nsertSort(r,8);for(inti=0;i<8;i++){cout<=0;j--){r[j+1]=r[j];}r[j+1]=s;}}复制代码（2）折半插入排序<1>算法思路：我们看到在直接插入排序算法中，需要在有序区查找比r[i]的小的元素，然后插入到这个元素后面，但这里要注意这个元素

5、是从无序区算第一个比r[i]小的元素。折半插入排序就是在有序区折半查找这个元素。<2>算法演示： //折半插入排序#includeusingnamespacestd;voidBinInsertSort(intr[],intn);intmain(){intr[]={53,34,76,23,55,28,63,88,34,66};BinInsertSort(r,10);for(inti=0;i<10;i++){cout<

6、nsertSort(intr[],intn){for(inti=1;i=high+1;j--){r[j+1]=r[j];}r[high+1]=s;//r[high]是要找的元素}}复制代码（3）希尔排序（ShellSort）<1>算法思路：把整个记录近一

7、个步长step(一般取记录长度的1/2)，分成step个组，再分别对每个级进行直接插入排序；然后再把整个记录近一个新的步长（一般取step/2）分成step/2个组，再分别对每个组进行直接插入排序；如此不断的缩小步长，反复分组排序，直到步长等于1为此（步长为1则不可能再分组，1是元素之间距离的最小值）。可以看出，希尔排序实质是一种分组插入方法。<2>算法演示： //希尔排序：#includeusingnamespacestd;voidShellSort(intr[],intn);intmain(

8、){intr[]={24,1,56,2,14,58,15,89};ShellSort(r,8);for(inti=0;i<8;i++){cout<=1){for(inti=step;i