//******************直接插入排序*************************
#include <stdio.h>
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void InsertSort(int a[], int n)
{
int temp=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i!=n; ++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a<a)
{
temp = a;
a = a;
int j=0;
for(j = i-2;(temp < a[j])&&(j>=0); --j)
a[j+1] = a[j];
a[j+1] = temp;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[] =
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length=sizeof(a)/sizeof(*a);
InsertSort(a,array_length);
for(int i = 0; i!=array_length; ++i)
printf("%d ", a);
}
//----------------------------------------------------------------------------
//*****************折半插入排序****************************
#include <stdio.h>
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void BInsertSort(int a[], int n)
{
int temp,low,high,mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1; i!=n; ++i)
{
temp=a;
low = 0;
high = i-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(low<=high)
{
mid=(low + high)/2;
if(temp <a[mid])
high = mid - 1;
else
low = mid + 1;
}
for(int j=i-1;j>=high+1;--j)
a[j+1]=a[j];
a[high + 1] = temp;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[] =
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length=sizeof(a)/sizeof(*a);
BInsertSort(a,array_length);
for(int i = 0; i!=array_length; ++i)
printf("%d ", a);
}
//------------------------------------------------------------------------
//***********************希尔排序***********************
#include <iostream.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ShellInsert(int a[], int array_length,int dk)
{
int temp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i = dk;i<=array_length;++i)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a<=a)
{
temp = a;
for(int j = i-dk; j>=0 && temp < a[j]; j -= dk)
a[j + dk] = a[j];
a[j+dk]=temp;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ShellSort(int a[], int array_length_a,int dlta[],int array_length_dlta)
{
for(int k=0; k < array_length_dlta; ++k)
ShellInsert(a, array_length_a,dlta[k]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length_a = sizeof(a)/sizeof(*a);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int dlta[]=
{7,5,3,1,0};
int array_length_dlta = sizeof(dlta)/sizeof(*dlta);
ShellSort(a,array_length_a, dlta, array_length_dlta);
for(int i = 0; i < array_length_a; ++i)
cout<<a<<" ";
}
//----------------------------------------------------------------------------
//***********************快速排序***********************
#include <iostream.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int Partition(int a[], int low, int high)
{
int pivot, temp;
pivot = temp = a[low];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(low < high)
{
while(low < high && a[high] >= pivot)
--high;
a[low] = a[high];
while(low < high && a[low] <= pivot)
++low;
a[high] = a[low];
}
a[low] = temp;
return low;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void QSort(int a[], int low, int high)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(low < high)
{
int pivotloc = Partition(a, low, high);
QSort(a, low, pivotloc - 1);
QSort(a, pivotloc + 1, high);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void QuickSort(int a[], int a_length)
{
QSort(a, 0, a_length-1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length_a = sizeof(a)/sizeof(*a);
QuickSort(a, array_length_a);
for(int i = 0; i < array_length_a; ++i)
cout<<a<<" ";
}
//----------------------------------------------------------------------------
//***********************冒泡排序***********************
#include <iostream.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void BubbleSort(int a[], int n)
{
bool change = true;
int tmp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=n-1;i>=1&&change;--i)
{
change = false;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=0; j < i;++j)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
change = true;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length = sizeof(a)/sizeof(*a);
BubbleSort(a, array_length);
for(int i=0; i!=array_length; ++i)
cout<<a<< " ";
return 0;
}
//----------------------------------------------------------------------------
//***********************简单选择排序***********************
#include <iostream.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void SelectSort(int a[], int array_length)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i != array_length; ++i)
{
int min=a;
int index = i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=i; j != array_length; ++j)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a[j] < min)
{
min=a[j];
index = j;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i != index)
{
a = a + a[index];
a[index] = a - a[index];
a = a - a[index];
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length = sizeof(a)/sizeof(*a);
SelectSort(a, array_length);
for(int i=0; i!=array_length; ++i)
cout<<a<< " ";
return 0;
}
//----------------------------------------------------------------------------
//******************堆排序*************************
#include <iostream.h>
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void HeapAdjust(int a[], int s, int m)
{
int rc = a[s-1];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=2*s; j <= m; j *= 2)
{
if(j < m && a[j-1] < a[j])
++j;
if(rc >= a[j-1])
break;
a[s-1] = a[j-1];
s=j;
}
a[s-1] = rc;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void HeapSort(int a[], int array_length)
{
for(int i = array_length/2; i>0; --i)
HeapAdjust(a, i, array_length);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j = array_length; j > 1; --j)
{
a[0] = a[0] + a[j-1];
a[j-1] = a[0] - a[j-1];
a[0] = a[0] - a[j-1];
HeapAdjust(a, 1, j-1);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length = sizeof(a)/sizeof(*a);
HeapSort(a, array_length);
for(int i=0; i!=array_length; ++i)
cout<<a<< " ";
return 0;
}
//-------------------------------------------------------------
//***********************归并排序***********************
void merge(int a[],int low,int middle,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int h,i,j,k;
int b[20];
h=low;
i=low;
j=middle+1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(h<=middle&&j<=high)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(a[h]<=a[j])
{
b=a[h];
h++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
b=a[j];
j++;
}
i++;
}
if(h>middle)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=j;k<=high;k++)
{
b=a[k];
i++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=h;k<=middle;k++)
{
b=a[k];
i++;
}
}
for(k=low;k<=high;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
a[k]=b[k];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//归并排序函数的具体实现
void mergesort(int a[],int low,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int middle;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(low<high)
{
middle=(low+high)/2;
mergesort(a,low,middle);
mergesort(a,middle+1,high);
merge(a,low,middle,high);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int a[]=
{56,23,48,25,84,15,35,69,87,12,54,28,37,19,47,12};
int array_length_a = sizeof(a)/sizeof(*a);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int b[]=
{0,0};
int array_length_b = sizeof(b)/sizeof(*b);
mergesort(a,0,15);
for(int i=0; i!=array_length_a; ++i)
cout<<a<< " ";
cout<<endl;
return 0;
} //-------------------------------------------------------------
posted on 2009-07-19 11:18
老马驿站 阅读(165)
评论(0) 编辑 收藏 引用 所属分类:
c++