数据结构-排序问题

   排序分为以下几大类：a:插入排序；b:选择排序；c:交换排序；d:归并排序；e:基数排序。

  a:插入排序:分为直接插入排序与希尔排序。直接插入排序的思想是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。

poj 2388代码：

#include <iostream>
using namespace std;
const int Max=10002;

void InsertSort(int a[],int n)
{
	int i,j;
	int temp;
	for (i=0;i<n-1;i++)
	{
		temp=a[i+1];
		j=i;
		while (j>-1&&temp<a[j])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}
}

int main()
{
	int n;
	cin>>n;
	int b[Max];
	for(int k=0;k<n;k++)
		cin>>b[k];
	InsertSort(b,n);
	cout<<b[n/2]<<endl;
	return 0;
}

 

 

 

b:选择排序

在选择排序中，有一种简单的方法叫做直接选择排序，直接选择排序的基本思想是：从待排序的数据元素中选取关键字最小的数据元素并将它与第一个数据交换位置；接着从不包括第一个位置的数据元素集合中选取关键字最小的，与第二个位置的数据交换，如此重复，直到只剩一个数据元素为止。显然，这种排序方式的时间复杂度为O(n*n)。

poj 2388代码如下：

#include <iostream>
using namespace std;
const int Max=10002;

void SelectSort(int a[],int n)
{
	int i,j,small;
	int temp;
	for (i=0;i<n-1;i++)
	{
		small=i;
		for (j=i+1;j<n;j++)
			if(a[j]<a[small])
				small=j;
			if(small!=i)
			{
				temp=a[i];
				a[i]=a[small];
				a[small]=temp;
			}
	}
}

int main()
{
	int n;
	cin>>n;
	int b[Max];
	for (int k=0;k<n;k++)
		cin>>b[k];
	SelectSort(b,n);
	cout<<b[n/2]<<endl;
	return 0;
}

 

  在直接选择排序中，待排序的数据元素集合构成一个线性表，要从有n个数据元素的线性表中选择出一个最小的数据元素需要比较n-1次。如果能把待排序的数据元素集合构成一棵完全二叉树结构，则每次选择出一个最大（最小）的元素只需要比较log2n次，所以排序的时间复杂度就是O(n*log2n)，这就是堆排序的思想。

    堆排序的流程：

    1.将完全二叉树调整为一个最大（小）堆。

     从第一个非叶子结点开始到根节点，每次都将当前结点调整为一个最大堆，前提是当前结点的左孩子和右孩子都已经是最大堆。

    2.每次把堆顶与当前最大堆的最后一个元素交换，最大堆元素个数减1，若此时根节点不满足最大堆的定义，调整根节点使之满足最大堆的定义。

poj 2388代码如下：

//堆排序：基于完全二叉树，是一种选择排序，不稳定。
#include <iostream>
const int MAX = 100001;
int a[MAX];
//调整非叶子结点a[h]使之满足最大堆的定义。前提：它的左孩子a[2*h+1]和右孩子a[2*h+2]均已是最大堆。
void createHeap(int n, int h)
{
	int i = h;
	int j = 2*i + 1;
	int t = a[i];
	bool flag = false;
	while(j < n && !flag)
	{
		if(j < n-1 && a[j] < a[j+1])
			j++;
		if(t > a[j])
			flag = true;
		else
		{
			a[i] = a[j];
			i = j;
			j = 2*i + 1;
		}
	}
	a[i] = t;
}

//从第一个非叶子结点a[(n-1)/2]开始到a[0]，构造最大堆。
void initialHeap(int n)
{
	for(int i = (n-1)/2; i>=0; i--)
		createHeap(n, i);
}

//每次将当前最大堆的堆顶a[0](最大)与最后一个元素交换。
void heapSort(int n)
{
	int t;
	initialHeap(n);
	for(int i = n-1; i > 0; i--)
	{
		t = a[0];
		a[0] = a[i];
		a[i] = t;
		createHeap(i,0);
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	heapSort(n);
	printf("%d",a[n/2]);
	return 0;
}

 

 c:交换排序 交换排序中的冒泡排序思想：依次比较相邻的两个数，如果a[i]>a[i+1]，就把i和i+1交换位置。这样，第一遍时，最大的数就排在了最后，如此反复，就可以排序。

    冒泡排序的优化：可以设置一个标志位，如果某一次循环中发现位置都没有变化，显然数组已排好序，直接退出。冒泡排序的时间复杂度为O(n*n)冒泡排序代码比较简单，

poj 2388代码如下：

#include <iostream>
using namespace std;
const int Max=10002;

void BubbleSort(int a[],int n)
{
	int i,j;
	int temp;
	for (i=1;i<n;i++)
	{
		for (j=0;j<n-i;j++)
		{
			if (a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}

int main()
{
	int n;
	cin>>n;
	int b[Max];
	for(int k=0;k<n;k++)
		cin>>b[k];
	BubbleSort(b,n);
	cout<<b[n/2]<<endl;
	return 0;
}

 

   快速排序是一种二叉树结构的交换排序方式。快速排序的思想：每次循环结束后，一反面将标准元素（通常为a[low]）放在了未来排好序的数组中的正确位置，另一方面将数组中的元素分为了两个子数组，位于标准元素左边的关键字均小于它，位于关键元素右边的关键字均大于等于它，然后对这两个子数组分别进行同样的操作，直到low=high结束。

    快速排序最坏的情况是数组已完全有序，此时二叉树将退化为单分支二叉树，深度为n。但它的平均时间复杂度为O(n*log2n)，不是一种稳定的排序方法。poj 2388代码如下：

#include <iostream>
using namespace std;
const int Max=10002;

void QuickSort(int a[],int low,int high)
{
	int i,j;
	if(low>high)
		return;
	i=low;
	j=high;
	int temp;
	temp=a[i];
	while (i<j)
	{
		while(i<j&&temp<a[j])j--;
		if (i<j)
		{
			a[i]=a[j];
			i++;
		}
		while(i<j&&a[i]<temp)i++;
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	a[i]=temp;
	QuickSort(a,low,--j);
	QuickSort(a,++i,high);
}

int main()
{
	int n;
	int b[Max];
	cin>>n;
	for (int k=0;k<n;k++)
		cin>>b[k];
	QuickSort(b,0,n-1);
	cout<<b[n/2]<<endl;
	return 0;
}

 

 关于归并排序，以后再进行详细解释！！