1.java常用排序方法
1) 选择排序
原理:a. 将数组中的每个元素,与第一个元素比较
如果这个元素小于第一个元素, 就将这个
两个元素交换.
b. 每轮使用a的规则, 可以选择出一个最小元素
放到第一个位置.
c. 经过n-1轮比较完成排序
简单说: 每轮选择最小的放到前面.
原理说明:
ary={8,2,3,7,1}
ary={1|8,3,7,2}
ary={1,2|8,7,3}
ary={1,2,3|8,7}
ary={1,2,3,7|8}
代码分析:
i 代表第一个数据的位置
j 代码后部每一个数据的位置
ary i j ary[i] ary[j] ary[i]>ary[j] [i]<->[j]
{8|2,3,7,1} 0 1 8 2 true 8<->2
{2|8,3,7,1} 0 2 2 3 false
{2|8,3,7,1} 0 3 2 7 false
{2|8,3,7,1} 0 4 2 1 true 2<->1
{1,8|3,7,2} 1 2 8 3 true 8<->3
{1,3|8,7,2} 1 3 3 7 false
{1,3|8,7,2} 1 4 3 2 true 3<->2
{1,2,8|7,3} 2 3 8 7 true 8<->7
{1,2,7|8,3} 2 4 7 3 true 7<->3
{1,2,3,8|7} 3 4 8 7 true 8<->7
{1,2,3,7,8} 4
部分重要代码：
i= 0 ~ < ary.length – 1;
j=i+1 ~ <ary.length
if(ary[i]>ary[j]){
//ary[i]<->ary[j]
int temp = ary[i];
ary[i]=ary[j];
ary[j]=temp;
}
2) 冒泡排序
原理: a. 逐一比较数组中相邻的两个元素, 如果后面
的数字小于前面的数字, 就交换先后元素.
b. 经过一个轮次的比较, 一定有一个最大的排
在最后的位置.
c. 每次比较剩下的元素, 经过n-1次比较, 可以
实现排序
简单说: 比较相邻元素,大的向后交换
原理说明:
ary={8,2,3,7,1}
ary={2,8,3,7,1}
ary={2,3,8,7,1}
ary={2,3,7,8,1}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,1|7,8}
ary={2,3,1|7,8}
ary={2,1|3,7,8}
ary={1,2,3,7,8}
i代表次数
j代表比较位置
ary i j j+1 ary[j] ary[j+1] [j]>[j+1] [j]<->[j+1]
{8,2,3,7,1} 0 0 1 8 2 true 8<->2
{2,8,3,7,1} 0 1 2 8 3 true 8<->3
{2,3,8,7,1} 0 2 3 8 7 true 8<->7
{2,3,7,8,1} 0 3 4 8 1 true 8<->1
{2,3,7,1|8} 1 0 1 2 3 false
{2,3,7,1|8} 1 1 2 3 7 false
{2,3,7,1|8} 1 2 3 7 1 true 7<->1
{2,3,1|7,8} 2 0 1 2 3 false
{2,3,1|7,8} 2 1 2 3 1 true 3<->1
{2,1|3,7,8} 3 0 1 2 1 true 2<->1
{1,2,3,7,8}
部分重要代码：
i = 0~ < ary.length-1
j = 0~ < ary.length – i -1;
if([j]>[j+1]){
[j]<->[j+1]
}
3) 插入排序
原理: a. 将数组分为两部分, 将后部分的第一张逐一
与前部分每一张比较, 如果当前元素小, 就
一点被比较元素.
b. 找到合理位置插入.
原理说明:
temp = 1
{8|2,3,7,1}
{2,8|8,7,1}
{2,3,8|7,1}
{2,3,8|8,1}
{2,3,7,8|8}
{2,3,7,7|8}
{2,3,3,7|8}
{2,2,3,7|8}
{1,2,3,7|8}
temp 代表取出的待插入元素
i 代表后组待插入元素 位置
j 代表前组每个元素的位置
(移动) 插入
ary i t j ary[j] t<[j] [j]->[j+1] t->[j+1]
{8|2,3,7,5} 1 2 0 8 true 8->[j+1]
{8|8,3,7,5} 1 2 -1 2->[j+1]
{2,8|3,7,5} 2 3 1 8 true 8->[j+1]
{2,8|8,7,5} 2 3 0 2 false 3->[j+1]
{2,3,8|7,5} 3 7 2 8 true 8->[j+1]
{2,3,8|8,5} 3 7 1 3 false 7->[j+1]
{2,3,7,8|5} 4 5 3 8 true 8->[j+1]
{2,3,7,8|8} 4 5 2 7 true 7->[j+1]
{2,3,7,7|8} 4 5 1 3 false 5->[j+1]
{2,3,5,7|8} 5
部分重要代码：
i= 1 ~ <ary.length, i++
t = [i];
j= i-1 ~ >=0, j–
if(t<[j]){
[j]->[j+1] //移动
}else{
break j;
}
t->[j+1]//插入
2. java 系统排序 Arrays.sort(), 排序算法性能很好
3. 方法的递归调用
1) java 的栈: 是Java进程启动时候在内存中开辟的存储空间
栈内存的利用方式LIFO(后进先出). Java所有局部变量都在栈中
分配(压入), 方法的参数也是局部变量, 局部变量在离开作用域
时候回收 就是从栈中弹出(删除).
2) Java方法调用使用栈实现, 递归调用就是栈实现的
3) 递归时候要按照递归深度分配全部临时变量, 栈开销很大, 性能
不好, 要注意不要超过栈的大小, 并且一定要给出结束条件, 否则
会造成栈溢出错误.
案例：1+2+3+…+n=f(n)=n+f(n-1) && (n>0, f(1)=1)
注意事项: 解决问题简练，性能很差。一定给出结束条件。
若有不完善的地方请大家多提意见，转发时请注明出处！
