一. 直接插入排序
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
}
}
}
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] | }
+-----+
| 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;
}
}
}
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)停止循环, 并返回枢轴位置
}
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;
}
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一些比较常见的排序算法和...排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
│ 06-二分查找_选择题目1.mp4 │ 10-冒泡排序_初步实现.mp4 │ 13-冒泡排序_优化_进一步优化比较次数.mp4 │ 17-选择排序_实现.mp4 │ 18-选择排序_vs_冒泡排序.mp4 │ 19-插入排序_演示.mp4 │ 22-希尔排序...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
快速排序 -----------------选择: 4. 程序调用自身的编程技巧称为()。 A. 继承 B. 复用 C. 递归 D. 循环 -----------------选择: 5. 大量的计算机通过网络被连结在一起,可以获得极高的运算能力及广泛的数据共享 ...
查找算法:基本、二分、插值、分块 排序算法:冒泡排序、选择排序、插入排序、快速排序
:thinking_face: 算法 基于Java 8实现的代码片段集合,可以在之上的同步理解这些算法代码片段。博客地址: :fox:排序算法-排序 与排序相关的数据结构:优先权...二分查找-BinarySearch 广度优先搜索 深度优先搜索
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 消除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
java8 源码 Table of Contents ...二分查找 o(nlog(n)) 分块查找 B树和B+树查找 hash表查找 o(1) 排序 插入排序 直接插入排序 折半插入排序 希尔排序 交互排序 冒泡排序 快速排序 选择排序 简单选择排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
递归的二分查找 汉诺(Hanoi)塔问题 归并排序 清除递归 一些有趣的递归应用 小结 问题 实验 编程作业 第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...