c语言实现排序和查找所有算法

C语言版排序查找完成，带详细解释，一下看到爽，能直接运行看效果。

/* Note:Your choice is C IDE */

#include "stdio.h"

#include"stdlib.h"

#define MAX 10

void SequenceSearch(int *fp,int Length);

void Search(int *fp,int length);

void Sort(int *fp,int length);

/*

注意：

1、数组名x,*(x+i)就是x[i]哦

*/

/*

================================================

功能:选择排序

输入:数组名称(数组首地址)、数组中元素个数

================================================

*/

void select_sort(int *x, int n)

{

int i, j, min, t;

for (i=0; i

{

min = i; /*假设当前下标为i的数最小,比较后再调整*/

for (j=i+1; j

{

if (*(x+j) < *(x+min))

min = j; /*如果后面的数比前面的小,则记下它的下标*/

}

if (min != i) /*如果min在循环中改变了,就需要交换数据*/

{

t = *(x+i);

*(x+i) = *(x+min);

*(x+min) = t;

}

}

}

/*

================================================

功能:直接插入排序

输入:数组名称(也就是数组首地址)、数组中元素个数

================================================

*/

void insert_sort(int *x, int n)

{

int i, j, t;

for (i=1; i

{

/*

暂存下标为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的数的放置位置*/

}

}

/*

================================================

功能:冒泡排序

输入:数组名称(也就是数组首地址)、数组中元素个数

================================================

*/

void bubble_sort0(int *x, int n)

{

int j, h, t;

for (h=0; h

{

for (j=0; j

{

if (*(x+j) > *(x+j+1)) /*大的放在后面,小的放到前面*/

{

t = *(x+j);

*(x+j) = *(x+j+1);

*(x+j+1) = t; /*完成交换*/

}

}

}

}

/*优化：记录最后下沉位置，之后的肯定有序*/

void bubble_sort(int *x, int n)

{

int j, k, h, t;

for (h=n-1; h>0; h=k) /*循环到没有比较范围*/

{

for (j=0, k=0; j

{

if (*(x+j) > *(x+j+1)) /*大的放在后面,小的放到前面*/

{

t = *(x+j);

*(x+j) = *(x+j+1);

*(x+j+1) = t; /*完成交换*/

k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/

}

}

}

}

/*

================================================

功能:希尔排序

输入:数组名称(也就是数组首地址)、数组中元素个数

================================================

*/

void shell_sort(int *x, int n)

{

int h, j, k, t;

for (h=n/2; h>0; h=h/2) /*控制增量*/

{

for (j=h; j

{

t = *(x+j);

for (k=j-h; (k>=0 && t<*(x+k)); k-=h)

{

*(x+k+h) = *(x+k);

}

*(x+k+h) = t;

}

}

}

/*

================================================

功能:快速排序

输入:数组名称(也就是数组首地址)、数组中起止元素的下标

注：自己画画

================================================

*/

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 (i

{

while (it) /*在右边的只要比基准点大仍放在右边*/

{

j--; /*前移一个位置*/

}

if (i

{

*(x+i) = *(x+j); /*上面的循环退出:即出现比基准点小的数,替换基准点的数*/

i++; /*后移一个位置,并以此为基准点*/

}

while (i

{

i++; /*后移一个位置*/

}

if (i

{

*(x+j) = *(x+i); /*上面的循环退出:即出现比基准点大的数,放到右边*/

j--; /*前移一个位置*/

}

}

*(x+i) = t; /*一遍扫描完后,放到适当位置*/

quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/

quick_sort(x,i+1,high); /*对基准点右边的数再执行快速排序*/

}

}

/*

================================================

功能:堆排序

输入:数组名称(也就是数组首地址)、数组中元素个数

注：画画

================================================

*/

/*

功能:建堆

输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始

*/

void sift(int *x, int n, int s)

{

int t, k, j;

t = *(x+s); /*暂存开始元素*/

k = s; /*开始元素下标*/

j = 2*k + 1; /*左子树元素下标*/

while (j

{

if (j

{

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 Merge(int a[], int start, int mid, int end)

{

int i,k,j, temp1[10], temp2[10];

int n1, n2;

n1 = mid - start + 1;

n2 = end - mid;

// 拷贝前半部分数组

for ( i = 0; i < n1; i++)

{

temp1[i] = a[start + i];

}

// 拷贝后半部分数组

for (i = 0; i < n2; i++)

{

temp2[i] = a[mid + i + 1];

}

// 把后面的元素设置的很大

temp1[n1] = temp2[n2] = 1000;

// 合并temp1和temp2

for ( k = start, i = 0, j = 0; k <= end; k++)

{

//小的放到有顺序的数组里

if (temp1[i] <= temp2[j])

{

a[k] = temp1[i];

i++;

}

else

{

a[k] = temp2[j];

j++;

}

}

}

// 归并排序

void MergeSort(int a[], int start, int end)

{

if (start < end)

{

int i;

i = (end + start) / 2;

// 对前半部分进行排序

MergeSort(a, start, i);

// 对后半部分进行排序

MergeSort(a, i + 1, end);

// 合并前后两部分

Merge(a, start, i, end);

}

}

/*顺序查找*/

void SequenceSearch(int *fp,int Length)

{

int i;

int data;

printf("开始使用顺序查询.\n请输入你想要查找的数据.\n");

scanf("%d",&data);

for(i=0; i

if(fp[i]==data)

{

printf("经过%d次查找,查找到数据%d,表中位置为%d.\n",i+1,data,i);

return ;

}

printf("经过%d次查找,未能查找到数据%d.\n",i,data);

}

/*二分查找*/

void Search(int *fp,int Length)

{

int data;

int bottom,top,middle;

int i=0;

printf("开始使用二分查询.\n请输入你想要查找的数据.\n");

scanf("%d",&data);

printf("由于二分查找法要求数据是有序的,现在开始为数组排序.\n");

Sort(fp,Length);

printf("数组现在已经是从小到大排列,下面将开始查找.\n");

bottom=0;

top=Length;

while (bottom<=top)

{

middle=(bottom+top)/2;

i++;

if(fp[middle]

{

bottom=middle+1;

}

else if(fp[middle]>data)

{

top=middle-1;

}

else

{

printf("经过%d次查找,查找到数据%d,在排序后的表中的位置为%d.\n",i,data,middle);

return;

}

}

printf("经过%d次查找,未能查找到数据%d.\n",i,data);

}

/*

下面测试了

*/

void Sort(int *fp,int Length)

{

int temp;

int i,j,k;

printf("现在开始为数组排序,排列结果将是从小到大.\n");

for(i=0; i

for(j=0; j

if(fp[j]>fp[j+1])

{

temp=fp[j];

fp[j]=fp[j+1];

fp[j+1]=temp;

}

printf("排序完成!\n下面输出排序后的数组:\n");

for(k=0; k

{

printf("%5d",fp[k]);

}

printf("\n");

}

/*构造随机输出函数类*/

void input(int a[])

{

int i;

srand( (unsigned int)time(NULL) );

for (i = 0; i < 10; i++)

{

a[i] = rand() % 100;

}

printf("\n");

}

/*构造键盘输入函数类*/

/*void input(int *p)

{

int i;

printf("请输入 %d 个数据 :\n",MAX);

for (i=0; i

{

scanf("%d",p++);

}

printf("\n");

}*/

/*构造输出函数类*/

void output(int *p)

{

int i;

for ( i=0; i

{

printf("%d ",*p++);

}

}

void main()

{

int start=0,end=3;

int *p, i, a[MAX];

int count=MAX;

int arr[MAX];

int choise=0;

/*printf("请输入你的数据的个数:\n");

scanf("%d",&count);*/

/* printf("请输入%d个数据\n",count);

for(i=0;i

{

scanf("%d",&arr[i]);

}*/

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

do

{

printf("1.使用顺序查询.\n2.使用二分查找法查找.\n3.退出\n");

scanf("%d",&choise);

if(choise==1)

SequenceSearch(a,count);

else if(choise==2)

Search(a,count);

else if(choise==3)

break;

}

while (choise==1||choise==2||choise==3);

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试选择排序*/

p = a;

printf("选择排序之后的数据:\n");

select_sort(p,MAX);

output(a);

printf("\n");

system("pause");

/**/

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试直接插入排序*/

printf("直接插入排序之后的数据:\n");

p = a;

insert_sort(p,MAX);

output(a);

printf("\n");

system("pause");

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试冒泡排序*/

printf("冒泡排序之后的数据:\n");

p = a;

insert_sort(p,MAX);

output(a);

printf("\n");

system("pause");

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试快速排序*/

printf("快速排序之后的数据:\n");

p = a;

quick_sort(p,0,MAX-1);

output(a);

printf("\n");

system("pause");

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试堆排序*/

printf("堆排序之后的数据:\n");

p = a;

heap_sort(p,MAX);

output(a);

printf("\n");

system("pause");

/*录入测试数据*/

input(a);

printf("随机初始数组为：\n");

output(a);

printf("\n");

/*测试归并排序*/

printf("归并排序之后的数据:\n");

p = a;

MergeSort(a,start,end);

output(a);

printf("\n");

system("pause");

}

C 语言 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。