`
亚当爱上java
  • 浏览: 696140 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java基础-插入,冒泡,选择,快速排序,二分查找

 
阅读更多
一. 直接插入排序
void insertSort(int[] a){
for(int i=1;i<a.length; i++){
if (a[i]<a[i-1]){
temp = a[i]; //1
a[i] = a[i-1]; //2

// 继续和前面的进行比较
for(int j=i-2; j>=0; j--){
if(temp < a[j])
a[j+1] =a[j];//3
}
a[j+1] = temp;//4
}
}
}

算法(简要描述):
1. temp保存被比较的数值
2. 前一位数值移动到被比较的数值的位置
3. 前面的继续往后移动
4. 把被比较的数值放到适当的位置
直接插入排序



二.冒泡排序

冒泡排序,就是从最底那个开始往上比较,遇到比它小的就交换,相当于过五关看六将,不断地向前冲。接着循环第二个...
+-----+ void bubbleSort(int[] a){
| a[6] | //每个都进行冒泡(一个一个来)
+-----+ for (int i=0; i<a.length; i++){
| a[5] |
+-----+ //和后面的每个都进行比较(过五关看六将)
| a[4] | for (int j=i; j<a.length-1; j++){
+-----+ if (a[j]>a[j+1]){
| a[3] | temp = a[j];
+-----+ a[j] = a[j+1];
| a[2] | a[j+1] = temp;
+-----+ }
| a[1] | }
+-----+ }
| a[0] | }
+-----+


三.选择排序
选择排序,就是选择最小的,然后置换,循环再找到最小的,再置换...

void selectSort(int[] a){
for (int i=0; i<a.length; i++){
small = i;

//找出最小的
for (int j=i+1; j<a.lenth; j++){
if (a[small]>a[j]){
small = j;
}
}

//置换位置
if (i != small){
temp = a[small];
a[small] = a[i];
a]i] = temp;
}
}
}

四.快速排序
快速排序的基本过程:
得到枢轴索引:compare首先从high位置向前搜索找到第一个小于compare值的索引,并置换(这时high索引位置上的值为compare值);然后从low位置往后搜索找到第一个大于compare值的索引,并与high索引上的值置换(这时low索引位置上的值为compare值);重复这两步直到low=high为止。
得到枢轴索引后,则递归进行枢轴两边的队列的排序....
void quickSort(int[] a, int low, int high) {
p = get(a, low, high);
quickSort(a, low, p-1);
quickSort(a, p+1, high);
}

int get(int[] a, int low, int high){
compare = a[low];

while(low < high){ //无论如何置换, 被置换的都包含compare的值
while(low<high && a[high]>=compare)
high--;

//在 low<high 的情况下找到a[high]<compare并置换
temp = a[low];
a[low] = a[high];
a[high] = temp;

while(low<high && a[low]<=compare)
low++;

//在 low<high 的情况下找到a[low]>compare并置换
temp = a[low];
a[low] = a[high];
a[high] = temp;
}
return low; //while(low==hight)停止循环, 并返回枢轴位置
}


五.二分查找
二分查找原理很容易懂,想象为二叉查找树就明白了。

int binarySearch(int[] a, int value){
int low = 0;
int high = a.length-1;

while(low <= high){
mid = (low+high)/2; //**
if (a[mid] == value)
return mid;
else if (a[mid] > value)
high = mid-1;
else
low = mid +1;
}
return -1;
}

** mid = (low + high) / 2; 有问题,当low + high大于int范围时就会溢出的。Sun的jdk里面的二分查找源码原先也有同样的问题。
解决的方法是mid = low/2 + high/2。这样用2先除一下,就不会溢出了。

分享到:
评论

相关推荐

    Java排序算法和查找算法

    该工具包含有Java一些比较常见的排序算法和...排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、

    H马Java面试专题课

    │ 06-二分查找_选择题目1.mp4 │ 10-冒泡排序_初步实现.mp4 │ 13-冒泡排序_优化_进一步优化比较次数.mp4 │ 17-选择排序_实现.mp4 │ 18-选择排序_vs_冒泡排序.mp4 │ 19-插入排序_演示.mp4 │ 22-希尔排序...

    数据结构与算法复习(Java):排序、字符串、数组、链表、二分查找、二叉树.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    北语15春《计算机科学导论》作业3.doc

    快速排序 -----------------选择: 4. 程序调用自身的编程技巧称为()。 A. 继承 B. 复用 C. 递归 D. 循环 -----------------选择: 5. 大量的计算机通过网络被连结在一起,可以获得极高的运算能力及广泛的数据共享 ...

    Java程序设计-常见算法

    查找算法:基本、二分、插值、分块 排序算法:冒泡排序、选择排序、插入排序、快速排序

    TheAlgorithms:基于Java 8的算法实现

    :thinking_face: 算法 基于Java 8实现的代码片段集合,可以在之上的同步理解这些算法代码片段。博客地址: :fox:排序算法-排序 与排序相关的数据结构:优先权...二分查找-BinarySearch 广度优先搜索 深度优先搜索

    【超全!】图解Java数据结构和算法(共195集)【资料+视频+课件+代码+笔记】

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...

    java数据结构与算法第二版

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...

    Java数据结构和算法中文第二版

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...

    Java数据结构和算法(第二版)

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...

    基础算法与数据结构 -- Java 实现.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    用Java实现基础数据结构,排序算法、经典算法以及leetcode刷题记录.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    Java数据结构与算法-笔记-代码-课件-资料

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...

    java8源码-interview:面试

    java8 源码 Table of Contents ...二分查找 o(nlog(n)) 分块查找 B树和B+树查找 hash表查找 o(1) 排序 插入排序 直接插入排序 折半插入排序 希尔排序 交互排序 冒泡排序 快速排序 选择排序 简单选择排序

    Java基础,数据结构与算法.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    java基础,数据结构及算法.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    Java数据结构和算法中文第二版(1)

    递归的二分查找 汉诺(Hanoi)塔问题 归并排序 清除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树...

    #数据结构与算法java实现 #包括排序,线性表,树,图,散列等基础数据结构.zip

    算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...

    architect-java:java后端架构师技术图谱

    并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...

Global site tag (gtag.js) - Google Analytics