希尔排序c语言课程设计
㈠ 希尔排序（c语言）
#include<stdio.h>
#include<stdlib.h>
void hillsort(int*,int);
main()
{
int sup=10;
int *list=(int *)malloc(sizeof(int)*sup);
int val,i=1,j;
scanf("%d",&val);
while(val!=EOF)//以-1结束
{
list[i++]=val;
scanf("%d",&val);
if(i>=sup){
sup=i+sup;
realloc(list,sizeof(int)*sup);
}
}
hillsort(list,i-1);
for(j=1;j<i;j++){
printf("%d ",list[j]);
if(j%10==0)
printf("\n");
}
return 0;
}
void hillsort(int *list,int n)
{
int gap=n/2,count,j;
while(gap>=1){
for(count=1+gap;count<=n;count+=gap)
{
if(list[count]<list[count-gap])
{
list[0]=list[count];
for(j=count-gap;j>0&&list[j]>list[0];j-=gap)
list[j+gap]=list[j];
list[j+gap]=list[0];
}
}
gap=gap/2;
}
}
㈡ C语言程序设计 排序题
楼主 看到你的问题后我写到现在。。满意的话请采纳 QAQ
输入数据的时候每个数字之间用回车隔开。
也可以修改一下用随机数放到数组中
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#defineRADIX_1010//整形排序
#defineKEYNUM_3110//关键字个数，这里为整形位数
voidswap(int*a,int*b);//交换两个数
voidinputnum(int*a,intn); //输入数组里的数字
voidshowarray(int*a,intn); //显示数组数据
intpaixu(int*a,intn); //不要吐槽名字因为不让用sortQAQ
voidstraight_insert_sort(int*a,intn); //直接插入排序
voidbin_insert_sort(int*a,intn); //折半查找排序
voidShellSort(int*pDataArray,intiDataNum); //希尔排序
voidShellInsert(int*pDataArray,intd,intiDataNum); //一趟希尔排序
voidquickSort(inta[],intleft,intright);//快速排序
voidselectSort(inta[],intn); //简单选择排序
voidMinheapsortTodescendarray(inta[],intn);//堆排序
voidMinHeapFixdown(inta[],inti,intn);
voidMakeMinHeap(inta[],intn);
voidRadixSort(int*pDataArray,intiDataNum);//基数排序
intGetNumInPos(intnum,intpos);
intmain(void)
{
intn;
int*a;
printf("请输入数据个数n=");
scanf("%d",&n);
while(n!=0)
{
a=(int*)malloc((n+1)*sizeof(int));
inputnum(a,n); //输入数据
showarray(a,n);
paixu(a,n); //数组排序
showarray(a,n); //输出数组
free(a);
printf(" 请输入数据个数n=");
scanf("%d",&n);
}
return0;
}
//输入数字到数组
voidinputnum(int*a,intn)
{
inti;
srand(time(NULL));
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
//a[i]=rand()%200;
}
}
//输出数组
voidshowarray(int*a,intn)
{
inti;
for(i=1;i<=n;i++)
{
printf("%d",a[i]);
}
}
voidstraight_insert_sort(int*a,intn)
{
inti;
intj;
for(i=2;i<=n;i++)
{
if(a[i]<a[i-1])
{
a[0]=a[i];
a[i]=a[i-1];
for(j=i-2;a[0]<a[j];j--)
{
a[j+1]=a[j];
}
a[j+1]=a[0];
}
}
}
voidbin_insert_sort(int*a,intn) //折半查找排序
{
intlow,high,mid,i,j;
for(i=2;i<=n;i++)
{
a[0]=a[i];
low=1;
high=i-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[0]<a[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
for(j=i-1;j>=high+1;j--)
{
a[j+1]=a[j];
}
a[high+1]=a[0];
}
}
/********************************************************
*函数名称：ShellInsert
*参数说明：pDataArray无序数组；
*d增量大小
* iDataNum为无序数据个数
*说明：希尔按增量d的插入排序
*********************************************************/
voidShellInsert(int*pDataArray,intd,intiDataNum)
{
inti,j,temp;
for(i=d;i<iDataNum;i+=1)//从第2个数据开始插入
{
j=i-d;
temp=pDataArray[i];//记录要插入的数据
while(j>=0&&pDataArray[j]>temp)//从后向前，找到比其小的数的位置
{
pDataArray[j+d]=pDataArray[j];//向后挪动
j-=d;
}
if(j!=i-d)//存在比其小的数
pDataArray[j+d]=temp;
}
}
/********************************************************
*函数名称：ShellSort
*参数说明：pDataArray无序数组；
* iDataNum为无序数据个数
*说明：希尔排序
*********************************************************/
voidShellSort(int*pDataArray,intiDataNum)
{
intd;
d=iDataNum/2;//初始增量设为数组长度的一半
while(d>=1)
{
ShellInsert(pDataArray,d,iDataNum);
d=d/2;//每次增量变为上次的二分之一
}
}
//冒泡排序
voidBubbleSort(inta[],intn)
{
inti,j;
for(i=1;i<=n;i++)
for(j=2;j<=n-i;j++)
if(a[j-1]>a[j])
{
a[0]=a[j];
a[j]=a[j-1];
a[j-1]=a[0];
}
}
//快速排序
voidquickSort(inta[],intleft,intright)
{
inti=left;
intj=right;
inttemp=a[left];
if(left>=right)
return;
while(i!=j)
{
while(i<j&&a[j]>=temp)
j--;
if(j>i)
a[i]=a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
while(i<j&&a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
quickSort(a,left,i-1);/*递归左边*/
quickSort(a,i+1,right);/*递归右边*/
}
voidselectSort(inta[],intn) //简单选择排序
{
inti,j,k,t;
for(i=1;i<=n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
{
if(a[k]>a[j])k=j;
}
if(k!=i)
{t=a[i];a[i]=a[k];a[k]=t;}
}
}
voidMinheapsortTodescendarray(inta[],intn)
{
inti;
for(i=n-1;i>=1;i--)
{
swap(&a[i],&a[0]);
MinHeapFixdown(a,0,i);
}
}
voidswap(int*a,int*b)//交换两个数
{
intx;
x=*a;
*a=*b;
*b=x;
}
//建立最小堆
voidMakeMinHeap(inta[],intn)
{
inti;
for(i=n/2-1;i>=0;i--)
MinHeapFixdown(a,i,n);
}
//从i节点开始调整,n为节点总数从0开始计算i节点的子节点为2*i+1,2*i+2
voidMinHeapFixdown(inta[],inti,intn)
{
intj,temp;
temp=a[i];
j=2*i+1;
while(j<n)
{
if(j+1<n&&a[j+1]<a[j])//在左右孩子中找最小的
j++;
if(a[j]>=temp)
break;
a[i]=a[j];//把较小的子结点往上移动,替换它的父结点
i=j;
j=2*i+1;
}
a[i]=temp;
}
voidover_array(int*a,intn)
{
intx;
inti=1;
while(i<=n)
{
x=a[i];
a[i]=a[n];
a[n]=x;
n--;
i++;
}
}
//将有二个有序数列a[first...mid]和a[mid...last]合并。
voidmergearray(inta[],intfirst,intmid,intlast,inttemp[])
{
inti=first,j=mid+1;
intm=mid,n=last;
intk=0;
while(i<=m&&j<=n)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
voidmergesort(inta[],intfirst,intlast,inttemp[])
{
if(first<last)
{
intmid=(first+last)/2;
mergesort(a,first,mid,temp);//左边有序
mergesort(a,mid+1,last,temp);//右边有序
mergearray(a,first,mid,last,temp);//再将二个有序数列合并
}
}
intMergeSort(inta[],intn)
{
int*p=malloc(sizeof(int)*n);
if(p==NULL)
return0;
mergesort(a,0,n-1,p);
free(p);
return1;
}
/********************************************************
*函数名称：GetNumInPos
*参数说明：num一个整形数据
* pos表示要获得的整形的第pos位数据
*说明：找到num的从低到高的第pos位的数据
*********************************************************/
intGetNumInPos(intnum,intpos)
{
inti;
inttemp=1;
for(i=0;i<pos-1;i++)
temp*=10;
return(num/temp)%10;
}
/********************************************************
*函数名称：RadixSort
*参数说明：pDataArray无序数组；
* iDataNum为无序数据个数
*说明：基数排序
*********************************************************/
voidRadixSort(int*pDataArray,intiDataNum)
{
inti,pos,j,k;
int*radixArrays[RADIX_10];//分别为0~9的序列空间
for(i=0;i<10;i++)
{
radixArrays[i]=(int*)malloc(sizeof(int)*(iDataNum+1));
radixArrays[i][0]=0;//index为0处记录这组数据的个数
}
for(pos=1;pos<=KEYNUM_31;pos++)//从个位开始到31位
{
for(i=0;i<iDataNum;i++)//分配过程
{
intnum=GetNumInPos(pDataArray[i],pos);
intindex=++radixArrays[num][0];
radixArrays[num][index]=pDataArray[i];
}
for(i=0,j=0;i<RADIX_10;i++)//收集
{
for(k=1;k<=radixArrays[i][0];k++)
pDataArray[j++]=radixArrays[i][k];
radixArrays[i][0]=0;//复位
}
}
}
intpaixu(int*a,intn)
{
inti;
printf(" 请输入排序方法： ");
printf("1.直接插入排序 ");
printf("2.折半插入排序 ");
printf("3.希尔排序 ");
printf("4.冒泡排序 ");
printf("5.快速排序 ");
printf("6.简单选择排序 ");
printf("7.堆排序 ");
printf("8.归并排序 ");
printf("9.基数排序 ");
scanf("%d",&i);
switch(i)
{
case1: straight_insert_sort(a,n);break;
case2:bin_insert_sort(a,n);break;
case3:ShellSort(a+1,n);break;
case4:BubbleSort(a,n);break;
case5:quickSort(a,1,n);break;
case6:selectSort(a,n);break;
case7:MakeMinHeap(a+1,n);MinheapsortTodescendarray(a+1,n);
over_array(a,n);
break;
case8:MergeSort(a+1,n);break;
case9:RadixSort(a+1,n);break;
default:return0;
}
return1;
}
㈢ 用c语言编写一个希尔排序程序，新手，最好能给注释下！谢谢
网友wang1992092对希尔排序的理解有些错误，希尔排序对每个子序列进行的是直接插入排序，而不是如他所给出的选择排序。你可以先网络一下希尔排序的定义。我这里给一个C源代码，你可以试试。直接插入排序的思路是：将待排表分成两部分，一部分是已有序部分L，另一部分是待排序部分R。L初始化为只含第一个元素的表，因L现在只含一个元素，所以是有序的。然后每次从R中取出最前面的元素到tmp(相当于出队到tmp中)，然后在L中从后向前搜索插入位置，边搜索边向后移动比tmp大的元素，找到了插入位置后就将tmp插入到L中。直到R部分为空时结束。
typedef int datatype;
void InsertSort(datatype a[], int left, int right, int gap)
/*对数组a中起始下标为left，结束下标为right，步长为gap的子序列进行直接插入排序，当gap等于1时就是通常的插入排序了*/
{
int tmp, i, j;
for(i = left + gap; i <= right; i += gap){
for(tmp = a[i], j = i - gap; j >= left && a[j] > tmp; j -= gap)
a[j + gap] = a[j];
a[j + gap] = tmp;
}
}
void ShellSort(datatype a[], int left, int right)
{
int gap = (right - left + 1) / 2, i;/*步长gap初始化为n/2取下整*/
while(gap > 0)
{
for(i = left; i < gap; i++) /*对每个子序列进行直接插入排序*/
InsertSort(a, i, right, gap);
gap = gap / 2; /*将步长缩小为原来的一半并取下整*/
}
}
㈣ 数据结构课设：学生成绩处理 C语言编程 顺序存储结构 希尔排序
这是考察数据结构的单链表吧，排序方式用冒泡排序是最简单的了。
㈤ 数据结构C语言编程题 希尔排序排序和折半查找算法查找
实验一
#include<stdio.h>
#include<stdlib.h>
#defineN10
voidshellpass(inta[],intn,intd)
{
inti,j,temp;
for(i=d;i<n;i++)
{
if(a[i]<a[i-d])
{
temp=a[i];
for(j=i-d;j>=0&&temp<a[j];j-=d)
a[j+d]=a[j];
a[j+d]=temp;
}
}
}
voidshellsort(inta[],intn,intdelta[],intt)
{
inti,j;
for(i=0;i<t;i++)
{
shellpass(a,n,delta[i]);
printf("第%d趟希尔排序，增量为%d，排序之后的结果 ",i+1,delta[i]);
for(j=0;j<n;j++)
{
printf("%d ",a[j]);
}
printf(" ");
}
}
voidmain()
{
intn=N,a[N];
intb[3]={5,3,1};
inti;
printf("输入%d个数 ",n);
for(i=0;i<n;i++)
{
printf("第%d个数: ",i+1);
scanf("%d",&a[i]);
}
shellsort(a,n,b,3);
printf("最终希尔排序之后的结果 ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf(" ");
}
㈥ 排序算法课程设计
// 各种排序算法汇总.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
#include <stack>
#include <time.h>
#include <stdlib.h>
template < typename T >
class SqList
{
private:
int length;
T * r;
public://接口
SqList(int n = 0);//构造长度为n的数组
~SqList()
{
length = 0;
delete r;
r = NULL;
}
void InsertSort();//顺序插入排序
void DisPlay();//输出元素
void BInsertSort();//折半插入排序
void ShellSort(int dlta[],int t);//希尔排序
void QuickSort();//快速排序
void SelectSort();//简单选择排序
void BubbleSort();//改进冒泡排序
void Bubble_Sort2();//相邻两趟是反方向起泡的冒泡排序算法
void Bubble_Sort3();//对相邻两趟反方向算法进行化简,循环体中只包含一次冒泡
void HeapSort();//堆排序
void Build_Heap_Sort();//堆排序由小到大序号建立大根堆
void MergeSort();//归并排序
void OE_Sort();//奇偶交换排序的算法
void Q_Sort_NotRecurre();//非递归快速排序
void HeapSort_3();//三叉堆排序
public://调用
void ShellInsert(int dk);//一趟希尔排序
void QSort(int low,int high);//快速排序
int Partition(int low,int high);//一趟快速排序
int SelectMinKey(int i);//从i到length中选择最小值下标
void HeapAdjust(int s,int m);//调整s的位置,其中s+1~m有序
void HeapAdjust_3(int s,int m);//三叉堆****调整s的位置,其中s+1~m有序
void Merge(T SR[],T TR[],int i,int m,int n);//归并
void MSort(T SR[],T TR1[],int s,int t);//归并
void Easy_Sort(int low,int high);//3个数直接排序
void Build_Heap(int len);//从低下标到高下标逐个插入建堆的算法***建立大根堆**但为排序
};
template < typename T >
SqList<T>::SqList(int n = 0)
{
//srand( time(0) );
length = n;
r=new T[length+1];
T t;
cout<<"随机生成"<<n<<"个值:"<<endl;
for (int i=1;i<=length;i++)
{
//cin>>t;
r[i] = rand()%1000;
//r[i] = t;
}
for (int i=1; i<=length;i++)
cout<<r[i]<<",";
cout<<endl;
}
template < typename T >
void SqList<T>::InsertSort()
{
int i,j;
for (i=2;i<=length;i++)
{
if (r[i]<r[i-1])
{
r[0]=r[i];
r[i]=r[i-1];
for (j=i-2;r[0]<r[i-2];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
}
template < typename T >
void SqList<T>::DisPlay()
{
int i;
cout<<length<<" 元素为："<<endl;
for (i = 1;i < length+1;i++ )
{
cout<<r[i]<<" ,";
}
cout<<endl;
}
template < typename T >
void SqList<T>::BInsertSort()
{
int i, j, m;
int low,high;
for (i = 2;i<= length;i++)
{
r[0]=r[i];
low=1;
high=i-1;
while (low<=high)
{
m = (low+high)/2;
if ( r[0] < r[m] )
high=m-1;
else
low=m+1;
}
for ( j=i-1;j >=high+1; j--)
{
r[j+1] = r[j];
}
r[high+1] = r[0];
}
}
template < typename T >
void SqList<T>::ShellInsert(int dk)
{
int i,j;
for (i=dk+1;i<=length;i++)
if (r[i] < r[i-dk])
{
r[0] = r[i];
for ( j=i-dk; j>0 && r[0] < r[j]; j-=dk)
{
r[j+dk]=r[j];
}
r[j+dk] = r[0];
}
}
template < typename T >
void SqList<T>::ShellSort(int dlta[],int t)
{
int k=0;
for (;k<t;k++)
{
ShellInsert(dlta[k]);
}
}
template < typename T >
int SqList<T>::Partition(int low,int high)
{
int pivotkey;
r[0] = r[low];//记录枢轴值
pivotkey = r[low];
while (low < high)
{
while (low < high&& r[high] >= pivotkey)
high--;
r[low] = r[high];
while (low < high&& r[low] <= pivotkey)
low++;
r[high] = r[low];
}
r[low] = r[0];//枢轴记录到位
return low;//返回枢轴位置
}
template < typename T >
void SqList<T>::QSort(int low,int high)
{
int pivotloc;
if (low < high)
{
pivotloc = Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
template < typename T >
void SqList<T>::QuickSort()
{
QSort(1,length);
}
template < typename T >
int SqList<T>::SelectMinKey(int i)
{
int j,min=i;
for (j=i;j <= length;j++)
{
if (r[min] > r[j])
{
min = j;
}
}
return min;
}
template < typename T >
void SqList<T>::SelectSort()
{
int i,j;
T t;
for (i=1;i < length;i++)//循环length-1次不是length次
{
j=SelectMinKey(i);
if (i != j)
{
t= r[j];
r[j]=r[i];
r[i]=t;
}
}
}
template < typename T >
void SqList<T>::BubbleSort()
{
int i,j;
int flag=1;//标识位，如果出现0，则没有交换，立即停止
T t;
for (i=1;i < length && flag;i++)
{
flag = 0;
for (j=length-1;j>=i;j--)
if (r[j]>r[j+1])
{
t=r[j];
r[j]=r[j+1];
r[j+1]=t;
flag=1;
}
}
}
template < typename T >
void SqList<T>::Bubble_Sort2()
{
bool change = true;
int low = 1, high = length;
int i;
T t;
while ( (low < high) && change )
{
change = false;
for ( i = low; i < high; i++ )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
high-=1;
for ( i = high; i > low; i-- )
{
if ( r[i] < r[i-1] )
{
t = r[i];
r[i] = r[i-1];
r[i-1] = t;
change = true;
}
}
low+=1;
}
}
template < typename T >
void SqList<T>::Bubble_Sort3()
{
int i,d=1;
bool change = true;
int b[3] = {1,0,length};//b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
T t;
while (change)//如果一趟无交换，则停止
{
change = false;
for ( i=b[1-d]; i!=b[1+d]; i=i+d )//统一的冒泡算法
{
if ( (r[i]-r[i+d])*d > 0 )///注意这个交换条件
{
t = r[i];
r[i] = r[i+d];
r[i+d] = t;
change = true;
}
}
d = d*(-1);//换个方向
}
}
template < typename T >
void SqList<T>::HeapAdjust(int s,int m)
{
/* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
int j;
T rc = r[s];
for (j=2*s;j <= m;j*=2)
{
/* 沿key较大的孩子结点向下筛选 */
if (j < m && r[j] < r[j+1])
j++;/* j为key较大的记录的下标 */
if (rc >= r[j])
break;/* rc应插入在位置s上 ,无需移动*/
r[s]=r[j];
s=j;
}
r[s]=rc;/* 插入 */
}
template < typename T >
void SqList<T>::HeapSort()
{
/* 对顺序表H进行堆排序。算法10.11 */
T t;
int i;
for (i=length/2;i>0;i--)/* 把H.r[1..H.length]建成大顶堆 */
HeapAdjust(i,length);
for (i=length;i>1;i--)
{
/* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
t=r[1];
r[1]=r[i];
r[i]=t;
HeapAdjust(1,i-1);/* 将H.r[1..i-1]重新调整为大顶堆 */
}
}
template < typename T >
void SqList<T>::Build_Heap_Sort()
{
int i;
Build_Heap(length);
for ( i = length; i > 1; i-- )
{
T t;
t = r[i];
r[i] = r[1];
r[1] = t;
Build_Heap(i-1);
}
}
template < typename T >
void SqList<T>::Build_Heap(int len)
{
T t;
for (int i=2; i <= len; i++ )
{
int j = i;
while ( j != 1 )
{
int k = j/2;
if ( r[j] > r[k] )
{
t = r[j];
r[j] = r[k];
r[k] = t;
}
j = k;
}
}
}
template < typename T >
void SqList<T>::Merge(T SR[],T TR[],int i,int m,int n)
{
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
int j,k,x;
for (j=m+1,k=i;j<=n&&i<=m;k++)/* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if (i<=m)
for (x=0;x<=m-i;x++)
TR[k+x]=SR[i+x];/* 将剩余的SR[i..m]复制到TR */
if (j<=n)
for (x=0;x<=n-j;x++)
TR[k+x]=SR[j+x];/* 将剩余的SR[j..n]复制到TR */
}
template < typename T >
void SqList<T>::MSort(T SR[],T TR1[],int s,int t)
{
/* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */
int m;
T *TR2=new T[length+1];
if (s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2;/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m);/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t);/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t);/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
template < typename T >
void SqList<T>::MergeSort()
{
MSort(r,r,1,length);
}
template < typename T >
void SqList<T>::OE_Sort()
{
int i;
T t;
bool change = true;
while ( change )
{
change = false;
for ( i=1;i<length;i+=2 )
{
if (r[i] > r[i+1])
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
for ( i=2;i<length;i+=2 )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
}
}
typedef struct
{
int low;
int high;
}boundary;
template <typename T >
void SqList<T>::Q_Sort_NotRecurre()
{
int low=1,high=length;
int piv;
boundary bo1,bo2;
stack<boundary> st;
while (low < high)
{
piv = Partition(low,high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
high = low;
}
}
while ( !st.empty() )
{
bo2 = st.top();
st.pop();
low = bo2.low;
high = bo2.high;
piv = Partition(low, high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
}
}
}
template < typename T >
void SqList<T>::Easy_Sort(int low,int high)
{
T t;
if ( (high-low) == 1 )
{
if ( r[low] > r[high] )
{
t = r[low];
r[low] = r[high];
r[high] = t;
}
}
else
{
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
if ( r[low+1] > r[high] )
{
t = r[low+1];
r[low+1] = r[high];
r[high] = t;
}
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
}
}
template < typename T >
void SqList<T>::HeapAdjust_3(int s,int m)
{
T rc = r[s];
for (int j = 3*s-1; j <= m;j=j*3-1)
{
if (j+1<m)//有3个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] && rc>=r[j+2] )
break;
else
{
if ( r[j] > r[j+1] )
{
if ( r[j] > r[j+2] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
else//r[j]<=r[j+1]
{
if ( r[j+1] > r[j+2] )
{
r[s]=r[j+1];
s=j+1;
}
else//r[j+1]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
}
}
if ( j+1==m )//有2个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] )
break;
else
{
if ( r[j] > r[j+1] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+1]
{
r[s]=r[j+1];
s=j+1;
}
}
}
if (j==m)//有1个孩子结点
{
if ( rc>=r[j] )
break;
else
{
r[s]=r[j];
s=j;
}
}
}
r[s]=rc;
}
template <typename T >
void SqList<T>::HeapSort_3()
{
int i;
T t;
for (i=length/3; i>0; i--)
HeapAdjust_3(i,length);
for ( i=length; i > 1; i-- )
{
t = r[i];
r[i] = r[1];
r[1] = t;
HeapAdjust_3(1,i-1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
SqList<int> Sq(15);
//Sq.InsertSort();
//Sq.BInsertSort();
/* 希尔排序*/
// int a[5]={5,4,3,2,1};
// Sq.ShellSort(a,5);
/* Sq.QuickSort();*/
// Sq.SelectSort();
/* Sq.BubbleSort();*/
/* Sq.HeapSort();*/
/* Sq.MergeSort();*/
/* Sq.Q_Sort_NotRecurre();*/
/* Sq.Bubble_Sort2();*/
/* Sq.OE_Sort();*/
/* Sq.Bubble_Sort3();*/
/* Sq.Build_Heap_Sort();*/
Sq.HeapSort_3();
Sq.DisPlay();
system("pause");
return 1;
}
㈦ 这是用C语言实现的希尔排序，求大神指教
你好！
你是想说你的程序运行的错误？你的int
i,a[10]这儿的逗号是中文逗号吧。
如果对你有帮助，望采纳。
㈧ 急求希尔排序完整程序C语言版的
#include <stdio.h>
void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void selsort(int a[], int n, int incr)
{
int i, j;
for (i = incr; i < n; i += incr)
for (j = i; (j >= incr)
&& (a[j] < a[j-incr]); j -= incr)
swap(a, j, j-incr);
}
void shellsort(int a[], int n)
{
int i, j;
for (i = n / 2; i > 2; i /= 2)
for (j = 0; j < i; j++)
selsort(&a[j], n - j, i);
selsort(a, n, 1);
}
int main()
{
int i;
int a[10] = {2, 1, 9, 0, 8, 3, 7, 5, 6, 4};
shellsort(a, 10);
for (i = 0; i < 10 ; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
㈨ c语言希尔排序
voidShellInsertSort(inta[],intn,intdk)
{
for(inti=dk;i<n;++i){
if(a[i]<a[i-dk]){//若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
intj=i-dk;
intx=a[i];//复制为哨兵，即存储待排序元素
a[i]=a[i-dk];//首先后移一个元素
while(x<a[j]){//查找在有序表的插入位置
a[j+dk]=a[j];
j-=dk;//元素后移
}
a[j+dk]=x;//插入到正确位置
}
}
}
/**
*先按增量d（n/2,n为要排序数的个数进行希尔排序
*
*/
voidshellSort(inta[],intn){
intdk=n/2;
while(dk>=1){
ShellInsertSort(a,n,dk);
dk=dk/2;
}
}
㈩ 希尔排序，选择排序，插入排序，堆排序的c语言实现
希尔排序算法
void Shellinsert ( SqList &L, int dk ) {
// 对顺序表 L 作一趟希尔插入排序。此算法和一趟直接插入排序相比，作了以下修改：
// (1) 前后记录为止的增量是 dk，而不是 1；
// (2) r[0] 只是暂存单元，而不是哨兵。当 j <= 0 时，插入位置已经找到。
for ( i = dk+1; i <=L.length; ++i )
if ( L.r[i].key < L.r[i-dk].key ) { // 需要将 L.r[i] 插入有序增量子表
L.r[0] = L.r[i]; // 暂存在 L.r[0]
for ( j = i-dk; j > 0 && ( L.r[0].key < L.r[j].key ); j -= dk )
L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置
L.r[j+dk] = L.r[0]; // 插入到正确位置
} // if 结束
} // ShellInsert