C语言中选择法排序的应用实现

论文总字数：10217字

摘 要

排序是计算机算法编程设计中的重要步骤，在计算机的数据处理运算中，占据非常重要的地位。选择法排序是计算机算法编程众多排序方法中的一种，它具有操作简单而且排序有效的特点。本论文将详细讨论选择法排序在 C语言中的三种基本实现方法：简单选择法排序，树形选择法排序，堆选择法排序，以及对这三种排序方法的时间复杂度和空间复杂度进行比较和分析讨论，分析选择排法排序在C语言中的排序利弊。

关键词：选择法排序，简单选择法排序，树形选择法排序，堆选择法排序，C语言

Abstract：Sorting algorithm is an important step in computer programmed , it occupies a very important position in the data processing operation of the computer. Selection Sort method is a computer programming algorithm in one of the many sorting method, which is simple and effective sorting features. In this paper, we will discuss the selection method to sort three kinds of basic C language implementation in detail: select sort, tree select sort, heap select sort , analyze and discuss this three kinds of sorting methods’ space complexity and time complexity , analyze select rows sorting in C language ordering the pros and cons.

Keywords：select sort , simply select sort, tree select sort,heap select sort, C languages

目 录

1 引言………………………………………………………………………… 4

2 C语言中选择法排序……………………………………………………………4

2.1选择法排序的概念………………………………………………………………5

2.2常规的选择法排序………………………………………………………………5

2.2.1简单选择法排序…………………………………………………………………6

2.2.2树形选择法排序………………………………………………………………… 6

2.2.3堆选择排序法……………………………………………………………………9

2.3选择法的比较分析…………………………………………………………………10

3选择法排序在C语言中的应用…………………………………………18

结论 ……………………………………………………………………………19

参考文献………………………………………………………………………… 20

致谢 ……………………………………………………………………………21

1 引言

排序是近代计算机编程发展过程中不可或缺的重要步骤，同时排序也是计算机编程过程中应用最频繁的操作之一。排序在计算机数据处理中也占据非常重要的作用及位置。相关资料显示，中央处理器用在数据排序上的时间超过其处理数据时间的一半^[1，2]。选择法排序、插入法排序、中值排序等都是计算机数据运算处理过程中经常使用的排序方法。选择法排序是初学者最容易学习掌握的排序方法，选择法排序的循环流程虽然与冒泡法一致，但它在循环过程中，其基本排序思想是记比较次数为第i次，则从(n-i 1)个序列中选出关键字最小的元素，排在有序序列的第i个位置，直至排序结束。选择法排序较之冒泡排序减少了元素之间的替换次数，节省了近一半的时间和空间复杂度，在排序过程中提高了排序效率。虽然选择法排序比不上快速排序法那么高效，但在掌握的难易度及使用灵活性上，它又比快速排序法占有更大优势。在该论文的正文部分，本文将注重分析讨论C语言中选择法排序的三种不同的实现方法,以及这三种方法的时间空间复杂度。

2 C语言中选择法排序

2.1 选择法排序的概念

选择法排序的运行基本原理是每比较一次就从初始序列元素中选出最小一个元素，放到排序后的第一位，直到初始序列的每一个元素都比较结束。 因为选择排序每次比较都是序列中相邻两个数比大小，若后面的元素小于前面的元素就用一个临时变量t，交换这两个元素的位置，并且用变量k记录较小元素的角标，继续用第二个数跟它的后一个元素再比大小，如果依然是后面一个元素小，则仍用临时变量t来实现元素位置的互换，用变量k记录较小元素的角标。直到一次循环结束后，就能找到最小的数的角标，此时再判断k与第一个元素的角标是否相同，如果不同，就把该元素和第一个元素互换，这样就把最小的元素放到有序序列的第一位^[3]。^]然后用同样的方法找到序列中第二小的数，跟原序列的第二个元素互换，最终得到新的有序序列。流程图见图1。

图1 选择法排序流程图

2.2 常规的选择法排序

选择法排序还可以细分为三种排序法：第一是简单排序法；第二是树形选择法排序；第三是堆选择排序法。在下面的章节中，将详细分析这三种排序方法，比较它们之间的优缺点。

2.2.1 简单选择法排序

简单选择法排序的基本排序思想是：第i趟排序从序列的后n-i 1（i=1,2,3......n-1）个元素中选择一个最小的元素，与该n-i 1个元素的前面那个元素进行位置交换，也就是与第i个位置上元素进行交换，直到i=n-1^[4]。

下面通过一个例子来介绍它的执行过程。有这样一组序列{3,6,4,2,11,10}

第一趟排序从全部元素中选出最小的一个，并将它与第一个元素交换位置。初始序列中最小的元素是2，所以将2与第一个元素3交换位置，得到序列{2,6,4,3,11,10}

剩余内容已隐藏，请支付后下载全文，论文总字数：10217字