java实现七种经典排序算法

article/2025/10/24 18:41:38

简单算法：冒泡，简单选择，直接插入

改进算法：希尔，堆，归并，快速

直接插入排序：将一个记录插入到已经拍好的有序列表中，从而得到一个新的、记录数增加1的有序表。

冒泡排序：两两比较，反序交换。每趟将最大（小 ）的浮到最上面或沉到最底下。

简单选择排序：通过关键字之间的比较，每次将剩余的记录中选择最小的与指定位置交换。

希尔排序：跳跃的插入排序，选择某个增量，对间隔增量的子序列进行排序，随着增量递减，逐步完成所有值的排序。

堆排序：将待排序序列构建成一个大顶堆，此时整个序列最大值就是根节点。将它和末尾元素交换，随后将剩余的n-1个元素重新构造成一个堆，以此类推。

归并排序：拆分，随后重组。

快速排序：通过一趟排序将待排记录分成独立的两部分，一部分都小于另一部分，随后对两部分分别进行再次排序，以达到整体有序。

（所有代码均可独立运行成功）

冒泡排序：

import java.util.Arrays;/*** 冒泡排序算法* 两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止* @author 诸葛浪**/
public class BubbleSortDemo {public static void bubbleSort0(int[] arr) {//初级版本冒泡算法 每一个关键字都和后面每一个关键字相比较for(int i =0;i<arr.length-1;i++) for(int j =i+1; j<arr.length;j++)if(arr[i] > arr[j])swap(arr, i, j);}public static void bubbleSort(int[] arr) {//从后往前 两两比较 每一轮把最小的转移到i的位置for(int i=0;i<arr.length;i++)for(int j = arr.length-1;j>i;j--)//for(int j=0 ; j<arr.length-1-i ; j++) 从前往后也可以 每一趟把最大的放最后	if(arr[j-1] > arr[j])swap(arr, j-1, j);}public static void bubbleSort2(int[] arr) {//改进版 如果一趟下来没有交换 说明有序 之后就不必循环判断了boolean flag = true;//用以记录是否发生交换for(int i = 0;i<arr.length&&flag;i++) {flag = false;for(int j = arr.length - 1;j>i;j--) {if(arr[j-1] > arr[j]) {		swap(arr, j-1, j);flag = true;}}}}public static void main(String[] args) {int[] arrTest = {9,1,5,8,3,7,4,6,2};System.out.println("before: " +	Arrays.toString(arrTest));bubbleSort2(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}public static void swap(int[] arr , int i, int j) {//交换数组两元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

 

直接插入排序：

import java.util.Arrays;/*** 插入排序算法* 基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个记录数+1的有序表* @author 诸葛浪**/
public class InsertSortDemo {public static void insertSort(int[] arr) {//设置一个辅助空间arr[0]for(int i =2;i<arr.length;i++	) {if(arr[i] < arr[i-1]) {		//需要将arr[i]插入有序子表arr[0] = arr[i];//设置哨兵int j;for(j = i-1;arr[j] > arr[0];j--)arr[j+1] = arr[j];//记录后移arr[j+1] = arr[0];//插入到正确位置}}}public static void main(String[] args) {int[] arrTest = {0,1,5,8,3,7,4,6,2};System.out.println("before: " +	Arrays.toString(arrTest));insertSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}}

简单选择排序

import java.util.Arrays;/*** 简单选择排序* 基本思想是每一趟在n-i个记录中选择最小的作为第i个记录（从0开始）* * @author 诸葛浪**/
public class SelectSortDemo {public static void selectSort(int[] arr) {//选择排序 每一趟找到最小的放到i的位置for(int i=0;i<arr.length;i++) {int min = i;//将当前下标定义为最小值下标for(int j = i+1; j<arr.length;j++)	{if(arr[min] > arr[j]	)//如果有小于当前最小值的关键字min = j;	  //将此下标赋值给min}if(i != min)//有更改 则交换swap(arr, i, min);}}public static void main(String[] args) {int[] arrTest = {9,1,5,8,3,7,4,6,2};System.out.println("before: " +	Arrays.toString(arrTest));selectSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}public static void swap(int[] arr , int i, int j) {//交换数组两元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

希尔排序：

import java.util.Arrays;/*** 希尔排序 又叫增量递减排序* 将相距某个”增量“的记录组成一个子序列* 保证在子序列内分别进行直接插入排序后得到的结果是基本有序的* 直接插入排序的升级版* @author 诸葛浪**/
public class ShellSortDemo {public static void shellSort(int[] arr) {//增量递减的插入排序int increment = arr.length;do {increment = increment / 3 + 1;for(int i = increment + 1 ; i < arr.length; i++) {if(arr[i] < arr[i - increment]) {//对间隔增量的位置进行比较arr[0] = arr[i];//暂存在0int j;for(j = i - increment; j> 0 && arr[0] < arr[j]; j -= increment)arr[j+increment] = arr[j];//记录后移 查找插入位置arr[j+increment] = arr[0];			}}}while(increment > 1);}public static void main(String[] args) {int[] arrTest = {0,1,5,8,3,7,4,6,2};System.out.println("before: " +	Arrays.toString(arrTest));shellSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}
}

 

堆排序：


import java.util.Arrays;/*** 堆排序 利用完全二叉树的结构* 对于完全二叉树来说，层序遍历之后如果i>1 则i/2(向上取整3.5->3)为其双亲节点* 而双亲节点均大于或小于子节点* 根节点最大称大顶堆 否则小顶堆* 通过不断移除根节点（与末尾结点交换）并重新组织成堆* 从而得到有序序列* 简单选择排序的升级版* @author 诸葛浪**/
public class HeapSortDemo {public static void heapSort(int[] arr) {for(int i = (arr.length-1)/2; i>0;i--) heapAdjust(arr, i, arr.length-1);for(int i = (arr.length-1);i>1;i--) {swap(arr, 1, i);heapAdjust(arr, 1, i-1);}}public static void heapAdjust(int[] arr, int s, int m) {//将s到m调整为大顶堆int temp = arr[s];for(int j = s*2;j<=m;j*=2) {//左孩子节点2*s 右孩子2*s+1if(j < m && arr[j] < arr[j+1])//左孩子小于右孩子 j指向右孩子++j;if(temp >= arr[j])//根节点大于右孩子 满足大顶堆特性 跳出循环break;arr[s] = arr[j];//否则将大节点赋值给根节点s = j;//根节点向下指向孩子节点}arr[s]  = temp;}public static void swap(int[] arr , int first, int next) {//交换数组两元素int temp = arr[first];arr[first] = arr[next];arr[next] = temp;}public static void main(String[] args) {int[] arrTest = {0,50,10,90,30,70,40,80,60,20};System.out.println("before: " +	Arrays.toString(arrTest));heapSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}
}

归并排序：

import java.util.Arrays;/*** 归并排序算法* 假设初始序列含有n个记录 则可以看成是n个有序的子序列 每个子序列长度为1* 然后两两归并 得到n/2（向上取整）个长度为2或1的有序子序列 两两归并 如此重复 * 直到得到长度为n的有序序列为止 称为2路归并* 一种拆分到最小 并从最小合并成最大的思路* 拆分之后的归并实际上是选择排序的一种* @author 诸葛浪**/
public class MergeSortDemo {public static void mergeSort(int[] arr ) {mSort(arr, arr, 0, arr.length-1);}public static void mSort(int[] SR,int[] TR1,int s, int t ) {int m;int[] TR2 = new int[SR.length + 1];if(s == t)//递归返回条件 拆分至最小了TR1[s] = SR[s];else {m = (s+t)/2; //将SR[s..t]分成s到m和m+1到tmSort(SR, TR2, s, m); //递归地将SR[s...m]归并为有序的TR2[s..m]mSort(SR, TR2, m+1, t); //同上merge(TR2,TR1,s,m,t);//TR2归并到TR1中}}public static void merge(int[] SR,int[] TR,int i, int m ,int n ) {//将有序的SR[i..m]和SR[m+1...n]归并为有序的TR[i...n]int j,k,l;for(j = m+1,k=i;i<=m&&j<=n;k++) {//两半里面挨个挑 将SR中记录由小到大并入TRif(SR[i] < SR[j])//比较符号反过来就是从大到小的排序TR[k] = SR[i++];elseTR[k] = SR[j++];}//剩下哪个全都归入TR数组if(i <= m)for(l = 0;l<=m-i;l++)TR[k+l] = SR[i+l];if(j <= n)for(l = 0;l<=n-j;l++)TR[k+l] = SR[j+l];}public static void main(String[] args) {int[] arrTest = {50,10,90,30,70,40,80,60,20};System.out.println("before: " +	Arrays.toString(arrTest));mergeSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}
}

快速排序：


import java.util.Arrays;/*** 快速排序算法* 属于交换排序 * 基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小* 则可以分别对这两个部分继续进行排序 以达到整个序列有序的目的* * @author 诸葛浪**/
public class QuickSortDemo {public static void quickSort(int[] arr) {qSort(arr, 0, arr.length-1);}/*对arr中的子序列arr[low...high]做快速排序*/public static void qSort(int[] arr, int low,int high) {int pivot;//枢轴变量if(low < high) {//将arr[]一分为二 算出枢轴值pivot//pivot = partition(arr, low ,high);pivot = partition1(arr, low, high);qSort(arr, low, pivot-1);//对低子表进行递归排序qSort(arr, pivot+1, high);//对高子表进行递归排序}}/*交换arr中字表的记录 使枢轴记录到位 并返回其所在位置，此时在它之前均不大于他 之后均不小于他*/public static int partition(int[] arr, int low, int high) {int pivotKey = arr[low];//用子表的第一个记录作为枢轴值while(low < high) {//low和high双指针不断向中间靠拢，枢轴值也在不断移动 性能依赖枢轴值在序列中的分布//另一个版本中也可以不移动枢轴值 最后赋值皆可while(low < high && arr[high] >= pivotKey)high--;swap(arr, low, high);while(low < high && arr[low] <= pivotKey)low++;swap(arr, low, high);}return low;}public static int partition1(int[] arr, int low, int high) {int pivotKey ;//用子表三数取中法 作为枢轴值int m = low +(high - low) /2;//找到序列中间位置if(arr[low] > arr[high])swap(arr, low, high);if(arr[m] > arr[high])swap(arr, high, m);if(arr[m] > arr[low])swap(arr, m, low);pivotKey = arr[low];//此时枢轴值选择为左中右三个数中位数值while(low < high) {//可以不移动枢轴值 最后赋值皆可while(low < high && arr[high] >= pivotKey)high--;arr[low] = arr[high]; //改为直接赋值while(low < high && arr[low] <= pivotKey)low++;arr[high] = arr[low];}arr[low] = pivotKey;return low;}public static void swap(int[] arr , int i, int j) {//交换数组两元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arrTest = {50,10,90,30,70,40,80,60,20};System.out.println("before: " +	Arrays.toString(arrTest));quickSort(arrTest);System.out.println("after: " + Arrays.toString(arrTest));}}

快排和归并的示意图：

 

再加一个啊哈磊的图


http://chatgpt.dhexx.cn/article/HbTH0E7l.shtml

相关文章

java实现10种排序算法

java实现10种排序算法

1.冒泡排序(Bubble Sort) import java.util.Arrays; //冒泡排序 public class BubbleSort_01 {public static void main(String[] args) {int a[]{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};//记录比较次数int count0;//i0,第一轮比较for (int i 0; i < a.length-1; i) {…
阅读更多...
SQL sever数据库触发器设计

SQL sever数据库触发器设计

SQL sever数据库触发器设计 一、目的: 能够理解触发器调用的机制。能够使用SQL命令创建DML触发器。能够完成触发器的修改、删除等管理任务。 二、触发器: 定义&#xff1a;触发器&#xff08; T rigger &#xff09;是 SQL server 提供给程序员和数据分析员来保证数据完整性…
阅读更多...
MySQL——超详细数据库触发器教程

MySQL——超详细数据库触发器教程

目录 一、触发器的概念 二、创建触发器 三、查看触发器 四、删除触发器 总结 一、触发器的概念 在实际开发中往往会碰到这样的情况&#xff1a; 当我们对一个表进行数据操作时&#xff0c;需要同步对其它的表执行相应的操作&#xff0c;正常情况下&#xff0c;如果我们使用…
阅读更多...
关于数据库触发器（trigger）的简单使用操作

关于数据库触发器（trigger）的简单使用操作

最近在做一些东西&#xff0c;用到关于数据库触发器的简单使用。比如当我们在做用户模块的表设计的时候&#xff0c;我们建了联用户信息表&#xff08;t_user&#xff09;和账号表&#xff08;t_account&#xff09;&#xff0c;账号表&#xff08;t_account&#xff09;用来进…
阅读更多...
MySQL数据库触发器

MySQL数据库触发器

MySQL 数据库中触发器是一个特殊的存储过程&#xff0c;不同的是执行存储过程要使用 CALL 语句来调用&#xff0c;而触发器的 执行不需要使用 CALL 语句来调用&#xff0c;也不需要手工启动&#xff0c;只要一个预定义的事件发生就会被 MySQL自动调用 引发触发器执行的事件一般…
阅读更多...
mysql数据库触发器失效,mysql 的数据库触发器解决方法

mysql数据库触发器失效,mysql 的数据库触发器解决方法

mysql 的数据库触发器 我要做一个数据库触发器&#xff0c;当删除数据库中的某一张表的时候触发这个一个事件&#xff0c;删除其他表中的某一些数据。 大家给个例子 ------解决方案-------------------- MYSQL官方免费手册中已经有现成的例子了。 CREATE TABLE test1(a1 INT); …
阅读更多...
什么是数据库触发器？

什么是数据库触发器？

目录 什么是数据库触发器&#xff1f; 事件 AFTER触发器 INSTEAD OF触发器 特殊数据库对象 定义 用于触发器 复杂的审计 执行业务规则 派生列值 触发器很棘手&#xff01; 什么是数据库触发器&#xff1f; 数据库触发器是在数据库中发生特定操作时运行的特殊存储过…
阅读更多...
Oracle数据库 触发器

Oracle数据库 触发器

文章目录 一、触发器的定义二、触发器的分类三、触发器的功能四、触发器的语法五、触发器的使用案例案例1&#xff1a;向emp1表中插入一条数据后输出 欢迎加入 语句案例2&#xff1a;数据校验&#xff0c;在周四这一天不允许向emp1表中插入/更新数据案例3&#xff1a;创建触发器…
阅读更多...
数据库之触发器详解

数据库之触发器详解

一、触发器的概念 触发器是与表有关的数据库对象&#xff0c;在满足定义条件时触发&#xff0c;并执行触发器中定义的语句集合。触发器的这种特性可以协助应用在数据库端确保数据的完整性。 举个例子&#xff0c;比如你现在有两个表【用户表】和【日志表】&#xff0c;当一个…
阅读更多...
数据库-触发器

数据库-触发器

目录 1. 触发器概述 2. 触发器的创建 2.1 创建触发器语法 3. 查看、删除触发器 3.2 删除触发器 4. 触发器的优缺点 4.2 缺点 4.3 注意点 在实际开发中&#xff0c;我们经常会遇到这样的情况&#xff1a;有 2 个或者多个相互关联的表&#xff0c;如 商品信息 和 库存信…
阅读更多...
触发器（数据库必学）

触发器（数据库必学）

文章目录 概念注意 优缺点优点缺点 语法参数说明 查看触发器删除触发器实例实际应用注意重新编辑拓展不能对同一张表进行修改 概念 触发器是一种特殊类型的存储过程&#xff0c;它不同于存储过程&#xff0c;主要是通过事件触发而被执行的。而存储过程则需要主动调用其名字执行…
阅读更多...
C语言实现字符串逆序、倒置字符串（字符串逆序问题的升级）

C语言实现字符串逆序、倒置字符串（字符串逆序问题的升级）

一.字符串逆序 问题描述&#xff1a; 输入一个字符串str&#xff0c;将其内容颠倒过来&#xff0c;并输出。 数据范围0<len(str)<10000 输入描述&#xff1a; 输入一个字符串&#xff0c;可以有空格 输出描述&#xff1a; 输出逆序的字符串 输入样例&#xff1a; …
阅读更多...
指针实现字符串逆序

指针实现字符串逆序

代码如下&#xff1a; #include<stdio.h> #include<string.h> void reverse(char* str) { //指针变量分别指向第一个和最后一个元素&#xff0c;借助中间变量temp进行交换。char* left str;char* right str strlen(str) - 1;while (left < right){char temp…
阅读更多...
c语言字符串逆序输出reverse,将一个字符串逆序输出

c语言字符串逆序输出reverse,将一个字符串逆序输出

C语言：输入一个字符串，然后逆序输出 输入一个字符串，然后逆序输出，要CSS布局HTML小编今天和大家分享主函数调用fun函数，fun的功能是逆可以将整数当做字符串(字符串长度不超过10)接收，然后反向输出字符数组元素即可。 字符串实际长度可以用strlen函数来计算。 方法程序如下…
阅读更多...
字符串逆序输出

字符串逆序输出

字符串逆置 方法1:下标法&#xff0c;定义一个i下标从头开始&#xff0c;使用strlen函数求出字符串长度(不包括\0),定义一个j下标等于字符串长度减一&#xff0c;i&#xff0c;j下标字符进行交换&#xff0c;只需要遍历字符串长度一半即可 方法2:额外创建一个数组&#xff0c…
阅读更多...
递归实现字符串逆序

递归实现字符串逆序

编写一个函数 reverse_string(char * string)&#xff08;递归实现&#xff09;&#xff0c;将参数字符串中的字符反向排列&#xff0c;不是逆序打印。 &#xff08;要求&#xff1a;不能使用C函数库中的字符串操作函数。&#xff09; &#xff08;在本次练习中&#xff0c;由于…
阅读更多...
C字符串逆序、C++字符串逆序

C字符串逆序、C++字符串逆序

1.C字符串逆序&#xff1a; void CReverse(char* ch) {int nLen strlen(ch) - 1;char szStr;for (int i 0; i < nLen - i; i){szStr ch[i];ch[i] ch[nLen - i];ch[nLen - i] szStr;}ch[nLen 1] 0; } 2.C字符串逆序&#xff08;利用栈的先进后出的原理&#xff09; …
阅读更多...
字符串逆序 - 多种方法实现

字符串逆序 - 多种方法实现

字符串逆序实现方法 1. 借助额外数组2. 循环实现2.1 图解2.2 思路2.3 代码实现 3. 递归实现14. 递归实现24.1 思路 对字符串进行逆序&#xff0c;以字符串abcdef为例 1. 借助额外数组 #include <stdio.h> #include <string.h>int main() {char str[] "abcd…
阅读更多...
字符串逆序的几种写法

字符串逆序的几种写法

字符串逆序的几种写法 提示&#xff1a;将字符串逆序与将其逆序打印出来是两码事&#xff0c;逆序是将内容倒着改变了&#xff0c;逆序打印虽然打印结果也是倒着的&#xff0c;不过储存字符串的数组内容并没有改变。 一、非递归写法 1. 将一个给定的字符串abcdef逆序 #incl…
阅读更多...
字符串逆序（递归实现）

字符串逆序（递归实现）

目录 一、代码实现&#xff1a; 二、代码逐步实现过程&#xff1a; 1、不用递归用循环方式实现&#xff1a; 1、使用库函数&#xff1a; 2、不使用库函数&#xff1a; &#xff08;1&#xff09;使用参数是数组的形式&#xff1a; &#xff08;2&#xff09;使用参数是指…
阅读更多...
推荐文章

Copyright @ 2022~2023