排序算法详解（三）
前面说了插入排序和快速排序，下面我们来看一下选择排序。
选择排序的基本思想是：每一趟在n-i+1的记录中选个去关键字最小的记录作为有序序列的第i个记录。我们先来看下选择排序中最简单的方法，简单选择排序，其使用与序列元素比较少的情况。
简单选择排序的基本思想是，在要排序的元素序列中找到一个最小的元素，将它与序列的第一个元素进行交换，然后在剩余的n-1个元素中在找到最小的，跟剩余序列中的第一个元素进行交换，重复此过程直到全部选择完成。
其算法思想很简单，下面我们来看一个简单选择排序的小例子，进一步加深对此算法的理解：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
void Selectsort(int *arr,int n)
{
int i,j,min,t;
for(i=0;i<n-1;i++)
{
min = i;
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
min = j;
}
if(min-i)
{
t = arr[min];
arr[min] = arr[i];
arr[i] = t;
}
}
for(i=0;i<n;i++)
printf("L[%d]=%d\n",arr[i]);
}
int main()
{
int i,n,L[N];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&L[i]);
Selectsort(L,n);
return 0;
}
由上面的分析可以看出，简单选择排序的时间复杂度为O(n2)。是不稳定的排序算法。
当数据量比较大的时候，简单选择排序就不太适用了，那么我们下来看另外一种选择排序，堆排序，其适用于大数据量的排序。
首先我们来看下什么是堆。堆的定义是：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。了解了堆以后，我们就来看下如何实现堆排序。(使用大跟堆)
1、先将初始初始序列L[0..n-1]建成一个大根堆，此堆为初始的无序区。
2、然后将最大的元素L[0](即堆顶)和无序区的最后一个记录L[n-1]交换，由此得到新的无序区L[0..n-2]和有序区L[n-1]，且满足L[0..n-2]≤L[n-1]。
3、将当前无序区L[0..n-2]调整为堆，然后再次将L[0..n-2]中最大的元素L[0]和该区间的最后一个记录L[n-2]进行交换，这样有得到新的无序区L[0..n-3]和有序区L[n-2..n-1]，且仍满足关系L[0..n- 3]≤L[n-2..n-1]。
4、再将无序区调整为堆，重复以上步骤直到无序区只有一个元素为止。
前面每交换一次元素后都要重新将无序区调成为堆，那么一个序列怎样转化为堆呢，下面我们来看下如何创建一个堆。
从一个无序序列建堆的过程就是一个反复筛选的过程。如将此序列看成是一个完全二叉树，则最后一个非终端节点是第 n/2 个元素，由此筛选就从n/2开始即可。从n/2第一个非终端节点开始，比较其左右子树的根节点，如果大于左右子树根节点，那么不做变动，如果小于左右子树根节点的最大值，那么就与这个最大值交换位置，然后继续从n/2-1个非终端节点开始继续比较，知道所有非终端节点比较完成，一个堆就初始化完成了。
堆排序听起来比较复杂，那么我们下来看一个堆排序的例子加深对堆排序的理解：
[cpp]
#include<stdio.h>
#include<stdlib.h>
#define N 100
void HeapAdjust(int *arr,int n) //建堆函数
{
int t,i,j,start,max;
start = n/2;
for(i=start;i>0;i--)
{
max = 2*i-1;
if(2*i+1<=n)
if(arr[2*i-1]<arr[2*i])
max++;
if(arr[i-1]<arr[max])
{
t = arr[max];
arr[max] = arr[i-1];
arr[i-1] = t;
}
}
t = arr[n-1]; //后面三行是将堆的根节点与最后一个元素进行交换
arr[n-1] = arr[0];
arr[0] = t;
}
void Heapsort(int *arr,int n) //堆排序函数
{
int i;
for(i=n;i>0;i--)
HeapAdjust(arr,i);
for(i=0;i<n;i++)
printf("L[%d]=%d\n",i,arr[i]);
}
int main()
{
int i,n,L[N];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&L[i]);
Heapsort(L,n);
return 0; www.zzzyk.com
}
堆排序的时间复杂度是O(nln n)。是不稳定的排序算法。
以上就是对几种基本的排序算法进行了一个大概的说明，代码都是自己编写，有什么问题欢迎指正。
作者：wanchres
补充：软件开发 , C++ ,
