希爾排序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