数组排序方法概述|数组排序方法
时间：2018-12-29 03:39:02 来源：雅意学习网 本文已影响 人 
摘 要： 数组排序是程序设计的重要内容，本文主要对冒泡排序法、快速排序法、简单选择排序法、直接插入法进行简单讨论，并从时间复杂度、空间复杂度、稳定性方面加以论述。在这几种方法分析、比较的基础上，可以得知没有一种方法是最优的，应根据实际情况进行选择。
关键词： 数组排序 算法 时间复杂度
数组排序是C语言中的一项重要内容，所谓排序就是将一组杂乱无章的数据按照大小顺序排列，包括整型、实型、字符型及字符串的排序。排序的方法有很多种，常用的有交换法、选择法、插入法。其中交换法包括冒泡排序法和快速排序法。
衡量算法的两个重要指标是时间复杂度和空间复杂度，本文主要从时间复杂度的角度对算法进行分析。
一、交换法
1.冒泡排序法［１］
（1）冒泡排序法的基本思想
将相邻两个数进行比较，若满足条件升序（或降序）时，就不需要交换，反之，就要交换。例如：对于一个数组a［n］进行降序排列运用冒泡法分析如下：首先把a与a进行比较，若a＜a则交换，反之不交换；其中i=1，2，…n-1。进行第一回比较后就把最大的数放在a的位置；第二回比较就从a开始比较，比较的结果就把次最大的数放在a的位置上。如此进行下去，可以推知，对n个数要比较n-1回，才能使这n个数按大小顺序排列。在第一回要进行两个数之间的比较，共比较n-1次，第二回比较n-2次……第n-1回比较1次。
（2）用C语言实现算法
void fun(int a，int n)
{int i，j，t;
for(j=0;j＜n-1;j++)/*进行n-1次循环，实现n-1趟比较*/
for(i=0;i＜n-j;i++)/*在每一趟中进行n-j次比较*/
if(a［i］＜a［i+1］) /*相邻两元素比较*/
{t=a［i］; a［i］=a［i+1］; a［i+1］=t;} }
（3）算法分析
②空间复杂度。因为只用一个辅助单元，所以为O(1)。
③稳定性。从排序过程来看，要对相邻元素交换，因此是稳定的排序方法。
2.快速排序［２］
（1）快速排序的基本思想
任取待排序列中的元素作为基准(一般取第一个元素)，通过一趟排序，将待排序元素分为左右两个序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字都大于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。
例如数组a有n元素要对它进行排序，low为数组的低端下标，high为数组的高端下标，取a［low］为基准元素i的初值为low，j的初值为high。为了实现一次划分，首先让j从它的初值开始一次向前取值，并将每一元素a［j］的关键字同a［i］进行比较，直到a［j］的关键字小于a［i］的关键字时交换a［j］与a［i］的值，使得关键字较小交换到左区间中。然后让i从i+1开始，依次向后取值，并使每一元素a［i］的关键字同a［j］的关键字进行比较，当a［i］的关键字大于a［j］的关键字时，交换a［i］与a［j］的值，使得关键字较大的元素交换到右区间中。接着让i从j-1开始，依次向前取值，重复此过程，直到i等于j为止，此位置就是基准元素存放的位置，完成一次规划过程。划分后，待排序列被分为两个子序列，左子序列的元素的关键字均小于基准元素的关键字，右子序列元素的关键字均大于等于基准元素的关键字。重复以上过程，直到整个序列有序。
（2）用C语言实现算法
void fun(int a，int low，high)
{ int i=low，j=high;
int t=a［low］；/*取第一个元素为基准元素*/
while(i＜j){
while(i＜j&&t＜＝a［j］)j--；/*在数组右端扫描*/
if(i＜j) {a［i］=a［j］； i++；}
while(i＜j&&a［i］＜t)i++；/*在数组的左端扫描*/
if(i＜j) { a［j］=a［i］；j--；} }
a［i］=t；
if(low＜i) fun(a，low，i-1)；
if(i＜high) fun(a，j+1，high)；}
（3）算法分析［３］
③稳定性。从排序结果可以看出：在排序过程中涉及不相邻元素间的交换，所以快速排序是一种不稳定的排序方法。
二、选择排序
1.简单选择排序方法［４］
（1）简单选择排序的基本思想
对n个待排序的数列a，a，…，a［n-1］；进行n-1回扫描，第i回扫描数组a［n］中的n-i-1个元素，并从中选出最小关键字的元素与第i个元素交换位置(1≤i≤n-1)。重复这样n-1回扫描，最后得到的序列就是有序的。
例如：数组a［n］要按升序排列，第一回是a与a，a，…，a［n-1］相比较，找出最小的元素放在a的位置，第二回就是a与a，a…，a［n-1］比较，把最小的元素放在a的位置，在第i回就是a［i-1］与a［i］，a［i+1］，…，a［n-1-i］相比较，把最小的元素放在a［i-1］中，直到整个数组有序。
（2）算法实现
void fun(int a，int n)
{int i，j，k，t；
for (i=0；i＜n-1；i++) { k=i；
for(j=i+1；j＜n；j++)
if(a［j］＜a［k］)k=j； t=a［k］；a［k］=a［i］；a［i］=t；}
（3）算法分析
②空间复杂度。在排列过程中需要一个辅助空间，所以空间复杂度为O(1)。
③稳定性。相同的关键字的元素在排序后其前后顺序有改变的可能性，所以简单选择排序是不稳定的排序方法。
三、插入法
1.直接插入排序［５］的基本思想
顺序地把待排序的元素按其关键字值的大小插入到已经排列有序的子集合的合适的位置上，使子集合中的数据元素个数逐渐从只有一个不断的增加。当子集合等于集合时，算法结束。
例如：设n个元素的数组a，初始时子集合a有序，第一次循环只要比较a和a，若a＜a，说明有序直接把a插到a后面，否则把a插到a前面这样子集合就增大为2，然后把a在插入前面的子集合中，使子集合也有序，这时子集合增大为3，重复上述过程，直到把a［n-1］插入到前面的子集合中，这时子集合等于集合，算法结束。
2.算法实现
void fun (int a，int n)
{int i， j，t；for (i=0；i＜n-1；i++)
{ t=a［i+1］；j=i；
while (j＞－1&&t＜a［j］)
{ a［j+1］=a［j］；j--； }
a［j+1］=t；} }
3.算法分析
(1)时间复杂度
(2)空间复杂度
在排序的过程中要用到一个辅助空间，所以空间复杂度为O(1)。
(3)稳定性
在排序过程中相同的关键字的元素在排序后顺序保持不变，所以直接插入排序是一种稳定的排序方法。
四、各种排序方法的性能比较
五、选择排序方法的规则［６］
1.影响排序方法的因素
待排序的元素的数目、记录本身信息量的大小、排序方法的稳定性、辅助空间的大小。
2.在选择排序方法时
首先应考虑排序的稳定性，其次考虑待排序记录数n的大小，从而选取合适的排序方法。
参考文献：
［1］谭浩强.C语言程序设计（第三版）.清华大学出版社，P134，135.
［2］张伍荣，王军武.全国计算机等级考试实用应试教程―二级公共基础知识.电子工业出版社.
［3］朱战立.数据结构――使用C语言（第三版）.西安交通大学出版社，P249，250.
［4］李可清.数据结构――C语言描述.华中科技大学出版社，P237，238.
［5］朱战立.数据结构――使用C语言（第三版）.西安交通大学出版社，P236-239.
［6］欺庆巴拉.数据结构（C语言描述）.中国水利水电出版社，P214，215.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
