浅析排序算法

杨玉芹

摘要：本文主要关于4种排序进行了一个简单的讲解，并为每一种排序使用C/C++语言给每种排序算法相应的实现，并在最后比较了每种算法的稳定性以及时间复杂度.看本文的前提是熟悉C/C++程序设计语言。

关键词：排序；冒泡算法；插入排序；快速排序；选择排序1引言

随着计算机的不断普及，技术越来越成熟，计算机硬件以及存储设备具有局限性，提供计算机的效率成了程序员特别关注的一方向，其中排序就是其中之一。如何能在最短时间，在最节省内存的情况下，使呈任意序列的数据元素，在最快的时间得到从大到小或从小到大的序列，是程序员一直研究的问题。

本文主要是简单的讲述一下排序的几种算法，冒泡排序，插入排序，快速排序，选择排序。

2冒泡排序

冒泡排序，是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法用C语言的实现如下：

for(int i=0;i<10;i++){for(int j=i;j<10;j++){if(a[j]

3插入排序

插入排序的思路简要的描述是：将序列的元素分作有序和无序两类，然后在保持前一类有序的前提下，通过迭代将后一类元素逐一插至前一类中的适当位置。

插入排序有直接插入排序，折半插入排序，2-路插入排序和希尔排序。这里仅给出直接插入排序的实现。

算法用C++语言的实现如下：

void InsertSort(int*p,int n){int temp=0;for(int i=1;ip[i-1]){temp=p[i];p[i]=p[i-1];for(int j=i-2;temp>p[j]&&j>0;j--){p[j+1]=p[j];}p[j+1]=temp;}}}

4快速排序

快速排序的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录关键字均比另一部分记录的关键字小，则可分为对这两部分继续进行排序，已达到整个序列有序。

算法用C语言的实现如下：

int QuickSock(int*a,int Left,int Right)//算法的核心

{int Temp=a[Left];while(Left=a[Right])

{Right--;}a[Left]=a[Right];while(Left

a[Right]=a[Left];}a[Left]=Temp; return Right;}

void Repeat(int*a,int Left,int Right)

{if(Left

5选择排序

选择排序的基本思想是，每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

算法用C语言的实现如下：

void SelectSort(int*p,int n){int j=0;int temp=0;for(int k=n;k>0;k--){

for(int i=0;i

int SelectMinKey(int*q,int m){int temp =q[0];int min=0;for(int i=1;i<=m;i++)

{if(temp>q[i])temp=q[i];min=i;}}return min;}

6對比各种排序

表1

冒泡排序 插入排序 快速排序 选择排序

稳定性 稳定 稳定 稳定 不稳定

时间复杂度 O(n^2) O(n^2) O(n^2) O(n^2)

[参考文献]

[1]严蔚敏,吴伟民,编著.数据结构（C语言版）.清华大学出版社,2011年5月.

[2]邓俊辉,编著.数据结构（C++语言版）（第二版）.清华大学出版社，2011年10月.

[3]Mark Allen Weiss,著.数据结构与算法分析——C语言描述.机械工业出版社，2011年10月.

[4]百度百科知识.