排序算法详解（三）

前面说了插入排序和快速排序，下面我们来看一下选择排序。

选择排序的基本思想是：每一趟在n-i+1的记录中选个去关键字最小的记录作为有序序列的第i个记录。我们先来看下选择排序中最简单的方法，简单选择排序，其使用与序列元素比较少的情况。

简单选择排序的基本思想是，在要排序的元素序列中找到一个最小的元素，将它与序列的第一个元素进行交换，然后在剩余的n-1个元素中在找到最小的，跟剩余序列中的第一个元素进行交换，重复此过程直到全部选择完成。

其算法思想很简单，下面我们来看一个简单选择排序的小例子，进一步加深对此算法的理解：

#include<stdio.h>#include<stdlib.h>#define N 100void 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;}

堆排序的时间复杂度是O(nln n)。是不稳定的排序算法。
以上就是对几种基本的排序算法进行了一个大概的说明，代码都是自己编写，有什么问题欢迎指正。