继续快速排序,简单选择排序和堆排序
一,快速排序
b,分区过程,将比这个数大的放在右边,小于等于这个数的放到左边
c,再对左右区间重复第二步,直到各个区间只剩一个数
2,代码
void QuickSort(int[]s,int l,int r){//l,r是指快排的范围,从s[l]到s[r]
int i=l;
int j=r;
int temp;
if(l<r){
temp=s[l];
while(i!=j){
while(j>i&&s[j]>temp){//从右向左找小于temp的数
j--;
}
if(i<j){
s[i]=s[j];
i++;
}
while(i<j&&s[i]<temp){//从左向右找大于temp的数
i++;
}
if(i<j){
s[j]=s[i];
j--;
}
}
s[i]=temp;
QuickSort(s, l, i-1);
QuickSort(s, i+1, r);
}
}
二,简单选择排序
1,算法思想
选择类排序的主要动作是“选择”,简单选择排序采用最简单的选择方式,从头至尾顺序扫描排列,找出最小的一个记录,和第一个记录交换,
接着从剩下的记录中继续这种选择和交换,最终使序列有序。
void SelectSort(int r[],int n){
int i,j,k;
int temp;
for(i=1;i<=n;i++){
k=i;
//算法关键处,从无需序列中挑出一个最小的元素
for(j=i+1;j<=n;j++){
if(r[k]>r[j]){
k=j;
}
temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}
}
三,堆排序
warning:学堆排序之前,应该了解堆的相关知识;)
算法思想还是上杰宝吧...
代码如下咯:
/*调整为最小堆*/
void Sift(int R[],int low,int high){
int i=low,j=2*i;//R[j]是R[i]的左孩子节点
int temp=R[i];
while(j<=high){
if(j<high&&R[j]<R[j+1]){
j++;
}
if(temp<R[j]){
R[i]=R[j];
i=j;
j=2*i;
}else{
break;
}
}
R[i]=temp;
}
/*堆排序函数*/
void heapSort(int R[],int n){
int i;
int temp;
for(i=n/2;i>=1;--i){
Sift(R,i,n);
for(i=n;i>=2;--i){
/*以下3句换出了根节点中元素将其放入最终位置*/
temp=R[1];
R[1]=R[i];
R[i]=temp;
Sift(R,1,i-1);//在减少了一个无需序列中进行调整
}
}
}
分享到:
相关推荐
详细讲述了8中常见算法的原理及思想,并用JAVA进行了实现,代码中有详细的注释,解释了算法的实现逻辑和一些小技巧。
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
文档格式是chm文档,方便查看,点击即可快速浏览排序算法,里面的程序可以直接拿来用,实现语言是标准的C程序。
简单的数据结构算法和排序,可以让大家简单的认识下数据结构和算法!
数据结构中几种常见的排序算法之比较,比较常见的冒泡排序、快速排序等
对各种排序算法的一个总结,分析了几种常用算法的思想和实现过程。
用C语言写的常见排序算法,包括直接选择排序、折半插入排序、起泡排序、快速排序、简单选择排序、归并排序等,已通过VC 6.0 测试。绝对实用。
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在排序过程中需要...
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
使用随机数产生器产生大数据集合,运行上述各种排序算法,使用系统时钟测量各个算法所需的实际时间,并分析程序的运行结果。(常见内排序算法实际排序所需时间测试及比较)
程序内含多种常见数据结构的排序算法,并且附带详细的说明注释
本文实例讲述了JS中的算法与数据结构之常见排序(Sort)算法。分享给大家供大家参考,具体如下: 排序算法(Sort) 引言 我们平时对计算机中存储的数据执行的两种最常见的操作就是排序和查找,对于计算机的排序和...
几种常见的排序算法的实现与性能分析数据结构课程设计报告.doc
数据结构教材8种常见排序算法用c++代码编码实现,而且测试过啦,都能够正确运行
数据结构常见问题:12单元16 经典排序算法.doc
排序是程序设汁中常见的任务,在数据结构课程中介绍了很多种排序方法,有插入排序、交换排序、选择排序、归并排序、基数排序等。每种排序的效率、稳定性和算法的复杂程度都有所区别。在实际应用中,插入排序和现则...
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
简单的数据结构,主要有链表、栈、队列以及常见的排序算法