锐客网

  1. 首页 > 睿知 > it技术 > >

包含c语言sift函数的词条

IT技术排序

c语言 数据结构 利用随机函数产生N个随机整数，对这些数进行多种方法进行排序srand(time(NULL)); //产生随机数
for(i = 0; in; i)
a[i] = rand()%(n - i);
extern void insert(int a[], int x) //插入排序
{
int i;
int n;
int j;
int temp;
n = x;
for(i = 1; in; i)
{
temp = a[i];
j = i - 1;
while(tempa[j]j = 0)
{
a[j1] = a[j];
j--;
}
a[j1] = temp;
}
}
static void shellsort(int a[], int d, int x)
{
int i;
int j;
int n;
int temp;
n = x;
for(i = d; in; i= d)
{
temp = a[i];
j = i - d;
while(a[j]tempj = 0)
{
a[jd] = a[j];
j -= d;
}
a[jd] = temp;
}
}
extern void shell(int a[], int x) //希尔排序
{
int n;
int d;
n = x;
d = n / 2;
while(d0)
{
shellsort(a, d, n);
d /= 2;
}
}
extern void bubble(int a[], int x) //冒泡排序
{
int ischange;
int i;
int j;
int n;
n = x;
for(i = n - 1; i0; i--)
{
ischange = 0;
for(j = 0; ji; j)
{
if(a[j1]a[j])
{
a[j1]= a[j];
a[j] = a[j1] - a[j];
a[j1] = a[j1] - a[j];
ischange = 1;
}
}
if(0 == ischange)
{
break;
}
}
}
static int partion(int a[], int left, int right)
{
int l;
int r;
int priv;
l = left;
r = right;
priv = a[l];
while(lr)
{
while(a[r]privrl)
r--;
if(lr)
{
a[l] = a[r];
}
while(a[l]privrl)
l;
if(lr)
{
a[r--] = a[l];
}
}
a[l] = priv;
return l;
}
static void quicksort(int a[], int left, int right)
{
int l;
int r;
int priv;
l = left;
r = right;
if(lr)
{
priv = partion(a, l, r);
quicksort(a, l, priv - 1);
quicksort(a, priv1, r);
}
}
extern void quick(int a[], int n) //快速排序
{
int l;
int r;
l = 0;
r = n - 1;
quicksort(a, l, r);
}
extern void selec(int a[], int x) //选择排序
{
int i;
int j;
int k;
int n;
n = x;
for(i = 0; in; i)
{
k = i;
for(j = i; jn; j)
{
if(a[j]a[k])
{
k = j;
}
}
if(i != k)
{
a[i]= a[k];
a[k] = a[i] - a[k];
a[i] -= a[k];
}
}
}
static void mergearray(int a[], int first, int mid, int last, int p[])
{
int i;
int j;
int k;
i = first;
j = mid1;
k = 0;
while(i = midj = last)
{
if(a[i] = a[j])
{
p[k] = a[i];
}
else
{
p[k] = a[j];
}
}
while(i = mid)
{
p[k] = a[i];
}
while(j = last)
{
p[k] = a[j];
}
for(i = 0; ik; i)
{
a[firsti] = p[i];
}
}
static void mergesort(int a[], int first, int last, int p[])
{
int mid;
if(lastfirst)
{
mid = first(last - first) / 2;
mergesort(a, first, mid, p);
mergesort(a, mid1, last, p);
mergearray(a, first, mid, last, p);
}
}
extern void merge(int a[], int n) 归并排序
{
int *p;
p = (int *)malloc(n * sizeof(int));
if(!p)
{
perror("malloc");
exit(-1);
}
mergesort(a, 0, n - 1, p);
free(p);
}
static void swap(int data[], int a, int b)
{
data[a] ^= data[b];
data[b] ^= data[a];
data[a] ^= data[b];
}
static void siftup(int data[], int n) // create heap
{
int i;
int p;
for(i = n; i1data[p = i / 2]data[i]; i = p)
swap(data, p, i);
}
static void siftdown(int data[], int n) // adjust heap
{
int i;
int c;
i = 1;
while(1)
{
c = 2 * i;
if(cn)
break;
if(c1 = ndata[c1]data[c])
c;
if(data[i] = data[c])
break;
swap(data, c, i);
i = c;
}
}
static void heapsort(int data[], int n)
{
int i;
for(i = 2; i = n; i)
{
siftup(data, i);
}
for(i = n; i = 2; i--)
{
swap(data, 1, i);
siftdown(data, i - 1);
}
}
extern void heap(int a[], int n) //堆排序
{
int *p;
int i;
p = (int *)malloc((n1) * sizeof(int));
if(!p)
{
perror("malloc");
}
for(i = 0; in; i)
*(pi1) = a[i];
heapsort(p, n);
for(i = 0; in; i)
a[i] = *(pi1);
free(p);
}
基数排序根据你是N进制数，申请N个队列，以空间换取时间，排序复杂度为线性o(n)
排序算法的设计（c语言）根据程序画流程图及对每句程序加注释#include "stdio.h"//标准io头文件
#include "stdlib.h"//库文件
#include "time.h"//时间系头文件
#define N0 100000 //定义常量
typedef int keytype; //类型命名
typedef struct node //定义结构体
{keytype key; //只是类型命名成keytype ， 其实就是int的
}Etp;//结构体类型叫做Etp
Etp R[N0 1]; // R[1]..R[n] //定义数组
int n=50, count;//全局变量
void readData( Etp R[], int n)//读数据的函数
{int i;
count=0;
srand( time( NULL ));//初始化时间种子
for( i=1; i=n; i) //对数组初始化
R[i].key=1000
(int)((9999.0-1000)*rand()/RAND_MAX); // 0..RAND_MAX
}
void printData( Etp R[], int n )//打印显示数据的函数
{ int i;
for( i=1; i=n; i)
printf("%峴", //格式化显示数组的数据
R[i].key, i%5==0?"\n":"");
printf("\ncount=%d\n", count);
}
void bubberSort( Etp R[], int n )//冒泡排序的函数
{ int i,j;//（这个函数块就是冒泡排序的算法程序）
bool swap;
for( i=1; i=n-1; i)
{ swap=false;
for( j=1; j=n-i; j)
if( count,R[j].keyR[j 1].key )
{ R[0]=R[j];
R[j]=R[j 1];
R[j 1]=R[0];
swap=true;
}
if( !swap ) break;
}
}
void bubberSort1( Etp R[], int n )//这个也是另一个冒泡排序的函数
{ int j;//跟上面不同的是这个算法用的是递归的方式，上面的是非递归的
for( j=1; j=n-1; j)
if( count,R[j].keyR[j 1].key )
{ R[0]=R[j];
R[j]=R[j 1];//________;//就是两个变量交换值
R[j 1]=R[0];
}
if( n1 ) bubberSort1( R, n-1); //___________;//递归调用
}
void selectSort( Etp R[], int n )//这个是选择排序
{ int i,j,k;//（这个函数块就是选择排序的算法程序）
for( i=1; i=n-1; i)
{
k=i;
for( j=i 1; j=n; j)
if( count,R[j].keyR[k].key ) k=j;
if( k!=i )
{ R[0]=R[i];
R[i]=R[k];
R[k]=R[0];
}
}
}
void insertSort( Etp R[], int n )//这个是插入排序
{ int i,j;
for( i=2; i=n; i)
{
R[0]=R[i];
j=i-1;
while( count,R[j].keyR[0].key ) R[j 1]=R[j--];
R[j 1]=R[0];
count;
}
}
void sift( Etp R[], int i, int m)//堆排序中的步骤
{ int k=2*i;
R[0]=R[i];
while( k=m )
{ if( count, k 1=mR[k 1].keyR[k].key) k;
if( count,R[0].keyR[k].key )R[i]=R[k];
else break;
i=k;
k=2*i;
}
R[i]=R[0];
}
void heapSort( Etp R[], int n )//这个是堆排序
{ int j;
for( j=n/2; j=1; j--) sift( R, j, n);
for( j=n; j=2; j--)
{ R[0]=R[1];
R[1]=R[j];
R[j]=R[0];
sift( R, 1, j-1 );
}
}
int main()//主函数的进入口
{
readData( R, n );//读取数据
bubberSort1( R, n );//调用递归冒泡排序
printData( R, n);//显示数据
readData( R, n );//读取数据
selectSort( R, n );//调用选择排序
printData( R, n);//显示数据
readData( R, n );//读取数据
insertSort( R, n );//调用插入排序
printData( R, n);//显示数据
readData( R, n );//读取数据
heapSort( R, n );//调用堆排序
printData( R, n);//显示数据
return 0;
}
//诶·~注释完我总算看出来了，难道你要我解释各个排序的过程？
//那你还不如直接baidu或者看书，你要是不理解原理是不可能看懂过程的 。
//注释也只是语句的解释，但是过程的含义是无法描述的
求c语言的一个程序编码*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中c语言sift函数，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换c语言sift函数，如此循环
到倒数第二个数和最后一个数比较为止 。
选择排序是不稳定的 。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void
select_sort(int
*x,
int
n)
{
int
i,
j,
min,
t;
for
(i=0;
in-1;
i)
/*要选择的次数：0~n-2共n-1次*/
{
min
=
i;
/*假设当前下标为i的数最小c语言sift函数，比较后再调整*/
for
(j=i 1;
jn;
j)/*循环找出最小的数的下标是哪个*/
{
if
(*(x j)
*(x min))
{
min
=
j;
/*如果后面的数比前面的小 ， 则记下它的下标*/
}
}
if
(min
!=
i)
/*如果min在循环中改变了，就需要交换数据*/
{
t
=
*(x i);
*(x i)
=
*(x min);
*(x min)
=
t;
}
}
}
/*
================================================
功能：直接插入排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中 ， 假设前面(n-1)
[n=2]
个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的 。如此反复循环，直到全部排好顺序 。
直接插入排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void
insert_sort(int
*x,
int
n)
{
int
i,
j,
t;
for
(i=1;
in;
i)
/*要选择的次数：1~n-1共n-1次*/
{
/*
暂存下标为i的数 。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数 ， 前面没有任何数 ， 单单一个，认为
它是排好顺序的 。
*/
t=*(x i);
for
(j=i-1;
j=0
t*(x j);
j--)
/*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置 。*/
{
*(x j 1)
=
*(x j);
/*如果满足条件就往后挪 。最坏的情况就是t比下标为0的数都?。旁谧钋懊?，j==-1，退出循环*/
}
*(x j 1)
=
t;
/*找到下标为i的数的放置位置*/
}
}
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，对当前还未排好序的范围内的全部数 ， 自上
而下对相邻的两个数依次进行比较和调整 ， 让较大的数往下沉，较
小的往上冒 。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时 ， 就将它们互换 。
下面是一种改进的冒泡算法 ， 它记录了每一遍扫描后最后下沉数的
位置k，这样可以减少外层循环扫描的次数 。
冒泡排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void
bubble_sort(int
*x,
int
n)
{
int
j,
k,
h,
t;
for
(h=n-1;
h0;
h=k)
/*循环到没有比较范围*/
{
for
(j=0,
k=0;
jh;
j)
/*每次预置k=0，循环扫描后更新k*/
{
if
(*(x j)
*(x j 1))
/*大的放在后面 ， 小的放到前面*/
{
t
=
*(x j);
*(x j)
=
*(x j 1);
*(x j 1)
=
t;
/*完成交换*/
k
=
j;
/*保存最后下沉的位置 。这样k后面的都是排序排好了的 。*/
}
}
}
}
/*
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助 。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换 。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想 。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序 。当增量减到1时 ， 整个要排序的数被分成
一组，排序完成 。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1 。
希尔排序是不稳定的 。
=====================================================
*/
void
shell_sort(int
*x,
int
n)
{
int
h,
j,
k,
t;
for
(h=n/2;
h0;
h=h/2)
/*控制增量*/
{
for
(j=h;
jn;
j)
/*这个实际上就是上面的直接插入排序*/
{
t
=
*(x j);
for
(k=j-h;
(k=0
t*(x k));
k-=h)
{
*(x k h)
=
*(x k);
}
*(x k h)
=
t;
}
}
}
/*
================================================
功能：快速排序
输入：数组名称（也就是数组首地址）、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述：
快速排序是对冒泡排序的一种本质改进 。它的基本思想是通过一趟
扫描后，使得排序序列的长度能大幅度地减少 。在冒泡排序中，一次
扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
减少1 。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
的左边各数都比它?。?右边各数都比它大 。然后又用同样的方法处理
它左右两边的数，直到基准点的左右只有一个元素为止 。它是由
C.A.R.Hoare于1962年提出的 。
显然快速排序可以用递归实现，当然也可以用栈化解递归实现 。下面的
函数是用递归实现的，有兴趣的朋友可以改成非递归的 。
快速排序是不稳定的 。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void
quick_sort(int
*x,
int
low,
int
high)
{
int
i,
j,
t;
if
(low
high)
/*要排序的元素起止下标，保证小的放在左边 ， 大的放在右边 。这里以下标为low的元素为基准点*/
{
i
=
low;
j
=
high;
t
=
*(x low);
/*暂存基准点的数*/
while
(ij)
/*循环扫描*/
{
while
(ij
*(x j)t)
/*在右边的只要比基准点大仍放在右边*/
{
j--;
/*前移一个位置*/
}
if
(ij)
{
*(x i)
=
*(x j);
/*上面的循环退出：即出现比基准点小的数 ， 替换基准点的数*/
i;
/*后移一个位置，并以此为基准点*/
}
while
(ij
*(x i)=t)
/*在左边的只要小于等于基准点仍放在左边*/
{
i;
/*后移一个位置*/
}
if
(ij)
{
*(x j)
=
*(x i);
/*上面的循环退出：即出现比基准点大的数，放到右边*/
j--;
/*前移一个位置*/
}
}
*(x i)
=
t;
/*一遍扫描完后 ， 放到适当位置*/
quick_sort(x,low,i-1);
/*对基准点左边的数再执行快速排序*/
quick_sort(x,i 1,high);
/*对基准点右边的数再执行快速排序*/
}
}
/*
================================================
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
堆排序是一种树形选择排序，是对直接选择排序的有效改进 。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi=h2i,hi=2i 1）或（hi=h2i,hi=2i 1）(i=1,2,...,n/2)
时称之为堆 。在这里只讨论满足前者条件的堆 。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项 。完全二叉树可以
很直观地表示堆的结构 。堆顶为根，其它为左子树、右子树 。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆，这时堆的根节点的数最大 。然后将根节点与堆的最后一个节点
交换 。然后对前面(n-1)个数重新调整使之成为堆 。依此类推，直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列 。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置 。所以堆排序有两个函数组成 。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数 。
堆排序是不稳定的 。算法时间复杂度O(nlog2n) 。
*/
/*
功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
*/
void
sift(int
*x,
int
n,
int
s)
{
int
t,
k,
j;
t
=
*(x s);
/*暂存开始元素*/
k
=
s;
/*开始元素下标*/
j
=
2*k
1;
/*右子树元素下标*/
while
(jn)
{
if
(jn-1
*(x j)
*(x j 1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整 。*/
{
j;
}
if
(t*(x j))
/*调整*/
{
*(x k)
=
*(x j);
k
=
j;
/*调整后，开始元素也随之调整*/
j
=
2*k
1;
}
else
/*没有需要调整了 ， 已经是个堆了 ， 退出循环 。*/
{
break;
}
}
*(x k)
=
t;
/*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void
heap_sort(int
*x,
int
n)
{
int
i,
k,
t;
int
*p;
for
(i=n/2-1;
i=0;
i--)
{
sift(x,n,i);
/*初始建堆*/
}
for
(k=n-1;
k=1;
k--)
{
t
=
*(x 0);
/*堆顶放到最后*/
*(x 0)
=
*(x k);
*(x k)
=
t;
sift(x,k,0);
/*剩下的数再建堆*/
}
}
void
main()
{
#define
MAX
4
int
*p,
i,
a[MAX];
/*录入测试数据*/
p
=
a;
printf("Input
%d
number
for
sorting
:\n",MAX);
for
(i=0;
iMAX;
i)
{
scanf("%d",p);
}
printf("\n");
/*测试选择排序*/
p
=
a;
select_sort(p,MAX);
/**/
/*测试直接插入排序*/
/*
p
=
a;
insert_sort(p,MAX);
*/
/*测试冒泡排序*/
/*
p
=
a;
insert_sort(p,MAX);
*/
/*测试快速排序*/
/*
p
=
a;
quick_sort(p,0,MAX-1);
*/
/*测试堆排序*/
/*
p
=
a;
heap_sort(p,MAX);
*/
for
(p=a,
i=0;
iMAX;
i)
{
printf("%d
",*p);
}
printf("\n");
system("pause");
}
基于C语言的几种排序算法的分析相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后 ， 仍能保持它们在排序之前的相对次序，我们就
说这种排序方法是稳定的 。反之，就是非稳定的 。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面 。假如变成a1,a4,
a2,a3,a5就不是稳定的了 。
2、内排序和外排序
在排序过程中 ， 所有需要排序的数都在内存，并在内存中调整它们的存储顺序 ， 称为内排序；
在排序过程中，只有部分数被调入内存 ， 并借助内存调整数在外存中的存放顺序排序方法称为外排序 。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量 。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间 。
================================================================================
*/
/*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中 ， 选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止 。
选择排序是不稳定的 。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;
for (i=0; in-1; i) /*要选择的次数：0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最?。冉虾笤俚髡?/
for (j=i 1; jn; j)/*循环找出最小的数的下标是哪个*/
{
if (*(x j)*(x min))
{
min = j; /*如果后面的数比前面的小，则记下它的下标*/
}
}
if (min != i) /*如果min在循环中改变了，就需要交换数据*/
{
t = *(x i);
*(x i) = *(x min);
*(x min) = t;
}
}
}
/*
================================================
功能：直接插入排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，假设前面(n-1) [n=2] 个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的 。如此反复循环，直到全部排好顺序 。
直接插入排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;
for (i=1; in; i) /*要选择的次数：1~n-1共n-1次*/
{
/*
暂存下标为i的数 。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数，前面没有任何数，单单一个 ， 认为
它是排好顺序的 。
*/
t=*(x i);
for (j=i-1; j=0t*(x j); j--) /*注意：j=i-1，j--，这里就是下标为i的数，在它前面有序列中找插入位置 。*/
{
*(x j 1) = *(x j); /*如果满足条件就往后挪 。最坏的情况就是t比下标为0的数都小 ， 它要放在最前面 ， j==-1 ， 退出循环*/
}
*(x j 1) = t; /*找到下标为i的数的放置位置*/
}
}
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒 。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们互换 。
下面是一种改进的冒泡算法 ， 它记录了每一遍扫描后最后下沉数的
位置k ， 这样可以减少外层循环扫描的次数 。
冒泡排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h0; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; jh; j) /*每次预置k=0，循环扫描后更新k*/
{
if (*(x j)*(x j 1)) /*大的放在后面 ， 小的放到前面*/
{
t = *(x j);
*(x j) = *(x j 1);
*(x j 1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置 。这样k后面的都是排序排好了的 。*/
}
}
}
}
/*
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中 ， 每次插入一个数 ， 使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助 。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换 。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想 。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序 。当增量减到1时，整个要排序的数被分成
一组，排序完成 。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1 。
希尔排序是不稳定的 。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h0; h=h/2) /*控制增量*/
{
for (j=h; jn; j) /*这个实际上就是上面的直接插入排序*/
{
t = *(x j);
for (k=j-h; (k=0t*(x k)); k-=h)
{
*(x k h) = *(x k);
}
*(x k h) = t;
}
}
}
/*
================================================
功能：快速排序
输入：数组名称（也就是数组首地址）、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述：
快速排序是对冒泡排序的一种本质改进 。它的基本思想是通过一趟
扫描后，使得排序序列的长度能大幅度地减少 。在冒泡排序中 ， 一次
扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
减少1 。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
的左边各数都比它?。冶吒魇急人?。然后又用同样的方法处理
它左右两边的数，直到基准点的左右只有一个元素为止 。它是由
C.A.R.Hoare于1962年提出的 。
显然快速排序可以用递归实现，当然也可以用栈化解递归实现 。下面的
函数是用递归实现的，有兴趣的朋友可以改成非递归的 。
快速排序是不稳定的 。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (lowhigh) /*要排序的元素起止下标 ， 保证小的放在左边 ， 大的放在右边 。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x low); /*暂存基准点的数*/
while (ij) /*循环扫描*/
{
while (ij*(x j)t) /*在右边的只要比基准点大仍放在右边*/
{
j--; /*前移一个位置*/
}
if (ij)
{
*(x i) = *(x j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
i; /*后移一个位置，并以此为基准点*/
}
while (ij*(x i)=t) /*在左边的只要小于等于基准点仍放在左边*/
{
i; /*后移一个位置*/
}
if (ij)
{
*(x j) = *(x i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
j--; /*前移一个位置*/
}
}
*(x i) = t; /*一遍扫描完后 ， 放到适当位置*/
quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
quick_sort(x,i 1,high); /*对基准点右边的数再执行快速排序*/
}
}
/*
================================================
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
堆排序是一种树形选择排序，是对直接选择排序的有效改进 。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi=h2i,hi=2i 1）或（hi=h2i,hi=2i 1）(i=1,2,...,n/2)
时称之为堆 。在这里只讨论满足前者条件的堆 。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项 。完全二叉树可以
很直观地表示堆的结构 。堆顶为根 ， 其它为左子树、右子树 。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆 ， 这时堆的根节点的数最大 。然后将根节点与堆的最后一个节点
交换 。然后对前面(n-1)个数重新调整使之成为堆 。依此类推，直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列 。
从算法描述来看，堆排序需要两个过程，一是建立堆 ， 二是堆顶与堆的最后一个元素
交换位置 。所以堆排序有两个函数组成 。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数 。
堆排序是不稳定的 。算法时间复杂度O(nlog2n) 。
*/
/*
功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k1; /*右子树元素下标*/
while (jn)
{
if (jn-1*(x j)*(x j 1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整 。*/
{
j;
}
if (t*(x j)) /*调整*/
{
*(x k) = *(x j);
k = j; /*调整后，开始元素也随之调整*/
j = 2*k1;
}
else /*没有需要调整了，已经是个堆了，退出循环 。*/
{
break;
}
}
*(x k) = t; /*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k=1; k--)
{
t = *(x 0); /*堆顶放到最后*/
*(x 0) = *(x k);
*(x k) = t;
sift(x,k,0); /*剩下的数再建堆*/
}
}
void main()
{
#define MAX 4
int *p, i, a[MAX];
/*录入测试数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; iMAX; i)
{
scanf("%d",p);
}
printf("\n");
/*测试选择排序*/
p = a;
select_sort(p,MAX);
/**/
/*测试直接插入排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试冒泡排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试快速排序*/
/*
p = a;
quick_sort(p,0,MAX-1);
*/
/*测试堆排序*/
/*
p = a;
heap_sort(p,MAX);
*/
for (p=a, i=0; iMAX; i)
{
printf("%d ",*p);
}
printf("\n");
system("pause");
}
什么是(c语言编程)顺序比较法,不是冒泡和选择额顺序比较法，就是冒泡呀 。。。
答案由提问者自己选择，并不代表爱问知识人的观点 揪错 ┆ 评论 ┆ 举报
祥子
[学者]相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）：
1、稳定排序和非稳定排序
简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就
说这种排序方法是稳定的 。反之，就是非稳定的 。
比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5 ，
则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面 。假如变成a1,a4,
a2,a3,a5就不是稳定的了 。
2、内排序和外排序
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；
在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序 。
3、算法的时间复杂度和空间复杂度
所谓算法的时间复杂度，是指执行算法所需要的计算工作量 。
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间 。
================================================================================
*/
/*
================================================
功能：选择排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止 。
选择排序是不稳定的 。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;
for (i=0; in-1; i) /*要选择的次数：0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最?。?比较后再调整*/
for (j=i 1; jn; j)/*循环找出最小的数的下标是哪个*/
{
if (*(x j)*(x min))
{
min = j; /*如果后面的数比前面的小 ， 则记下它的下标*/
}
}
if (min != i) /*如果min在循环中改变了 ， 就需要交换数据*/
{
t = *(x i);
*(x i) = *(x min);
*(x min) = t;
}
}
}
/*
================================================
功能：直接插入排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，假设前面(n-1) [n=2] 个数已经是排
好顺序的 ， 现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的 。如此反复循环，直到全部排好顺序 。
直接插入排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;
for (i=1; in; i) /*要选择的次数：1~n-1共n-1次*/
{
/*
暂存下标为i的数 。注意：下标从1开始，原因就是开始时
第一个数即下标为0的数 ， 前面没有任何数，单单一个，认为
它是排好顺序的 。
*/
t=*(x i);
for (j=i-1; j=0t*(x j); j--) /*注意：j=i-1，j-- ， 这里就是下标为i的数，在它前面有序列中找插入位置 。*/
{
*(x j 1) = *(x j); /*如果满足条件就往后挪 。最坏的情况就是t比下标为0的数都小 ， 它要放在最前面，j==-1，退出循环*/
}
*(x j 1) = t; /*找到下标为i的数的放置位置*/
}
}
/*
================================================
功能：冒泡排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒 。即：每当两相邻的数比较后发现它们的排序与排序要
求相反时，就将它们互换 。
下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的
位置k，这样可以减少外层循环扫描的次数 。
冒泡排序是稳定的 。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void bubble_sort(int *x, int n)
{
int j, k, h, t;
for (h=n-1; h0; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; jh; j) /*每次预置k=0 ， 循环扫描后更新k*/
{
if (*(x j)*(x j 1)) /*大的放在后面，小的放到前面*/
{
t = *(x j);
*(x j) = *(x j 1);
*(x j 1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置 。这样k后面的都是排序排好了的 。*/
}
}
}
}
/*
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点 ，
并且对插入下一个数没有提供任何帮助 。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换 。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想 。算法先将要排序的一组数按某个增量d分成若干组 ， 每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序 。当增量减到1时，整个要排序的数被分成
一组，排序完成 。
下面的函数是一个希尔排序算法的一个实现 ， 初次取序列的一半为增量 ，
以后每次减半，直到增量为1 。
希尔排序是不稳定的 。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h0; h=h/2) /*控制增量*/
{
for (j=h; jn; j) /*这个实际上就是上面的直接插入排序*/
{
t = *(x j);
for (k=j-h; (k=0t*(x k)); k-=h)
{
*(x k h) = *(x k);
}
*(x k h) = t;
}
}
}
/*
================================================
功能：快速排序
输入：数组名称（也就是数组首地址）、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述：
快速排序是对冒泡排序的一种本质改进 。它的基本思想是通过一趟
扫描后，使得排序序列的长度能大幅度地减少 。在冒泡排序中，一次
扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
减少1 。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
的左边各数都比它?。?右边各数都比它大 。然后又用同样的方法处理
它左右两边的数，直到基准点的左右只有一个元素为止 。它是由
C.A.R.Hoare于1962年提出的 。
显然快速排序可以用递归实现 ， 当然也可以用栈化解递归实现 。下面的
函数是用递归实现的，有兴趣的朋友可以改成非递归的 。
快速排序是不稳定的 。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;
if (lowhigh) /*要排序的元素起止下标，保证小的放在左边 ， 大的放在右边 。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x low); /*暂存基准点的数*/
while (ij) /*循环扫描*/
{
while (ij*(x j)t) /*在右边的只要比基准点大仍放在右边*/
{
j--; /*前移一个位置*/
}
if (ij)
{
*(x i) = *(x j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
i; /*后移一个位置，并以此为基准点*/
}
while (ij*(x i)=t) /*在左边的只要小于等于基准点仍放在左边*/
{
i; /*后移一个位置*/
}
if (ij)
{
*(x j) = *(x i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
j--; /*前移一个位置*/
}
}
*(x i) = t; /*一遍扫描完后，放到适当位置*/
quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
quick_sort(x,i 1,high); /*对基准点右边的数再执行快速排序*/
}
}
/*
================================================
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
堆排序是一种树形选择排序 ， 是对直接选择排序的有效改进 。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi=h2i,hi=2i 1）或（hi=h2i,hi=2i 1）(i=1,2,...,n/2)
时称之为堆 。在这里只讨论满足前者条件的堆 。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项 。完全二叉树可以
很直观地表示堆的结构 。堆顶为根，其它为左子树、右子树 。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
使之成为一个堆，这时堆的根节点的数最大 。然后将根节点与堆的最后一个节点
交换 。然后对前面(n-1)个数重新调整使之成为堆 。依此类推 ， 直到只有两个节点
的堆，并对它们作交换，最后得到有n个节点的有序序列 。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置 。所以堆排序有两个函数组成 。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数 。
堆排序是不稳定的 。算法时间复杂度O(nlog2n) 。
*/
/*
功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;
t = *(x s); /*暂存开始元素*/
k = s; /*开始元素下标*/
j = 2*k1; /*右子树元素下标*/
while (jn)
{
if (jn-1*(x j)*(x j 1))/*判断是否满足堆的条件：满足就继续下一轮比较 ， 否则调整 。*/
{
j;
}
if (t*(x j)) /*调整*/
{
*(x k) = *(x j);
k = j; /*调整后，开始元素也随之调整*/
j = 2*k1;
}
else /*没有需要调整了，已经是个堆了，退出循环 。*/
{
break;
}
}
*(x k) = t; /*开始元素放到它正确位置*/
}
/*
功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;
for (i=n/2-1; i=0; i--)
{
sift(x,n,i); /*初始建堆*/
}
for (k=n-1; k=1; k--)
{
t = *(x 0); /*堆顶放到最后*/
*(x 0) = *(x k);
*(x k) = t;
sift(x,k,0); /*剩下的数再建堆*/
}
}
void main()
{
#define MAX 4
int *p, i, a[MAX];
/*录入测试数据*/
p = a;
printf("Input %d number for sorting :\n",MAX);
for (i=0; iMAX; i)
{
scanf("%d",p);
}
printf("\n");
/*测试选择排序*/
p = a;
select_sort(p,MAX);
/**/
/*测试直接插入排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试冒泡排序*/
/*
p = a;
insert_sort(p,MAX);
*/
/*测试快速排序*/
/*
p = a;
quick_sort(p,0,MAX-1);
*/
/*测试堆排序*/
/*
p = a;
heap_sort(p,MAX);
*/
for (p=a, i=0; iMAX; i)
{
printf("%d ",*p);
}
printf("\n");
system("pause");
}
------------------------------------------------------------------------------------------------Mr_computer
c语言:已知数组a中的元素(a[1]..a[n])既然其它数都已经排好,只需要排最上面一个数c语言sift函数了,算法比较简单,一看就应该能明白.我设计c语言sift函数的是从A[0]....A[N-1],如果c语言sift函数你要从A[1]...A[N]c语言sift函数的话,把那个2*I 1,2*I 2改成2*I,2*I 1即可...
#include stdio.h
void swap(int *x, int *y){
int temp = *x;
*x = *y;
*y = temp;
}
void sift(int a[],int n){//调整堆顶元素
int i = 0;
while(2*i 2n){//找出最大的与a[i]交换,如果就是本身退出循环
int max = i;
if(a[max]a[2*i 1]){
max = 2*i 1;
}
if(a[max]a[2*i 2]){
max = 2*i 2;
}
if(max == i){
break;
}
else{
swap(a[i], a[max]);
i = max;
}
}
}
int main(){
int a[8] = {10, 88, 40, 50, 76, 9, 32, 5}, i;
sift(a, 8);
for(i=0; i8; i){
printf("%d\t", a[i]);
}
printf("\n");
return 0;
}
【包含c语言sift函数的词条】关于c语言sift函数和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息 ， 记得收藏关注本站 。

    推荐阅读


    上一篇：如何开启联想服务器的电源按钮？ 联想服务器按钮怎么开启

    下一篇：翡翠打磨工具直播，翡翠用什么打磨才会细腻