发布于2021-06-12 14:23 阅读(647) 评论(0) 点赞(6) 收藏(0)
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。就像煮开水中的气泡一样,不停的往上冒。
原理:
静图:
动图:
实现:
package 排序算法.冒泡排序;
/**
* @author shu
* @date 2021/6/7
* @description
*/
public class Bubble {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
/**
* 分析:需要排序的数据[4,5,6,3,2,1]
* 拿数组的最后一个元素,以此与前面的数据进行比较,
* 如果a[j]>a[j+1],表示前面的元素比后面的值大,
* 需要交换位置, a[temp]=a[j],a[i]=a[j+1],a[j+1]=a[temp]
* 注意:这里不能直接a[i]=a[j+1],需要一个中间变量,
* 你可以把他理解为男女相亲,需要中间人介绍才能认识
*/
//最外层控制冒泡的数据
for (int i = a.length - 1; i > 0; i--) {
//内层控制需要排序的数据
for (int j = 0; j < i; j++) {
if (greater(a[j], a[j + 1])) {
exch(a, j, j + 1);
}
}
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
时间复杂度分析:
元素比较的次数为: (N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
元素交换的次数为: (N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
总执行次数为: (N2/2-N/2)+(N2/2-N/2)=N^2-N
选择排序是一种更加简单直观的排序方法,对元素进行依次比较,在交换位置。
原理:
静图:
动图:
实现:
package 排序算法.选择排序;
/**
* @author shu
* @date 2021/6/9
* @description 选择排序算法
*/
public class Selection {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
/**
* [4,6,8,7,9,2,10,1]
* 分析:一:选择排序是初始化一个最小值,与后面的值依次进行比较,如果比初始值小,就交换值
* 二:i <= a.length - 2:如果是最后一个值进行++,没有意义
*/
//外层控制的使可以选择的次数
for (int i = 0; i <= a.length - 2; i++) {
//假定本次遍历,最小值所在的索引是i
int minIndex = i;
//内层控制比较
for (int j = i + 1; j < a.length; j++) {
if (greater(a[minIndex], a[j])) {
//跟换最小值所在的索引
minIndex = j;
}
}
//交换i索引处和minIndex索引处的值
exch(a, i, minIndex);
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
时间复杂度分析:
插入排序(Insertion sort)是一种简单直观且稳定的排序算法。 插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我 们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在 手中的每张牌进行比较。
原理:
静图:
动图:
实现:
package 排序算法.插入排序;
/**
* @author shu
* @date 2021/6/9
* @description 插入排序
*/
public class Insert {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
/**
* 分析:插入排序:将已排序数据和未排序数据分组,
* 已排序的最后一个元素,和未排序的第一个元素进行标记,
* 如果已排序的最后一个元素比未排序的第一个元素大,则交换
*/
//外层控制未排序的数据
for (int i = 1; i < a.length; i++) {
//内层控制倒叙已排序的数据
for (int j = i; j >0 ; j--) {
//如果已排序的最后一个元素比未排序的第一个元素大,则交换
if(greater(a[j-1],a[j])){
exch(a,j-1,j);
}else {
break;
}
}
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
时间复杂度分析:
希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。
原理:
静图:
动图:
实现:
//最大增量确定规则
int h=1
while(h<5){
h=2h+1;//3,7
}
//循环结束后我们就可以确定h的最大值;
h的减小规则为:
h=h/2
package 排序算法.希尔排序;
/**
* @author shu
* @date 2021/6/9
* @description 希尔排序
*/
public class Shell {
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
/**
* 分析: 希尔排序是对插入排序的优化,缩小的比较的次数,提高了效率
*/
//确定增长量h的最大值
int N = a.length;
int h=1;
while(h<N/2){
h=h*2+1;
}
while (h>=1) {
//最外层控制需要比较的数据
for (int i = h; i < N; i++) {
//内存控制排序数据的初始值
for (int j = i; j >=h ; j-=h) {
if (greater(a[j-h],a[j])){
exch(a,j,j-h);
}else{
break;
}
}
}
h/=2;
}
}
/*
比较v元素是否大于w元素
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序 表,称为二路归并。
原理:
静图:
实现:
package 排序算法.归并排序;
/**
* @author shu
* @date 2021/6/9
* @description 归并排序
*/
public class Merge {
/**
* 分析:归并排序是一数组的中位数将数组分组,
* 并且先建一个临时数组,依靠三个数组的索引完成排序
* 最后将临时数组的值赋值给原有的数组
*/
private static Comparable[] assist;//归并所需要的辅助数组
/*
对数组a中的元素进行排序
*/
public static void sort(Comparable[] a) {
//初始化临时数组
assist=new Comparable[a.length];
//定义一个最小索引
int lo=0;
//定义一个最大索引
int hi=a.length-1;
//进行排序
sort(a,lo,hi);
}
/*
对数组a中从lo到hi的元素进行排序
*/
private static void sort(Comparable[] a, int lo, int hi) {
//判断一下,是否索引输入错误
if(hi <= lo){
return;
}
//求中位数
int mid = lo + (hi - lo) / 2;
//进行前一个分组
sort(a, lo, mid);
//进行后一个分组
sort(a,mid+1,hi);
//进行归并
merge(a,lo,mid,hi);
}
/*
对数组中,从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
//定义三个指针
int p1=lo;
int p2=mid+1;
int i=lo;
//遍历
while (p1<=mid && p2<=hi){
if(less(a[p1],a[p2])){
assist[i++]=a[p1++];
}else{
assist[i++]=a[p2++];
}
}
//未遍历完的P1数组
while (p1<=mid){
assist[i++]=a[p1++];
}
//未遍历完的P2数组
while (p2<=hi){
assist[i++]=a[p2++];
}
//将辅助数组的数据放到原数组中
for (int index=lo;index<=hi;index++){
a[index]=assist[index];
}
}
/*
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
}
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一 部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序 过程可以递归进行,以此达到整个数据变成有序序列。
原理:
静图:
实现:
package 排序算法.快速排序;
/**
* @author shu
* @date 2021/6/10
* @description
*/
public class Quick {
public static void sort(Comparable[] a) {
//最小索引
int lo = 0;
//最大索引
int hi = a.length - 1;
sort(a, lo,hi);
}
private static void sort(Comparable[] a, int lo, int hi) {
//安全校验
if(hi<=lo){
return;
}
//中位数
int partition = partition(a, lo, hi);
//递归调用
sort(a,lo,partition-1);
sort(a,partition+1,hi);
}
public static int partition(Comparable[] a, int lo, int hi) {
Comparable key = a[lo];//把最左边的元素当做基准值
int left = lo;//定义一个左侧指针,初始指向最左边的元素
int right = hi + 1;//定义一个右侧指针,初始指向左右侧的元素下一个位置
//进行切分
while (true) {
//先从右往左扫描,找到一个比基准值小的元素
while (less(key, a[--right])) {//循环停止,证明找到了一个比基准值小的元素
if (right == lo) {
break;//已经扫描到最左边了,无需继续扫描
}
}
//再从左往右扫描,找一个比基准值大的元素
while (less(a[++left], key)) {//循环停止,证明找到了一个比基准值大的元素
if (left == hi) {
break;//已经扫描到了最右边了,无需继续扫描
}
}
if (left >= right) {
//扫描完了所有元素,结束循环
break;
} else {
//交换left和right索引处的元素
exch(a, left, right);
}
}
exch(a,lo,right);
return right;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
/*
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
}
原文链接:https://blog.csdn.net/weixin_44451022/article/details/117749652
作者:哦哦好吧
链接:http://www.javaheidong.com/blog/article/222239/b8158b2b35d5dcaf4b41/
来源:java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 java黑洞网 All Rights Reserved 版权所有,并保留所有权利。京ICP备18063182号-2
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!