作为入门级基本算法,徒手写出是基本要求,下面列取几种基本的算法实现。
可以查看对应的动画演示,可以更好的理解排序方法
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;
}
}
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;
}
}
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;
}
}
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;
}
}
希尔排序是插入排序的升级版,如果一个很小的数出现在了最末的位置,那只是插入排序的效率将会大大降低。 希尔排序则是,通过步长,将元素化为同一组,让他们在同组中进行插入排序
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;
}
}
选择排序和冒泡排序的遍历有点像,但不同出现在选择是记录最小的小标,最后开始替换;冒泡则是每次比较后,都可能会进行一次替换,保证当前下标元素永远是最小的。
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]
对上面两个数组进行有序合并很简单
经过上面的步骤,合并排序完成。但是如果是只有一个数组,且数据都还不是有序的呢,那将如何进行排序呢。
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;
}
}
基数排序,主要使用了分类,利用了以空间换时间的思想。
123
,则将放入序号为3
的队列之中0~9
0~9
的顺序从队列取数,放入到数组中1~3
,直到遍历完成最大的一位,会发现数组排序完成堆排序和上面的几种排序都不太一样,它是基于顺序存储的二叉树进行的一种排序,故此新开了一章进行讲解。
排序算法是最基本的算法,上面几个排序的方法,总的来说,用到了遍历、递归、双指针(双下标)这样的方法,也可以算初步找回以前刷算法题的感觉。
上面还有一个排序还有一个堆排序没有列出来,这我要先回顾全二叉堆,再进行更新了。
对应代码,已丢至码云,后续的算法题我也会在此进行更新
我是半月,祝你幸福!