新手初学Java常见排序算法
作者：随性0528 发布时间：2022-05-09 03:35:45
标签：Java,新手,排序算法
1、冒泡排序
排序原理：相邻两个元素比较，如果前者比后者大，则交换两个元素。每执行一次，都会确定一个最大值，其位置就固定了，下一次就不需要再参与排序了。
时间复杂度：O(n^2)
稳定性：稳定
具体实现：
public class Bubble {
/**
* 对数组a中的元素进行排序
*/
public static void sort(Comparable[] a){
//每冒泡一次，参与冒泡排序的元素个数就少一个
//需要排序的次数为数组个数减一
/*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);
}
}
}*/
for (int i=0; i<a.length-1; i++){
for (int j=0; j<a.length-i-1; j++){
if (greater(a[j],a[j+1])){
exch(a, j,j+1);
}
}
}
}
/**
* 比较u元素是否大于v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交换数组下标为i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 测试
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6};
sort(a);
System.out.println(Arrays.toString(a));
}
}
优化：可以加一个标志位，当冒泡一次也没有执行的时候，就说明已经排好了，就不需要再冒泡了。
2、选择排序
排序原理：从数组中找出最小值的下标，然后将最小值交换到前边。每执行一次前边就会有一个最小值位置固定，之后就不再需要参与查找最小值了。
时间复杂度：O(n^2)
稳定性：不稳定
具体实现：
public class Selelction {
/**
* 将数组排序
* @param a 待排序的数组
*/
public static void sort(Comparable[] a){
for (int i=0; i<a.length-1; i++){
//找出最小的值
int minIndex = i;
//注意这里不需要减一
for (int j=i+1; j<a.length; j++){
//Comparable数组 不能直接用下标比较大小
if (greater(a[minIndex],a[j])){
minIndex = j;
}
}
//交换
if (minIndex != i){
exch(a, minIndex, i);
}
}
}
/**
* 比较第一个参数是否大于第二个参数
* @param a
* @param b
* @return 第一个参数是否大于第二个参数
*/
private static boolean greater(Comparable a, Comparable b){
return a.compareTo(b) > 0;
}
/**
* 交换数组的两个元素
* @param a 数组
* @param i 数组下标
* @param j 数组下标
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7};
sort(array);
System.out.println(Arrays.toString(array));
}
3、简单插入排序
排序原理：将数组分成两组，左边一组是已排序的，右边一组是未排序的，然后拿未排序的第一个与左边的从后往前比较，如果比前边的小就交换，直到前边的值比它小或者等于它。
时间复杂度：O(n^2)
稳定性：稳定
具体实现：
public class Insertion {
/**
* 对数组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;
}
}
}
}
/**
* 比较u元素是否大于v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交换数组下标为i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 测试
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
优化思路：将要插入的数先保存起来，然后交换的代码就可以改成覆盖，就相当于后移，等找到合适位置再把之前保存的值放进去。
4、希尔排序
排序原理：是插入排序的优化版，插入排序在比较时只能一个一个比较，而希尔排序中加了一个增长量，可以跨元素比较，相对减少了比较交换的次数。
时间复杂度：O(n^1.3)
稳定性：不稳定
具体实现：
public class Shell {
/**
* 将数组排序
* @param a 待排序的数组
* @return 排好序的数组
*/
public static void sort(Comparable[] a){
//1.确定增长量h的值
int h=1;
while(h < a.length/2){
h = h*2+1;
}
//2.进行排序
while(h>=1){
//找到待排序的第一个值
for (int i=h; i<a.length; i++){
for (int j=i; j>=h; j-=h){
if (greater(a[j-h],a[j])){
exch(a, j, j-h);
}else{
break;
}
}
}
//h减小
h/=2;
}
}
/**
* 比较u元素是否大于v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交换数组下标为i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//测试数据
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7};
sort(a);
System.out.println(Arrays.toString(a));
}
}
5、归并排序
排序原理：使用了递归的思想，先把数组从中间递归分解，接着先排序左边的子数组，然后再排序右边的子数组，最后合并为一个数组。核心方法是merge方法。
时间复杂度：O(nlogn)
稳定性：稳定
具体实现：
public class Merge {
/**
* 辅助数组
*/
private static Comparable[] access;
/**
* 对数组a进行排序
* @param a
*/
public static void sort(Comparable[] a){
//1.初始化辅助数组
access = new Comparable[a.length];
//2.定义两个下标值
int lo = 0;
int hi = a.length -1;
//3.调用分组排序函数
sort(a, lo, hi);
}
/**
* 对数组a中的lo到hi进行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保护
if (hi <= lo){
return;
}
//1.得到mid
int mid = lo + (hi-lo)/2;
//2.对左数组分组排序
sort(a, lo, mid);
//3.对右数组分组排序
sort(a, mid+1, hi);
//4.将两个数组合并
merge(a, lo, mid, hi);
}
/**
* 将两个数组进行排序合并
* @param a
* @param lo
* @param mid
* @param hi
*/
private static void merge(Comparable[] a, int lo, int mid, int hi){
//1.定义三个指针
int i=lo;
int p1=lo;
int p2=mid+1;
//2.分别遍历两个子数组，直到有一个数组遍历完毕
while (p1 <= mid && p2 <= hi){
if (less(a[p1], a[p2])){
access[i++] = a[p1++];
}else{
access[i++] = a[p2++];
}
}
//3。将剩下的一个数组的剩余值放到辅助数组中
while(p1 <= mid){
access[i++] = a[p1++];
}
while(p2 <= hi){
access[i++] = a[p2++];
}
//4。将辅助数组中的值覆盖到原数组中
for (int index=lo; index<=hi; index++){
a[index] = access[index];
}
}
/**
* 比较第一个下标的值是不是小于第二个下标的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) <= 0;
}
/**
* 测试
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
6、快速排序
排序原理：把数组的第一个值设置为中间值，比中间值小的放到左边，比中间值大的放到右边。然后再对左边的做相同的操作，最后是对右边的做相同的操作。核心方法是partition方法，将小的数移到左边，大的数移到右边，最后返回中间值的下标。
时间复杂度：O(nlogn)
稳定性：不稳定
具体实现：
public class Quick {
/**
* 对数组a进行排序
* @param a
*/
public static void sort(Comparable[] a){
int lo = 0;
int hi = a.length-1;
sort(a, lo, hi);
}
/**
* 对数组a中的lo到hi进行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保护
if (hi <= lo){
return;
}
//获取中间值
int mid = partition(a, lo, hi);
//对左子数组进行排序
sort(a, lo, mid-1);
//对右子数组进行排序
sort(a, mid+1, hi);
}
/**
* 将比子数组中第一个值小的数放到其左边，大于的放到右边，最后返回中间值的下标
* @param a
* @param lo
* @param hi
* @return
*/
private static int partition(Comparable[] a, int lo, int hi){
//1.定义两个指针
int p1= lo;
int p2 = hi+1;
while (true){
//2.先移动右指针，找到第一个小于标准值的数
while(less(a[lo],a[--p2])){
if (p2 == lo){
break;
}
}
//3.移动左指针，找到第一个大于标准值的数
while(less(a[++p1],a[lo])){
if (p1 == hi){
break;
}
}
if (p1 >= p2){
//5.退出循环
break;
}else {
//4.交换两个值
exch(a, p1, p2);
}
}
//6.最后把子数组的第一个值和右指针所指的值交换，最后返回其下标
exch(a, lo, p2);
return p2;
}
/**
* 比较第一个下标的值是不是小于第二个下标的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) < 0;
}
/**
* 交换数组中两个下标的值
* @param a
* @param i
* @param j
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 测试
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
来源：https://www.cnblogs.com/lk0528/p/14969735.html
0
投稿猜你喜欢
- 目录Update计时器Invoke协程DoTween最开始接触unity的时候，我做延时都是在update里做计时器。后来才发现，我屮艸芔茻
最新更新的Flyme6整体效果不错，动画效果增加了很多了，看了看flyme6的Viewpager指示器，觉得有点意思，就模仿写了一下，整体效- 在实践中，项目的某些配置信息是需要进行加密处理的，以减少敏感信息泄露的风险。比如，在使用Druid时，就可以基于它提供的公私钥加密方式对数据
- mybatis的大于小于号转义符号言简意赅！如下XML转义字符<<小于号>>大于号<=
- 参考链接亲测试以下版本成功激活附激活教程。idea下载链接(对应版本号下载)：https://www.jetbrains.com/idea/
- 目录定义数据库表访问表中的数据插入数据查询数据创建数据库测试 DaoRoom 是 SQLite 的封装，它使 Android 对数据库的操作
- 本文实例为大家分享了Unity3D Shader实现镜子效果的具体代码，供大家参考，具体内容如下/p>Shader部分代码：Shade
- 啦啦毕业了，毕业前要写毕业设计，需要写一个简单的蓝牙APP进行交互，通过参考网上资料，问题顺利搞定，下面小编把具体实现思路分享给大家，供大家
- .sln：解决方案文件，为解决方案资源管理器提供显示管理文件的图形接口所需的信息。.csproj:项目文件，创建应用程序所需的引用、数据连接
- 1.连接池在实际开发中都会使用连接池因为它可以减少我们获取连接所消耗的时间连接池就是用于存储连接的一个容器，容器其实就是一个集合对象，该集合
- 一、文件上传的原理分析1、文件上传的必要前提a、表单的method必须是postb、表单的enctype属性必须是multipart/for
- 目录业务场景：解决方案：总结业务场景：一个用户数据接口，要求在20ms内返回数据，它的调用逻辑复杂，关联接口多，需要从3个接口汇总数据，这些
- 1、启动新Activty1.1、功能分析App功能在第一个Activity输入消息点击第一个Activity的发送按钮发送消息到第二个Act
- 目录MotionEventViewViewGroup事件拦截寻找目标视图，分发ACTION_DOWN分发除ACTION_DOWN外的其他事件
- 简单几步，实现SpringMVC+servlet3.0文件上传功能：第一步：配置web.xml文件中的servlet，添加multipart
- 经常有同学问到，使用Android能不能开发游戏呢？能开发那些游戏呢？由于操作系统和开发语言局限，一般开发安卓手机游戏，我们很少使用其自带语
- sql语句CDATA标签的用法CDATA 指的是不应由 XML 解析器进行解析的文本数据（Unparsed Character Data）。
- HTTP 头处理HTTP 头是 HTTP 请求和响应中的重要组成部分。在创建 HTTP 请求时需要设置一些 HTTP 头。在得到 HTTP
- 经过几天的折腾，终于到了学习一个重量级的查询方式上，使用@Query注解，使用注解有两种方式，一种是JPQL的SQL语言方式，一种是原生SQ
- 在Android开发中，定时器一般有以下3种实现方法：一、采用Handler与线程的sleep(long)方法二、采用Handler的pos
