正文
包含c语言sift函数的词条
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
c语言 数据结构 利用随机函数产生N个随机整数，对这些数进行多种方法进行排序
srand(time(NULL)); //产生随机数
for(i = 0; i n; 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; i n; i++)
{
temp = a[i];
j = i - 1;
while(temp a[j] j = 0)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
static void shellsort(int a[], int d, int x)
{
int i;
int j;
int n;
int temp;
n = x;
for(i = d; i n; i += d)
{
temp = a[i];
j = i - d;
while(a[j] temp j = 0)
{
a[j + d] = a[j];
j -= d;
}
a[j + d] = temp;
}
}
extern void shell(int a[], int x) //希尔排序
{
int n;
int d;
n = x;
d = n / 2;
while(d 0)
{
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; i 0; i--)
{
ischange = 0;
for(j = 0; j i; j++)
{
if(a[j + 1] a[j])
{
a[j + 1] += a[j];
a[j] = a[j + 1] - a[j];
a[j + 1] = a[j + 1] - 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(l r)
{
while(a[r] priv r l)
r--;
if(l r)
{
a[l++] = a[r];
}
while(a[l] priv r l)
l++;
if(l r)
{
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(l r)
{
priv = partion(a, l, r);
quicksort(a, l, priv - 1);
quicksort(a, priv + 1, 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; i n; i++)
{
k = i;
for(j = i; j n; 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 = mid + 1;
k = 0;
while(i = mid j = 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; i k; i++)
{
a[first + i] = p[i];
}
}
static void mergesort(int a[], int first, int last, int p[])
{
int mid;
if(last first)
{
mid = first + (last - first) / 2;
mergesort(a, first, mid, p);
mergesort(a, mid + 1, 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; i 1 data[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(c n)
break;
if(c + 1 = n data[c + 1] 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((n + 1) * sizeof(int));
if(!p)
{
perror("malloc");
}
for(i = 0; i n; i++)
*(p + i + 1) = a[i];
heapsort(p, n);
for(i = 0; i n; i++)
a[i] = *(p + i + 1);
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("%8d%s", //格式化显示数组的数据
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=m R[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=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=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");
}
------------------------------------------------------------------------------------------------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+2 n){ //找出最大的与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函数和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
