内部排序算法74129
#if 0
这段时间在做论文，忙着就没有来更新博客了。看着博客冷清了些真是心疼，
快快写些程序来充实下我的家园吧，哈哈
程序测试过没有问题，只是要注意有些算法我把第0个元素空间作为暂时存储区，
而其它算法里作为正常的数据存储区，这是为了算法更高效代码更紧凑。
这些是内部排序的各种算法，即是待排序的记录存放在内存里的。
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
归并排序：2-路归并排序
#endif
#include
#include
#define type int
#if 0
直接插入排序
平均时间复杂度为O(n^2)，如果待排数据基本有序，或者数据量较小时，
时间复杂度可以提高到接近O(n)的水平。
#endif
void InserSort( type a[], int length )
{ // a[0]作为暂存单元
int i,j;
for(i=2; i<=length; i++)
{
if( a[i] < a[i-1]) //若后一个元素a[i]比前一个元素a[i-1]小
{
a[0] = a[i]; //将较小的数据a[i]暂存到a[0]中
a[i] = a[i-1]; //将较大数据a[i-1]移到它后一个单元第i个位置
for(j=i-2; a[0]
//若比较出来的较小元素a[0]比它之前的元素a[j]还要小
{
a[j+1] = a[j]; //元素a[j]向后移动一个位置
}
a[j+1] = a[0]; //最后将较小数据a[0]存到正确位置
}
}
}
#if 0
希尔排序
这是直接插入排序的优化算法，平均时间复杂度为 N^1.5
算法思想是将待排数据分割成多个子序列分别进行直接插入排序，
达到整个序列基本有序时再对全体记录进行一次直接插入排序。
#endif
//注意：ShellSort函数执行一次，只按给定步长排序一趟
void ShellSort(type a[], int length, int footlen)
{ //a[0]作为暂存单元 , footlen存储每趟比较时的步长，length表示数组a 的长度
int i, j;
for( i=1+footlen; i<=length; i+=footlen)
{
if( a[i]< a[i-footlen] ) //相隔一个步长远的元素进行比较，若前面的元素大
{
a[0] = a[i]; //将较小元素a[i]暂存到a[0]中
a[i] = a[i-footlen]; //将较大元素移到第i个位置
for(j=i-2*footlen; j>0 && a[0]
//若较小元素a[0]小于它前面的差距两个步长的元素a[j]
{
a[j+footlen] = a[j]; //a[j]往前移动一个步长距离
}
a[j+footlen] = a[0]; //最后这个较小元素a[0]置于正确的位置
}
}
}
#if 0
冒泡排序
平均时间复杂度为N^2
#endif
void BubbleSort( type a[], int length )
{
int i, j;
type tmp;
for(i=0; i
{
for(j=0; j
{
if(a[j]>a[j+1])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
#if 0
快速排序
这是冒泡排序的优化算法
平均时间复杂度为N ln N，所以目前被认为是最好的一种内部排序方法
#endif
//单次排序
int Partition(type a[], int low, int high)
{
type tmp, pivotkey = a[low]; //枢轴点
while(low
{
while(low
{ --high; }//若a[high]值比枢轴点小，则交换到a[low]去
tmp = a[low];
a[low] = a[high];
a[high] = tmp;
while(low
{ ++low; }//若a[low]值比枢轴点大，则交换到a[high]去
tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
return low; //返回的是枢轴点的位置
}
void QuickSort(type a[], int low, int high)//通过递归方式逐级分段进行排序
{
int pivotloc; //记录枢轴点
if(low
{
pivotloc = Partition(a, low, high);
QuickSort(a, low, pivotloc-1);
QuickSort(a, pivotloc+1, high);
}
}
void PrintArr( type a[], int length )
{
int i;
for(i=0; i
{ printf("%d ",a[i] ); }
printf("\n");
}
#if 0
简单选择排序
平均时间复杂度为N^2
#endif
int SelectMinKey(type a[], int length, int k)
{
int i, loc;
type min = a[k];
for(i=k; i
{
if(a[i]<=min)
{
min = a[i];
loc = i; //如果是较小值则记录下该值的下标位置
}
}
return loc; //返回最小值的下标位置
}
void SelectSort(type a[], int length)
{
int i, j;
type tmp;
for(i=0; i
{
j = SelectMinKey(a, length, i); //根据返回位置将最小值置换至靠前位置
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
#if 0
堆排序
只需一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间
平均时间复杂度为 NlogN
(很快会附上这部分代码)
#endif
#if 0
2-路归并排序
平均时间复杂度为 NlogN
(很快会附上这部分代码)
#endif
int main()
{
int i, length, footlen = 5;
int arr[11] = {7,10,2,5,8,9,22,11,87,45,33};
length = sizeof(arr)/sizeof(int);
printf("length = %d\n",length);
// InserSort(arr, 10); //直接插入排序 注意：arr[0]作为暂存单元
/* while(footlen>=1)//第一趟步长为5，第二趟为3，第三趟为1，共循环三次
{
ShellSort( arr, footlen, length); //希尔排序 注意：arr[0]作为暂存单元
footlen-=2;
}
*/
// BubbleSort( arr, length );
// QuickSort(arr, 0, length-1);
SelectSort(arr, length);
PrintArr(arr, length);
while(1);
return 0;
}
数据正在载入中..