数据结构中的排序（一）

      在大学计算机专业类的本科学生中，我想《数据结构》一定是必修课吧。而在本科阶段数据结构的最大用途莫过于写排序算法。排序分为内排序和外排序两种。

1、  内排序是针对于规模较小的数据进行处理，一般这些数据都直接存储在计算机的内存中。

2、  外排序则是针对规模较大的数据进行处理，这些数据是不能一次性存入计算机的内存的，大部分数据都存在计算机的辅存（磁盘）中。

在这里我所说的排序是指内排序。

下面我将介绍三种最常见也是最易理解最简单的排序（假定从小到大的排）。

冒泡排序、选择排序、插入排序:尽管这三种代码简单易懂而且容易实现，但是如果要处理的数据比较多，你就会发现他们慢得令人无法忍受。可是在某些情况下这些简单的算法也许就是你没有想到的最好的算法。

下面为了描述方便用数据：42,20,17,13,28,14,23,15来说明

其UML图描述：SortUML.PNG

 

1、  冒泡排序（BubbleSort）

冒泡排序在有些书中也称为起泡排序，因其排序方法过程像是气泡从水底向上冒。气泡排序包括一个简单的双重for语句。第一个for循环表示比较趟数，第二个for则是两个相邻的数据进行比较，如果前面数据关键值大于后面的关键值，这两个数据则进行交换。

其算法代码如下:

 

 

 

 

//冒泡排序实现
template<class Elem>
void Sort<Elem>::BubbleSort()
{
	int i,j;
	int flag;
	for(i=0;i < Size;i++)
	{    
		for(j=0;j < Size-i-1;j++)
		{
			if(Data[j]>Data[j+1])
			{
				int tem = Data[j];
				Data[j] = Data[j+1];
				Data[j+1] = tem;
			}
		}
	}
}

 

 

数据演示：BubbleSort.png

 

 

其算法时间复杂度很容易看出

2、  插入排序（InserSort）

插入排序逐个处理待排序的数据记录，每个新记录与前面已经排好的子序列进行比较，并将它插入合适的位置

其代码如下：

//插入排序实现
template<class Elem>
void Sort<Elem>::InsertSort()
{
	for(int i=1;i<Size;i++)
	{
		for(int j=i;j>0;j--)
		{
			if(Data[j]<Data[j-1])
			{
				int tem = Data[j];
				Data[j]=Data[j-1];
				Data[j-1]=tem;
			}
		}
	}
}

  

图示演示：InsertSort.png

 

其算法时间复杂度：

选择排序（SelectSort）

选择排序是第i次选出该组数据中第i小的元素数据，并将它放在数组的第i个元素。换句话说，选择排序就是依次找出待排序数据中最小的数，并把他们按从前到后的顺序放置。其代码：

  

//选择排序的实现
template<class Elem>
void Sort<Elem>::SelectSort()
{
	for(int i = 0;i < Size-1;i++)
	{
		int minIndex = i;
		for(int j = i+1;j<Size;j++)
		{
			if(Data[j]<Data[minIndex])
			{
				minIndex = j;
			}
		}
		if(minIndex != i)
		{
			int tem = Data[i];
			Data[i] = Data[minIndex];
			Data[minIndex] = tem;
		}
	}
}

 

 

 

其图示表示：SelectSort.png

 

其算法时间复杂度也为

其实按算法角度来说，上面的冒泡排序程序还可以得到一些优化，从图示可以当for循环还没结束时，排序就已经排好了，即此时各个数据已经到了其应该在的位置。在这里我们其实可以设一个标志变量flag,令其初始值为0，若交换语句执行了flag = 1;故可以当内循环每次结束时，可以判断是否进行过交换，如果没交换则退出。

其他程序代码：

#pragma once

#include<iostream>
using namespace std;
#include<time.h>

const int Max = 40;

template<class Elem>
class Sort
{
public:
	Sort();
	~Sort();
	void BubbleSort();//冒泡排序
	void InsertSort();//插入排序
	void SelectSort();//选择排序
	void OutPut();//输出数据
private:
	int Size;
	Elem Data[Max];
};

/*
Sort构造函数，其构造数据的规模以及随机生成需要排序的数据
*/
template<class Elem>
Sort<Elem>::Sort()
{
	cout<<"请输入要生成随机数的个数:";
	int size;
	cin>>size;
	Size = size;
	srand(time(0));
	for(int i = 0;i < Size;i++)
	{
		Data[i] = rand()%100;//得到0---100的整数
	}
}

//输出数据
template<class Elem>
void Sort<Elem>::OutPut()
{
	for(int i = 0;i<Size;i++)
	{
		cout<<Data[i]<<" ";
		if(9 == i%10)
		{
			cout<<endl;
		}
	}
}
template<class Elem>
Sort<Elem>::~Sort(){}

  

 

其他排序将在后来发布

 

由于显示问题，我不会将图片插入文章中只好利用文件附件方式了

 

上面算法时间复杂度：Time.png