[数据结构与算法]数据结构（几种排序）

数据结构中排序的方法主要有6种：插入排序，希尔排序，冒泡排序，折半排序，快速排序和简单排序。下面我们对于6中排序方法来一一讲解。

结构准备

#include <stdio.h>
#include <stdlib.h>

typedef int keytype;
typedef char elemtype;
typedef struct
{
   keytype key;
   elemtype data;           //在排序中没有用到data
}RecType;

1.插入排序

以表L[n]为例来讲解。排序的方法是从表的头开始，当存在L[i]>L[i-1]时，我们又从第一个元素开始依次查找，当找到小于L[i-1]的元素L[k]时，将L[k]到L[i-1]的元素依次向前移动一位，最后将L[i]插入L[k]的位置。

从头开始，先让前面依次成递增排列，最后使整个表成递增排列。代码实现如下：

void InsertSort(RecType L[],int n)
{
	int team;
	for(int i=1;i<n;i++)           //在表中从前向后查找
	{
		if(L[i].key<L[i-1].key)    //当存在后面的数小于前面的数时，调整位置
		{
			team=L[i].key;         //将前面的数赋值给team；
			int j=i-1;
		    while(team<L[j].key)
		    {
		    	L[j+1].key=L[j].key;  //将后面小于team的数依次移动，找到L[i]应该插入的位置
		    	j--;
			}
			L[j+1].key=team;         //插入该位置
		}
	}
}

2.希尔排序

希尔排序主要是通过确定一个数d，将表中距离为d的数依次进行比较，如果有L[i]>L[i+d]的情况，将两个元素交换位置。然后在使用d=d/2继续进行该操作，在使用d/4继续进行该操作，直到d<0，最后使整个表成有序排列。排序完成。

希尔排序的特点是大量减少了空间复杂度，代码实现如下：

void ShellSort(RecType L[],int n)
{
	int d,team;
	d=n/2;                              //选择d为表的长度的一半
	while(d>0)                           
	{
		for(int i=1;i+d<=n;i++)         //当i+d超过表长度时，停止。 
		{
			if(L[i].key>L[i+d].key)     //存在L[i]>L[i+d]时，通过team对两个数进行交换
			{
				team=L[i].key;
				L[i].key=L[i+d].key;
				L[i+d].key=team;
			}
		}
		d=d/2;                          //将d减少一半，继续进行排序
	}
}

3.冒泡排序

冒泡排序的方法是在1~n中找到一个最大的数排在最后面，在从1~n-1中找到一个最大的数排到次后面，然后在从1~n-2中找到一个第三大树树放在第n-2个，依次从尾到头排成一个有序的表。主要的实现方法是从第一个元素开始，比较相邻的两个元素，如果大的数在前面，就将两个相邻的数互换。相当于最大的数想泡泡一样冒出到最后面，因此叫做冒泡排序。

冒泡排序的主要优点是时间复杂度低，运算较快，代码实现如下：

void BubbleSort(RecType L[],int n)
{
	int team;
	for(int i=n-1;i>=1;i--)             //从尾部开始，找到一个最大的数
		for(int j=1;j<=i;j++)
		{
			if(L[j].key>=L[j+1].key)     //如果相邻的两个数中前面的书大于后面的数
			{                    
				team=L[j+1].key;         //将大的数放在后面，直到将最大的数放到最后面  
                L[j+1].key=L[j].key;
                L[j].key=team;
			}
		}
}

4.快速排序

快速排序的基本方法是将一个表通过两个“指针”同时分别从头到尾和从尾到头进行排序。最后将一个表排序完成。

首先选择一个基准，以基准为单位，分别从两端向中间扫描，知道两个“指针”相遇。将左边大于基准的数和右边小于基准的数互换。然后在两个“指针”相遇的位置分别在左右两边递归，知道将整个表全部成递增排列。

快速排序是所以排序中最快的排序方法，代码实现如下：

int fanghui(biao L[],int s,int t)        //选择头为s，尾部为t.
{
	int i=s,j=t;                         //定义两个指针，i在头部，j在尾部。
	int team;
	team=L[i].key;                       //选择头部的第一个元素为基准。
	while(i<j)
	{
		while(j>i&&L[j].key>=team)       //“指针”j从尾部向中间扫描。
		  j--;
		L[i].key=L[j].key;               
		while(i<j&&L[i].key<=L[j].key)   //“指针”i从头部向中间扫描
		  i++;
		L[j].key=L[i].key;               //将头部i扫描到的大于基准的元素与尾部j扫描到的
	}                                      小于基准的元素互换。    
	L[i].key=team;
	return i;                             //返回相遇的位置
}
void kuaishu(biao L[],int s,int t)
{
	int i;
	if(s<t)
	{                             
		i=fanghui(L,s,t); 
		kuaishu(L,s,t-1);                 //左边进行快速排序。
		kuaishu(L,i+1,t);                 //右边进行快速排序。
	}                                     //最后整个表排序完成
}

5.折半排序

折半排序是通过折半的方式查找元素的位置，然后将元素与该位置的元素互换。主要实现的方式是：从第一个元素开始向后查找，如果发现相邻的两个元素中前面的元素大于后面的元素（L[i]>L[i+1]），将前面的元素使用折半查找法找到小于L[i+1]的元素，然后将L[i+1]与该位置前面的元素互换。

代码实现如下：

void BinInsertSort(RecType L[],int n)
{
	int team,j;
	for(int i=1;i<n;i++)
	{
		if(L[i].key<L[i-1].key)
		{
			team=L[i].key;
			int team=L[i].key;
			int zuo,you,zhong;
			zuo=0;you=i-1;
		    while(zuo<=you)
		    {
		    	zhong=(zuo+you)/2;
		    	if(L[zhong].key>team)
		    	  you=zhong-1;
		    	else if(L[zhong].key<team)
		    	  zuo=zhong+1;
		    }
		for(j=i;j>zuo;j--)
			L[j].key=L[j-1].key;
		L[j].key=team;
		}
	}
}

6.简单排序

简单排序是从一个元素开始，在后面的元素中选择最小的元素与第一个元素相互赋值，直到最后一个元素。相当于先从1~n中选择一个最小的元素，若元素小于L[0]，将L[0]与该元素相互赋值，将最小的元素排在第一位。然后通过同样的方式在2~n中选择一个最

小的元素放在第二位，直到将最大的元素排到最后一位，排序完成。

简单排序的特点是容易理解，也是生活中最简单的一种排序方法，代码实现如下：

void SelectSrot(biao L[],int n)
{
	int k,team;
	for(int i=1;i<=n-1;i++)          
	{
		k=i;                        //将i的值赋给k
		for(int j=i+1;j<=n;j++)     //从i+1开始查找，找到最小的元素。
			if(L[k].key>L[j].key)
			  k=j;                  //通过k记录该元素的位置
		if(k!=i)                    //将i位置的元素与k位置的元素相互赋值，完成互换
		{
			team=L[k].key;
			L[k].key=L[i].key;
			L[i].key=team;
		}
	}
}

简单排序和插入排序的区别是简单排序是通过交换元素值进行排序，而插入排序是通过交换元素的位置进行排序。

本人作为一名计算机的初学者，这是本人在CSDN上面发布的第一遍博客，欢迎大家前来指点修正，谢谢。