#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last)//冒泡排序
void InsertSort(int a[], const int first, const int last)//插入排序
void SelectSort(int a[], const int first, const int last)//选择排序
void MergeSort(int a[], const int p, const int r)//合并排序
void QuickSort(int a[],const int p,const int r)//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)//希尔排序
void HeapSort(int a[],const int p, int r)//堆排序
void StoogeSort(int a[],const int p,const int r)//Stooge排序(不用)算法复杂度没算清楚
void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1}
int dlta[]={9,5,3,2,1}
//BubbleSort(a,0,5)
//InsertSort(a,0,5)
//SelectSort(a,0,5)
//MergeSort(a,0,5)
//QuickSort(a,0,5)
//ShellSort(a,0,5,dlta,5)
HeapSort(a,0,5)
//StoogeSort(a,0,5)
for(int i=0i<=5i++)
{
printf("%d ",a[i])
}
}
/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp
for(i=firsti<=lasti++)
{
for(j=firstj<last-ij++)
{
if(a[j] >a[j+1])
{
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
}
}
}
}
/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“插入”排序
//最坏情况为n的平方，，多用于小数组
int i,j,temp
for(i=first+1i<=lasti++)
{
temp = a[i]
j = i - 1
while((j >= 0) &&(a[j] >temp))
{
a[j+1] = a[j]
j--
}
a[j+1] = temp
}
}
/************************选择排序***********************/
void SelectSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“选择”排序
int i, j, temp, num
for(i=firsti<lasti++)
{
num = i
for(j=i+1j<=lastj++)
{
if(a[j] <a[num])
{
num = j
}
}
if(i != num)
{
temp = a[num]
a[num] = a[i]
a[i] = temp
}
}
}
/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的实现合并的子程序
int iLLength,iRLength
int *L, *R, i, j, k
iLLength = q - p + 1
iRLength = r - q
L = (int *)malloc(iLLength*sizeof(int))//或者 C++中 new int[iLLength]
R = (int *)malloc(iRLength*sizeof(int))//或者 C++中 new int[iRLength]
if(L == 0 || R== 0)
{
printf("内存分配失败！！！")
return
}
for(i=0i<iLLengthi++)
{
L[i] = a[p+i]
}
for(j=0j<iRLengthj++)
{
R[j] = a[q+j+1]
}
i = 0
j = 0
for(k=pk<=rk++)
{
if((i<iLLength) &&(j<iRLength) &&(L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i]
i++
}
else if(j<iRLength)
{
a[k] = R[j]
j++
}
}
free(R)free(L)
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系数较小
int q
if(p<r)
{
q = (p+r)/2
MergeSort(a,p,q)
MergeSort(a,q+1,r)
Merge(a,p,q,r)
}
}
/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k
if(a[p]>a[r])
{
temp= a[p]
a[p]= a[r]
a[r]= temp
}
if((p+1) >= r)
{
return
}
k = (r-p+1)/3
StoogeSort(a,p,r-k)
StoogeSort(a,p+k,r)
StoogeSort(a,p,r-k)
}
/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(关键)分治过程
int temp, x, i, j
x = a[r]
i = p - 1
for(j=pj<rj++)
{
if(a[j] <= x)
{
i = i + 1
temp = a[i]
a[i] = a[j]
a[j] = temp
}
}
temp = a[i+1]
a[i+1] = a[r]
a[r] = temp
return (i+1)
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//与下面的“尾递归实现方法”比较，缺点：右边数组的递归不是必须的，增加了运行堆栈深度和调用开销
int q
if(p <r)
{
q = QuickPartition(a, p, r)
QuickSort(a, p, q-1)
QuickSort(a, q+1, r)
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾递归实现方法”是对上面的快速排序主程序实现的一种优化
//系数较小,常用大数组
int q
while(p <r)
{
q = QuickPartition(a, p, r)
QuickSort(a, p, q-1)
p = q + 1
}
}
/************************希尔排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希尔排序算法的关键子程序-插入排序子程序
int i, j, temp
for(i=p+dki<=ri++)
{
if(a[i] <a[i-dk])
{
temp = a[i]
for(j=i-dk((j>=0) &&(temp <a[j]))j -= dk)
{
a[j+dk] = a[j]
}
a[j+dk] = temp
}
}
}
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希尔排序算法-主程序
//按增量序列dlta[]中的前t个增量，实现对数组a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最后一个值必须是1
//增量序列中的值没有除1以外的因子， 其精确时间复杂度：数学上尚未解决的难题
int k
for(k=0k<tk++)
{
ShellInsert(a,p,r,dlta[k])
}
}
/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其来实现“优先级队列”
int Parent(int i)
{
return ((i+1)/2-1)
}
int Right(int i)
{
return (2*(i+1)-1)
}
int Left(int i)
{
return (2*(i+1))
}
void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp
l = Left(i)
r = Right(i)
largest = ((l<=hplast) &&(a[l]>a[i])) ? l:i
if((r<=hplast) &&(a[r]>a[largest]))
{
largest = r
}
if(largest != i)
{
temp = a[i]
a[i] = a[largest]
a[largest] = temp
Max_Heapify(a,hplast,largest)
}
}
void Build_Max_Heap(int a[],const int p, const int r)
{
int i
for(i = (p+r)/2i>=pi--)
{
Max_Heapify(a,r,i)
}
}
void HeapSort(int a[],const int p, int r)
{
int i,temp
Build_Max_Heap(a,p,r)
for(i = ri >pi--)
{
temp = a[p]
a[p] = a[i]
a[i] = temp
r -= 1
Max_Heapify(a,r,0)
}
}
