为了招聘将以前学过的排序算法又复习了一遍,就贴了出来,希望对忙于找工作的同学有点帮助!同时也希望大家有什么好的算法贴出来一起探讨。
#include<stdio.h>
#define N 8
/*
直接插入排序是一种基本的插入排序方法,其基本操作是将第i个记录插入到前面的i-1个已排好序的记录中。
具体的过程为:将第i个记录的关键字Ki顺次与前面记录的关键字Ki-1 ,Ki-2,...,K1比较,将所有关键字大于Ki的
记录一次向后移动一个位置,直到遇见一个关键字小于或等于Ki的记录Kj,此时Kj后面必为空位置,将第i个记录插入
空位置即可。*/
void InsSort(int temp[],int length){
//对记录数组r做直接插入排序,length为数组中待排序的记录的数目
int i=2;
int j;
for(;i<=length;i++){
temp[0]=temp[i];j=i-1;//将待插入记录放到监视哨temp[0]中
while(temp[0]<temp[j]){
temp[j+1]=temp[j];j=j-1;
}
temp[j+1]=temp[0];
}
}
void print(int temp[],int length){
int i=1;
for(;i<=length;i++){
printf("%d ",temp[i]);
}
printf("\n");
}
//折半排序
void BinSort(int r[],int length){
//对记录数组r进行折半插入排序,length为数组长度
int i=2;
int j,low,high,mid,x;
for(;i<=length;i++){
x=r[i];
low=1;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(x<r[mid]) high=mid-1;
else low=mid+1;
}
for(j=i-1;j>=low;--j) r[j+1]=r[j];
r[low]=x;
}
}
/*
希尔排序:当子序列记录间的间隔为d时,共有d个子序列,需要对d个子序列分别进行插入排序。但是算法在具体实现时
并不是先对第一个子序列完成插入排序,再对另一个子序列进行插入排序,而是从第一个子序列的第二个记录开始,顺序扫描
整个待排序记录序列,当前记录属于那个子序列,就在那个子序列中进行插入排序。
*/
void ShellInsert(int r[],int length,int delta){
//对记录数组r做一趟希尔插入排序,length为数组的长度,delta为增量
int i,j;
for(i=1+delta;i<=length;i++){//1+delta为第一个子序列的第二个元素的下标
if(r[i]<r[i-delta]){
r[0]=r[i];//备份r[i]
for(j=i-delta;j>0&&r[0]<r[j];j-=delta){
r[j+delta]=r[j];
}
r[j+delta]=r[0];
}
}
}
void ShellSort(int r[],int length,int delta[],int n){
//对记录数组r作希尔排序,length 为数组r的长度,delta为增量数组,n为delta[]的长度
int i;
for(i=0;i<n;i++){
ShellInsert(r,length,delta[i]);
}
}
//冒泡排序:反复扫描待排序记录序列,在扫描过程中顺次比较相邻的两个元素的大小,
//若逆序就交换位置。每次将最大的元素放置到待排序列的最后。
void BubbleSort(int r[],int length){
int i,j,temp;
int change=1;//判断元素是否有逆序
for(i=1;i<=length-1&&change;++i){
change=0;
for(j=1;j<=length-i;++j){
if(r[j]>r[j+1]){
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
change=1;
}
}
}
}
/*
快速排序:从待排序记录序列中选取一个记录为(通常选取第一个记录)枢纽,其关键字设为k1,然后将其关键字小于K1的
记录移到前面,而将关键字大于K1的记录移到后面,结果将待排序记录分成两个子表,最后将关键字为K1的记录插入到其分界线的位置处
。我们将这个过程称作一次快速排序。通过一次划分后,就以关键字为K1的记录为界,就将待排序列分成两个两个子表。且前面的子表中的所有记录
的关键字均小于K1.而后面子表中所有记录的关键字均不小于K1。对分割后的子表继续按上述原则进行分割,知道所有子表的表长不超过1为止,此时待排序记录
序列就变成了一个有序表。
*/
int QKPass(int r[],int left,int right){
//对记录数组r中的人r[left]至r[right]部分进行一趟快速排序,并得到基准位置,使得排序后的结果满足其之后(前)的记录的关键字却不小于(大于)基准记录
int x=r[left];
int low=left,high=right;
while(low<high){
while(low<high&&r[high]>=x){
high--;//high从右向左找小于x的记录
}
if(low<high){
r[low]=r[high];//找到小于x的记录则进行交换
low++;
}
while(low<high&&r[low]<x)//low从左向右找大于x的记录
low++;
if(low<high){//找到大于x的记录则进行交换
r[high]=r[low];
high--;
}
}
r[low]=x;//将基准记录保存到low=high的位置
print(r,8);
return low;//返回基准记录的位置
}
void QKSort(int r[],int low,int high){
//对记录数组r[low..high]调用快速排序算法进行排序。
int pos=0;
if(low<high){
pos=QKPass(r,low,high);//调用一趟快速排序,以枢轴元素为界划分两个子表
QKSort(r,low,pos-1);//对左部子表调用快速排序
QKSort(r,pos+1,high);//对右部子表调用快速排序
}
}
//选择排序的基本思想:每一趟在n-i+1的记录中选取关键字最小的记录作为有序序列中的第i个记录
//简单选择排序
void SelectSort(int r[],int length){
//对记录数组作简单选择排序,length为数组的长度
int i,j,k,n,x;
n=length;
for(i=1;i<=n-1;i++){
k=i;
for(j=i+1;j<=n;j++){
if(r[j]<r[k]){
k=j;
}
}
if(k!=i){
x=r[i];
r[i]=r[k];
r[k]=x;
}
}
}
//树形选择排序:先把待排序的n个记录的关键字两两进行比较取出较小者。然后再n/2个较小者中,采用同样的方法进行比较选出每两个中的较小者,
//如此反复,直至选出最小关键字为止。
//堆排序
//调整堆
void sift(int r[],int k,int m){
//假设人r[k...m]是以r[k]为根的完全二叉树,且分别以r[2k]和r[2k+1]为根的左,右子树为根为大根堆,调整r[k],使整个序列r[k...m]满足推得性质
int i,j,t,x;
t=r[k];
x=r[k];
i=k;
j=2*i;
while(j<=m){
if(j<m && r[j]<r[j+1]){
j=j+1;//若存在右子树,且右子树根的关键字大,则沿右分支筛选
}
if(x>=r[j]){
break;
}
else{
r[i]=r[j];
i=j;
j=2*i;
}//继续筛选
}
r[i]=t;//r[k]填入到恰当得位置
}
//建初堆.将一个任意序列看成是对应的完全二叉树,由于叶节点可以视为单元素的堆,因而可以反复利用上述调整堆算法(筛选法)
//自低向上把所有子树调整为堆。
void create_heap(int r[],int length){
int n,i;
n=length;
for(i=n/2;i>=1;--i){
sift(r,i,n);
}
}
//堆排序算法实现
void HeapSort(int r[],int length){
int i,n,b;
create_heap(r,length);
n=length;
for(i=n;i>=2;i--){
b=r[1];//将堆顶记录和堆中的最后一个元素和、交换。
r[1]=r[i];
r[i]=b;
sift(r,1,i-1);
}
}
//归并排序:它的基本思想是基于合并,将两个或者两个以上有序表合成一个新的有序表。
//算法思想:假设初始序列含有n个记录,首先江浙n个记录看成n个有序的子序列,每个子序列的长度为1,然后两两合并,得到n/2个长度为2的有序子序列。
//如此重复,直至得到一个长度为n的有序序列为止。
//相邻两个有序子序列的合并算法
void Merge(int r1[],int low,int mid,int high,int r2[]){
//已知r1[low..mid]和r1[mid+1,high]分别按关键字有序排列,将它们合并成一个有序序列,存放在r2[low...high]
int i,j,k;
i=low;j=mid+1;k=low;
while((i<=mid)&&(j<=high)){
if(r1[i]<=r1[j]){
r2[k]=r1[i];i++;
}
else{
r2[k]=r1[j];j++;
}
++k;
}
while(i<=mid){
r2[k]=r1[i];i++;k++;
}
while(j<=high){
r2[k]=r1[j];k++;j++;
}
}
//2-路归并排序的递归算法
void MSort(int r1[],int low,int high,int r3[]){
//r1[low..high]经过排序后放在r3[low...high]中,r2作为辅助空间
int mid;
int r2[N+1];
if(low==high) r3[low]=r1[low];
else{
mid=(low+high)/2;
MSort(r1,low,mid,r2);
MSort(r1,mid+1,high,r2);
Merge(r2,low,mid,high,r3);
}
}
void MergeSort(int r[],int n){
MSort(r,1,n,r);
}
main(){
int temp[]={0,48,62,35,77,55,14,35,98};
MergeSort(temp,8);
print(temp,8);
}
分享到:
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...