经典排序算法
2023-06-13 09:15:28 时间
经典排序算法
一、介绍
作为入门级基本算法,徒手写出是基本要求,下面列取几种基本的算法实现。
可以查看对应的动画演示,可以更好的理解排序方法
二、实现
2.1)冒泡排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 冒泡算法
*/
public class Demo01 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(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]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
}
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素会是最大的数
- 针对所有的元素重复以上的步骤,除了最后一个
- 重复步骤1~3,直到排序完成
2.2)快速排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 快速排序
*/
public class Demo02 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr, 0 , arr.length-1);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
private static int[] sort(int[] arr, int start, int end) {
// 在递归过程中,会传入只有一个元素的数组,也就是start和end相等,将不做排序处理
if(start<end){
// 定义比较的标准数
int standard = arr[start];
// 定义低位和高位的下标
int low = start;
int high = end;
// 循环让对应下标的值和标准数对比,进行迁移
while (low<high){
// 先判断高位下标的数
while (low<high && standard<=arr[high])
high--;
// 将高位的值赋值给低位
arr[low] = arr[high];
// 再判断低位下标的数
while (low<high && arr[low]<=standard)
low++;
arr[high] = arr[low];
}
arr[low] = standard;
// 将分割左边的数组,递归进行处理
sort(arr, start, low);
// 将分割右边的数组,递归进行处理
sort(arr, low+1, end);
}
return arr;
}
}
- 定义一个标准数,作为比较
- 将比这个标准数小的放在左边,比标准数大的放在右边
- 左边放一个下标会向后移动一位,右边放一个下标会向前移动一位,直到左右两边下标重合
- 会根据重合的下标,重新划分高位低位,进行递归,将重复1-3
2.3)插入排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 插入排序
*/
public class Demo03 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(int[] arr){
// 从第二个元素开始向后遍历
for (int i = 1; i < arr.length; i++) {
// 当前元素和前一个元素进行对比,如果当前元素小的话
if(arr[i]<arr[i-1]){
// 则记录当前元素进行记录
int temp = arr[i];
int j;
// 对当前元素下标前的元素进行遍历,如果前一个元素比当前元素大,则将前一个元素向后移动位置
for (j = i-1; j>=0 && temp<arr[j]; j--) {
arr[j+1] = arr[j];
}
// 直到结束后,将移动的下标,赋值当前元素
arr[j+1] = temp;
}
}
return arr;
}
}
- 从第二个数开始向后遍历
- 每一个数都将向前遍历,根据自己的大小找到自己的位置
2.4)希尔排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 希尔排序
*/
public class Demo04 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(int[] arr){
// 定义步长
int step = arr.length/2;
// 遍历步长,直到为1后执行最后一次
while (step>0){
// 从步长开始,遍历数组后的元素
for (int i = step; i < arr.length; i++) {
// 遍历同组内的元素,通过步长,从后向前遍历
for (int j = i-step; j >= 0; j-=step) {
if(arr[j]>arr[j+step]){
int temp = arr[j];
arr[j] = arr[j+step];
arr[j+step] = temp;
}
}
}
// 对步长进行二分缩短
step /= 2;
}
return arr;
}
}
希尔排序是插入排序的升级版,如果一个很小的数出现在了最末的位置,那只是插入排序的效率将会大大降低。 希尔排序则是,通过步长,将元素化为同一组,让他们在同组中进行插入排序
- 定义步长,初始步长为n/2,最后一次步长则为1
- 同插入排序一样,选择第二个元素,向前遍历找到他自己的位置。希尔排序这边同理,从步长位置开始,往前遍历步长个位置,找到他自己元素的位置
- 直到步长为1,进行最后一次插入逻辑后,完成排序
2.5)选择排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 选择排序
*/
public class Demo05 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
int tempIndex = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[tempIndex]>arr[j])
tempIndex = j;
}
int temp = arr[i];
arr[i] = arr[tempIndex];
arr[tempIndex] = temp;
}
return arr;
}
}
- 从第0个开始向后遍历,每次初始默认自己是最小的,并记录下标
- 每一个元素,都会向后遍历,选择看看有没有比自己还要小的。如果有,覆盖下标
- 当步骤2走完,当前下标元素和最小下标元素进行替换
- 重复步骤1-3,玩成排序
选择排序和冒泡排序的遍历有点像,但不同出现在选择是记录最小的小标,最后开始替换;冒泡则是每次比较后,都可能会进行一次替换,保证当前下标元素永远是最小的。
2.6)归并排序
package com.banmoon.algorithm.order;
import java.util.Arrays;
import java.util.Random;
/**
* 归并排序
*/
public class Demo06 {
public static void main(String[] args) {
int length = 10;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++)
arr[i] = random.nextInt(length);
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr, 0, arr.length-1);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(int[] arr, int start, int end){
if(start<end){
// 找到中间的下标
int mid = (start +end)/2;
// 开始至中间,为一个数组,进行递归
sort(arr, start, mid);
// 中间至结束,为一个数组,进行递归
sort(arr, mid+1, end);
// 归并两个左右两个数组
marge(arr, start, mid, end);
}
return arr;
}
/**
* 归并排序
* @param arr
* @param start 开始元素的下标
* @param mid 中间,左开右闭,
* @param end 结束元素的下标
*/
public static void marge(int[] arr, int start, int mid, int end){
// 需要创建一个新的数组容器
int[] tempArr = new int[end-start+1];
// 定义下标
int i = start;
int j = mid+1;
// 定义容器的下标
int index = 0;
while (i<=mid && j<=end){
if(arr[i]<=arr[j]){
tempArr[index] = arr[i];
i++;
}else {
tempArr[index] = arr[j];
j++;
}
index++;
}
// 查看还有哪部分没有遍历完
while (i<=mid){
tempArr[index] = arr[i];
i++;
index++;
}
while (j<=end){
tempArr[index] = arr[j];
j++;
index++;
}
// 还要将排序好的临时容器中的数,放回到原数组中
for (int k = 0; k < tempArr.length; k++) {
arr[start+k] = tempArr[k];
}
}
}
归并排序的思想来自于,两个已经有序的数组进行有序合并。 如
[1, 3, 5, 7, 9]
和[2, 4, 6, 8]
,将合并成[1, 2, 3, 4, 5, 6, 7, 8, 9]
对上面两个数组进行有序合并很简单
- 记录两个下标,左右两边的元素两两进行比较,谁小就谁先进入新数组;同时下标向后移动
- 直到一方下标移动完成,将另一方剩下的全部丢进新数组
经过上面的步骤,合并排序完成。但是如果是只有一个数组,且数据都还不是有序的呢,那将如何进行排序呢。
- 传入一个数组,只需要定义左下标,中间下标,右下标,就可以确定出两个数组了
- 左下标到中间下标的元素算作左数组
- 中间下标+1到右下标的元素算作右数组
- 当一个无序的数组,定义两边数组相关参数,向下递归。将它的左右数组缩小,最小为左右数组都只有一个元素时,进行上面步骤1-2有序合并
- 每一次递归,都可以看做将两个有序数组进行有序合并,而这次新合并出来的有序数组,将会作为上级调用者的左右有序数组
2.7)基数排序
package com.banmoon.algorithm.order;
import com.sun.jmx.remote.internal.ArrayQueue;
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
/**
* 基数排序
*/
public class Demo07 {
public static void main(String[] args) {
// int[] arr = {128, 359, 26, 78, 98, 5, 789, 12, 6, 2};
int[] arr = {2, 9, 7, 8, 3, 5, 4, 1, 6, 0};
System.out.println("排序前的数组:" + Arrays.toString(arr));
int[] sortArr = sort(arr);
System.out.println("排序后的数组:" + Arrays.toString(sortArr));
}
public static int[] sort(int[] arr){
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if(max<arr[i])
max = arr[i];
}
int maxLength = String.valueOf(max).length();
Map<Integer, LinkedList> containerMap = IntStream.range(0, 10).boxed()
.collect(Collectors.toMap(Function.identity(), a -> new LinkedList()));
for (int i = 0, n=1; i < maxLength; i++, n*=10) {
for (int j = 0; j < arr.length; j++) {
int temp = arr[j]/n%10;
containerMap.get(temp).add(arr[j]);
}
final int[] index = {0};
IntStream.range(0, 10).boxed().forEach(key -> {
LinkedList list = containerMap.get(key);
for (int k = 0; k < list.size(); k++) {
arr[index[0]] = (int) list.get(k);
index[0]++;
}
containerMap.put(key, new LinkedList());
});
}
return arr;
}
}
基数排序,主要使用了分类,利用了以空间换时间的思想。
- 数组中的元素将,遍历他们的10^{n}位,如个位、十位、百位……这将取决于数组中最大的那个数
- 每次都将对数组中的元素进行判断,判断当前位上是哪个数字,再放进对应的队列中
- 如果当前为个位遍历,判断
123
,则将放入序号为3
的队列之中 - 这样的队列一共有10个,分别为标记为
0~9
- 如果当前为个位遍历,判断
- 当数组中的元素都判断完成,依次从
0~9
的顺序从队列取数,放入到数组中 - 重复上面步骤
1~3
,直到遍历完成最大的一位,会发现数组排序完成
2.8)堆排序
堆排序和上面的几种排序都不太一样,它是基于顺序存储的二叉树进行的一种排序,故此新开了一章进行讲解。
三、最后想说的话
排序算法是最基本的算法,上面几个排序的方法,总的来说,用到了遍历、递归、双指针(双下标)这样的方法,也可以算初步找回以前刷算法题的感觉。
上面还有一个排序还有一个堆排序没有列出来,这我要先回顾全二叉堆,再进行更新了。
对应代码,已丢至码云,后续的算法题我也会在此进行更新
我是半月,祝你幸福!
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 深度学习经典算法 | 模拟退火算法详解
- 机器学习十大经典算法之决策树
- 机器学习十大经典算法之随机森林
- 像经典计算机一样「开箱即用」,百度走出中国量子计算产业化的重要一步
- 【经典书】数字图像处理算法介绍, 第三版
- [AI安全论文] 21.S&P21 Survivalism经典离地攻击(Living-Off-The-Land)恶意软件系统分析
- SLAM算法总结——经典SLAM算法框架总结
- java输出结果保留两位小数,经典好文
- 《面试季》经典面试题-数据库篇(一)
- 十大经典排序算法详解(三)-堆排序,计数排序,桶排序,基数排序[通俗易懂]
- 十大经典排序算法-快速排序算法详解
- fastRcNN算法路面病害检测_R语言经典算法
- C语言 排序算法_C语言中三大经典的排序算法
- 80. 三维重建15-立体匹配11,经典算法Fast Bilateral Solver
- web前端经典react面试题
- 十大经典排序算法的介绍及实现
- 独家 | 三个经典强化学习算法中重大缺陷(及如何修复)
- 经典排序算法:快速排序(Quick Sort)详解编程语言
- Java经典问题算法大全详解编程语言
- 经常面试到的10个经典的C语言小程序详解编程语言
- “抗美援朝志愿军经典武器”系列图解⑨50式冲锋枪
- “抗美援朝志愿军经典武器”㉚“卡秋莎”火箭炮
- 机操作系统Linux:变革计算机操作经典(linux计算)
- 语句Oracle精选经典SQL语句集锦(oracle经典sql)
- 式Oracle不等式:新概念与旧经典(oracle不等)
- SQL Server经典:让数据库变得更加完美(sqlserver经典)
- 超级经典一套鼠标控制左右滚动图片带自动翻滚
- 详解mysql的limit经典用法及优化实例