//******************直接插入排序*************************
#include <stdio.h>
#include <stdlib.h>
void InsertSort(int a[], int n)
{
int temp=0;
for(int i=1; i!=n; ++i){
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;
}
}
}
void main(){
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>
void BInsertSort(int a[], int n){
int temp,low,high,mid;
for(int i=1; i!=n; ++i){
temp=a;
low = 0;
high = i-1;
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;
}
}
void main(){
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>
void ShellInsert(int a[], int array_length,int dk){
int temp;
for(int i = dk;i<=array_length;++i){
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;
}
}
}
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]);
}
void main(){
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);
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>
int Partition(int a[], int low, int high){
int pivot, temp;
pivot = temp = a[low];
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;
}
void QSort(int a[], int low, int high){
if(low < high){
int pivotloc = Partition(a, low, high);
QSort(a, low, pivotloc - 1);
QSort(a, pivotloc + 1, high);
}
}
void QuickSort(int a[], int a_length){
QSort(a, 0, a_length-1);
}
void main(){
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>
void BubbleSort(int a[], int n){
bool change = true;
int tmp;
for(int i=n-1;i>=1&&change;--i){
change = false;
for(int j=0; j < i;++j){
if(a[j]>a[j+1]){
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
change = true;
}
}
}
}
int main(){
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>
void SelectSort(int a[], int array_length){
for(int i=0; i != array_length; ++i){
int min=a;
int index = i;
for(int j=i; j != array_length; ++j){
if(a[j] < min){
min=a[j];
index = j;
}
}
if(i != index){
a = a + a[index];
a[index] = a - a[index];
a = a - a[index];
}
}
}
int main(){
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>
void HeapAdjust(int a[], int s, int m){
int rc = a[s-1];
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;
}
void HeapSort(int a[], int array_length){
for(int i = array_length/2; i>0; --i)
HeapAdjust(a, i, array_length);
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);
}
}
int main(){
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)
{
int h,i,j,k;
int b[20];
h=low;
i=low;
j=middle+1;
while(h<=middle&&j<=high){
if(a[h]<=a[j]){
b=a[h];
h++;
}
else{
b=a[j];
j++;
}
i++;
}
if(h>middle)
for(k=j;k<=high;k++){
b=a[k];
i++;
}
else{
for(k=h;k<=middle;k++){
b=a[k];
i++;
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}
//归并排序函数的具体实现
void mergesort(int a[],int low,int high)
{
int middle;
if(low<high){
middle=(low+high)/2;
mergesort(a,low,middle);
mergesort(a,middle+1,high);
merge(a,low,middle,high);
}
}
int main(){
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);
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
老马驿站 阅读(167)
评论(0) 编辑 收藏 引用 所属分类:
c++