import java.util.Arrays;
public class SortsAndBinarySearch {
public static void main(String[] args) {
//待排序数组
int[] arr = { 4, 9, 23, 1, 45, 27, 5, 2 };
//快速递归排序
QuickSort(arr, 0, arr.length - 1);
//打印排序结果
System.out.println(Arrays.toString(arr));
//二分查找4对应下标,注意二分必须先排序
System.out.println("下标:"+binarySearch(arr,4));
}
public static int binarySearch(int[] data, int aim) {
// 以int数组为例,aim为需要查找的数
int start = 0;
int end = data.length - 1;
int mid = (start + end) / 2;
while (data[mid] != aim && end > start) {// 如果data[mid]等于aim则死循环,所以排除
if (data[mid] > aim) {
end = mid - 1;
} else if (data[mid] < aim) {
start = mid + 1;
}
mid = (start + end) / 2;
}
return (data[mid] != aim) ? -1 : mid;
}
public static void QuickSort(int[] data, int low, int high) {
// 枢纽元,一般以第一个元素为基准进行划分
int i = low;
int j = high;
if (low < high) {
// 从数组两端交替地向中间扫描
int pivotKey = data[low];
// 进行扫描的指针i,j;i从左边开始,j从右边开始
while (i < j) {
while (i < j && data[j]>pivotKey) { j--; }
// 比枢纽元素小的移动到左边
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i]<pivotKey) { i++; }
// 比枢纽元素大的移动到右边
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = pivotKey;// 枢纽元素移动到正确位置
QuickSort(data, low, i - 1); // 前半个子表递归排序
QuickSort(data, i + 1, high);// 后半个子表递归排序
}
}
}
分享到:
相关推荐
二分查找(非递归) <*******\n"); printf("\t***********> 3.二分查找(递归) <*******\n"); printf("\t***********> 4,直接插入排序 <*******\n"); printf("\t***********> 5.直接选择排序 <*******\n"); ...
课程设计教程包含了10个数据结构相关的实例,涵盖了二叉树的建立和遍历、冒泡排序、快速排序等内容。以下是每个实例的简介: ...10. 查找.c:介绍了常见的查找算法,包括顺序查找、二分查找和哈希查找
一、实验目的 1、掌握查找的不同方法,并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。...1、有序顺序表的二分查找的递归算法
二分查找 哈希查找 直接插入排序 折半插入排序 希尔(shell)排序 冒泡排序 快速排序 简单选择排序 堆排序 归并排序(非递归算法) 基数排序 实现图的存储结构 图的深度遍历 图的广度遍历 二叉排序树的...
1 一列数的规则如下: 1、1、2、3、5、8、13、21、34.........3 实现二分法查找,int a[8] = {3,12,24,36,55,68,75,88},查找24需要几次查找出来。 4 实现冒泡排序, int[] array = { 23,45,16,7,42 };。
二分查找则是先对数据进行排序,然后利用 三个标志,分别指向最大,中间和最小数据,接下来根据待查找数据和中间数据的比较 不断移动标志,直至找到。二叉排序树则是先构造,构造部分花费最多的精力,比根节 点数据...
01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15链表 16链表的迭代器 17循环链表 18...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...
②在最好情况下,二叉排序树在生成的过程中,树的形态比较匀称,最终得到的是一棵形态与二分查找的判定树相似的二叉排序树,此时它的平均查找长度大约是lgn。 ③插入、删除和查找算法的时间复杂度均为O(lgn)。 ...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...
20_二分查找 21_冒泡排序和选择排序 22_插入排序 23_希尔排序 24_归并排序 25_快速排序 26_Hash散列&ADT Map 27_树的嵌套列表实现 28_树结构的节点链接法实现 29_表达式解析树 30_树的遍历 31_python实现ADT ...
二分查找非递归Python语言实现,在图解算法中,作者给出了二分查找的实现的非递归Python2语言实现的程序
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...
树的删除.swfB树的生成.swf查找中序线索二叉树后继.swf串的顺序存单链表结点的插入.swf单链表结点的删除.swf堆排序.swf二叉排序树的删除.swf二叉排序树的生成.swf二叉树的建立.swf二分查找.swf分块查找.swf构造...
( A ) 9、二分查找法要求待查表的关键字的值必须有序。( A ) 10、哈希法是一种将关键字转换为存储地址的存储方法。( A ) 11、在二叉排序树中,根结点的值都小于孩子结点的值。 ( B ) 12、对有序表而言,采用二分...
2.二分查找法 对于有序数列,才能使用二分查找法 .使用递归的方式实现二分查找 .使用循环的方式实现二分查找 二、数据结构 1.线性结构 数组;栈;队列;链表;哈希表。。。 链表: 优点:真正的动态, 不需要处理...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
二分查找 BacktoBackSWE 播放列表 龟兔兔指针 树木 压扁树 树高 迭代遍历 最低共同祖先 层序遍历 二叉树的直径 递归遍历 对角线遍历 垂直遍历 序列化和反序列化树 其他 BackToBackSWE 的 图表 BFS 问题 图着色/...
8.3.2 快速排序 216 8.4 选择排序 219 8.4.1 简单选择排序 219 8.4.2 堆排序 221 8.5 归并排序 226 8.6 基数排序 228 8.6.1 多关键字的排序 228 8.6.2 链式基数排序 228 8.7 小结 232 习题 233
[单选题] 1. 于二叉树的遍历,以下选项中描述错误的是 A、二叉树的... 关于排序技术的描述,以下选项中错误的是 A、选择排序法在最坏的情况下需要比较n(n-1)/2次 B、快速排序法比冒泡排序法的速度快 C、冒泡排序法是