排序的算法是很多公司的笔试和面试题,个人感觉Java中其实无需使用这些排序方法,因为Java中已经为我们提供了很方便效率很高的sort()方法。但是不使用不能代表不需要学习这些算法,也不是仅仅为了面试和笔试才去学这些算法,这些算法中有很好的数据结构方面的思想,掌握这些算法可以帮助我们更好的理解数据结构。这次既然是回顾和思考,我决定使用很形象的图文展示的方式,透彻的去理解每一个排序算法。
一、选择排序
原理:第n轮比较将数组中除过自己的所有元素与第n个元素比较,如果大于(小于)第一个元素则交换。
有的朋友容易忘记这些排序算法或者说容易混淆这几种排序算法,在这里我建议大家从算法的名字上去记忆,比如说:“选择排序”可以这样去理解,我要从这一堆数组元素中选择出最大、最小(确定的东西,绝对的概念)元素,每次去选择剩下的元素中最大或者最小的元素,依次循环就能排序。
下面我们用Java代码来实现:
public static int[] selectionSort(int[] arry){
/*
* 对照上面的图
* 1、因为最后一个元素就是剩下的,因此不需要去找了,所以总共比较lengh-1轮
* 2、第n轮的第一次比较是数组下标n-1的元素和数组下标为n的元素比较。
* 比如第1轮第一次比较是数组下标为0的元素和数组下标为0+1的元素比较。
*/
for(int i=0; i<arry.length-1; i++){
for(int j=i+1; j<arry.length; j++){
//如果小于本轮第一个元素
if(arry[i] > arry[j]){
//交换两个元素
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}
}
return arry;
}
二、冒泡排序
原理:每一轮都去比较相邻的元素将小(大)的放到前面
下面我们用Java代码实现
/**
* 冒泡排序:请对照上图
* @param arry
* @return
*/
public static int[] bubbleSort(int[] arry){
/*
* 冒泡排序也比较length-1轮
* 与选择排序不同的是每次都从第一个元素开始
*/
for(int i=0; i<arry.length - 1; i++){
for(int j=0; j<arry.length - i - 1; j++){
if(arry[j] > arry[j + 1]){
int temp = arry[j];
arry[j] = arry[j+1];
arry[j+1] = temp;
}
}
}
return arry;
}
三、插入排序
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种。
这里仅研究一下直接插入排序
原理:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止.
用Java实现排序如下:
/**
* 直接插入排序
* @param arry
* @return
*/
public static int[] insertSort1(int[] arry){
/*
* 第一个元素不用排序了,所以从下标为1开始
*/
for(int i=1; i<arry.length;i++){
//和比他下标小的所有元素比较,所以是j<i
for(int j=0; j<i; j++){
if(arry[i] < arry[j]){
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}
}
return arry;
}
我们发现上面的代码还能优化,比如第四个元素和前面三个比较,本应该插入到第二个位置,插入后还要与原来的第二个和第三个元素比较。很快我们就将代码修改如下:
/**
* 直接插入排序
* @param arry
* @return
*/
public static int[] insertSort1(int[] arry){
int i, j, t;
/*
* 第一个元素不用排序了,所以从下标为1开始
*/
for(i=1; i<arry.length;i++){
t = arry[i];
/*
* 我们从后面往前面比较有两张情况
* 1、如果比较的结果是当前数小于前面(已经排序)的最后一个元素
* 说明需要将最后一个元素前移一位,然后将该元素放入到这个位置
* 2、如果比较的结果是当前数大于前面(已经排序)的最后一个元素
* 这样就直接将该元素放入到j位置即可。
*/
for(j=i-1; j>=0; j--){
if(t < arry[j]){
//将arry[j]元素放置到向后1位的位置上
arry[j+1] = arry[j];
}else{
break;
}
}
//因为上面代码执行后会执行一次j--,所以要j+1
arry[j+1] = t;
}
return arry;
}
还有一种和上面的算法相同的简单写法(经典写法),如下:
/**
* 直接插入排序(经典写法)
* @param arry
* @return
*/
public static int[] insertSort2(int[] arry){
int i, j, t;
for(i=1; i<arry.length;i++){
t = arry[i];
for(j=i-1; j>=0 && t<arry[j]; j--){
arry[j+1] = arry[j];
}
arry[j+1] = t;
}
return arry;
}
分享到:
相关推荐
数据结构课程设计五——排序算法综合分析.doc
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100(原始数据不少于100 ,可以用1000,这样方便测试出运行时间),表中数据随机产生,至少用5组不同...
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867026
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867321
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1871731
比KMP更快的字符串匹配算法——BM算法,排序算法数据结构 最快的排序算法
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867491
传统排序合集 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序
Biologically Inspired Methods —— 优化算法.zip(国外大学课件) Biologically Inspired Methods —— 优化算法.zip(国外大学课件) Biologically Inspired Methods —— 优化算法.zip(国外大学课件) Biologically ...
* 冒泡排序: * 每次在无序队列里将相邻两个数一次进行比较, * 将小数调到前面,逐次比较,直至将最大的数移到 * 最后。将剩下的N-1个数继续比较,将次大数移至 * 倒数第二位。
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1868188
毕业设计开题报告——理论算法研究类模板 (1).docx毕业设计开题报告——理论算法研究类模板 (1).docx毕业设计开题报告——理论算法研究类模板 (1).docx毕业设计开题报告——理论算法研究类模板 (1).docx毕业设计开题...
机器人学、机器视觉与控制——MATLAB算法基础.pdf
算法-归并排序(java)(csdn)————程序
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
数据结构——————KMP算法
[统计信号处理基础——实用算法开发(卷III)][罗鹏飞 等][光盘资料].rar
操作系统之LRU算法(java)(csdn)————程序