Java——(排序算法)冒泡、选择、插入、快排、归并、希尔、基数
程序员文章站
2022-06-04 15:01:19
...
一、冒泡算法
概述:冒泡排序:数组两两比较,进行位置交换,经过一轮排序后,最大的元素,放置在最后面。
public class MyTest {
public static void main(String[] args) {
int[] arr = {24, 69, 80, 57, 13};
//将一段代码抽取到方法中,ctrl+alt+M
// tuiDao(arr);
for (int j = 0; j <arr.length-1; j++) {
for (int i = 0; i < arr.length - 1-j; i++) {
if (arr[i] > arr[i + 1]) {
//值交换:采用中间变量的方式
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
}
System.out.println(Arrays.toString(arr));
}
private static void tuiDao(int[] arr) {
//第一轮排序
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
//值交换:采用中间变量的方式
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
//第二轮
for (int i = 0; i < arr.length - 1-1; i++) {
if (arr[i] > arr[i + 1]) {
//值交换:采用中间变量的方式
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
//第三轮
for (int i = 0; i < arr.length - 1 - 1-1; i++) {
if (arr[i] > arr[i + 1]) {
//值交换:采用中间变量的方式
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
//第四轮
for (int i = 0; i < arr.length - 1 - 1 - 1-1; i++) {
if (arr[i] > arr[i + 1]) {
//值交换:采用中间变量的方式
int t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
}
}
}
}
二、选择排序
概述:选择排序:从0索引处开始,拿着这个元素,跟后面的元素挨个比较,小的往前放,经过一轮比较后,最小元素,就会放在最前面。
public class MyTest2 {
public static void main(String[] args) {
int[] arr = {24, 69, 80, 57, 13,1,20,10,30};
//tuiDao(arr);
for (int index = 0; index < arr.length-1; index++) {
for (int i = 1 +index; i < arr.length; i++) {
if (arr[index] > arr[i]) {
int t = arr[index];
arr[index] = arr[i];
arr[i] = t;
}
}
}
System.out.println(Arrays.toString(arr));
}
private static void tuiDao(int[] arr) {
//第一轮比较
int index=0;
for (int i =1; i < arr.length; i++) {
if(arr[index]>arr[i]){
int t=arr[index];
arr[index]=arr[i];
arr[i]=t;
}
}
//第二轮比较
index=1;
for (int i = 1+1; i < arr.length; i++) {
if (arr[index] > arr[i]) {
int t = arr[index];
arr[index] = arr[i];
arr[i] = t;
}
}
//第三轮
index=2;
for (int i = 1 + 1+1; i < arr.length; i++) {
if (arr[index] > arr[i]) {
int t = arr[index];
arr[index] = arr[i];
arr[i] = t;
}
}
//第四轮
index=3;
for (int i = 1 + 1 + 1+1; i < arr.length; i++) {
if (arr[index] > arr[i]) {
int t = arr[index];
arr[index] = arr[i];
arr[i] = t;
}
}
}
}
三、直接插入排序
public class MyTest {
public static void main(String[] args) {
//算法思想
/*直接插入排序, 是一种最简单的排序方法.他的基本操作是将一个记录插入到一个长度为m 的有序表中, 使之仍保持有序, 从而得到一个新的长度为m + 1 的有序列表.假设有一组元素 { k1, k2...,kn },
排序开始就认为k1是一个有序序列, 让k2插入上述表长为1的有序序列, 使之成为一个表长为2的有序序列, 然后让k3插入上述表长为2的有序序列, 使之成为一个表长为3的有序序列, 以此类推, 最后让kn插入表长为n - 1
的有序序列, 得到一个表长为n的有序序列.
例如:
49, 38, 65, 97, 76, 13, 27 原始数据
[49], 38, 65, 97, 76, 13, 27 从1索引开始插入
[38, 49], ,65, 97, 76, 13, 27
[38, 49, 65]97, 76, 13, 27
[38, 49, 65, 97]76, 13, 27
[38, 49, 65, 76, 97]13, 27
[13, 27, 38, 49, 65, 76, 97],27
[13, 27, 38, 49, 65, 76, 97]*/
//代码实现
int[] arr={10,-1,1,1,3,5,6,9,0,100,3,-9,1000};
//外层循环定义轮次
//[10]
for (int i =1; i < arr.length; i++) {
int j=i;
//往之前的有序列表中插入元素,插入完之后,使之仍保持有序
while (j>0&&arr[j]<arr[j-1]){//当前元素arr[i] 跟我前面一个元素去比 arr[i-1]
int t=arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;
j--;
}
}
System.out.println(Arrays.toString(arr));
//插入排序,还有很多优化的变种,比如希尔排序,就是对插入排序的优化排法
}
}
四、快速排序
public class MyTest {
public static void main(String[] args) {
//快速排序
int[] arr = {10, 30, 10, 3, 6, 7, 6, -1, 3, 5, 1000, 200};
QuickSortUtils.quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
//方法:
public class QuickSortUtils {
/**
* @param arr 数组
* @param start 起始位置
* @param end 结束位置
*/
public static void quickSort(int[] arr, int start, int end) {
//找出基准数,对左右两半,重复调用
// 找出基准数,就是我刚才讲的,挖坑填数,用代码实现
if (start < end) {
int index = getIndex(arr, start, end);
//以基准数的索引分为左右两半,对左右两半进行递归
quickSort(arr, start, index - 1);//对左半边,进行递归
quickSort(arr, index + 1, end);//对右半边,进行递归
}
}
//挖坑填数
private static int getIndex(int[] arr, int start, int end) {
//定义三个变量
int i = start;
int j = end;
//定义一个基准数
int x = arr[i];
//将基准数挖出形成第一个坑。
//由后向前找比他小的数,找到后挖出此数填到前一个坑中。
//由前向后找比他大或等于的数,找到后也挖出此数填到前一个坑中。
//再重复执行2,3两步骤。
//再重复执行2,3 两步骤。
while (i < j) {
//2 由后向前找比他小的数,找到后挖出此数填到前一个坑中。
while (i < j && arr[j] > x) {
j--; //比他的大的,继续向前退
}
if (i < j) {
arr[i] = arr[j];
i++; //顺便让i递增一下
}
//3.由前向后找比他大或等于的数,找到后也挖出此数填到前一个坑中。
while (i < j && arr[i] <= x) {
i++; //后面的数,比他小 i继续往后找
}
if (i < j) {
arr[j] = arr[i];
j--; //顺便让j递减一下
}
}
arr[i] = x;
return i;
}
}
五、归并排序
public class ArrayDemo {
public static void main(String[] args) {
//治理:将两个有序子序列,合并成一个有序序列
// int[] arr={1,3,5,7,9,2,4,6,8,10};
//mergeSort(arr,0,4,arr.length-1);
int[] arr = {1, 4,6,0,-1,4,9,20,35,98, 9, 2, 4, 6, 8, 10,-4,1000,800};
chaiFen(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void chaiFen(int[] arr, int startIndext, int endIndex) {
//计算中间索引
int centerIndex=(startIndext+endIndex)/2;
if(startIndext<endIndex){
//递归拆左边
chaiFen(arr, startIndext, centerIndex);
//递归拆右边
chaiFen(arr, centerIndex + 1, endIndex);
mergeSort(arr, startIndext, centerIndex, endIndex);
}
}
/*
* @param arr 要归并排序的数组
* @param startIndtx 起始索引
* @param centerIndex 中间索引
* @param endIndex 结束索引
*/
private static void mergeSort(int[] arr, int startIndtx, int centerIndex, int endIndex) {
//定义一个临时数组
int[] tempArray=new int[endIndex-startIndtx+1];
//定义第一数组的起始索引
int i=startIndtx;
//定义第二个数组的起始索引
int j=centerIndex+1;
//定义临时数组的索引
int index=0;
//两个数组元素,进行对比归并
while (i<=centerIndex&&j<=endIndex){
if(arr[i]<=arr[j]){
//把小的数放到临时数组中
tempArray[index]=arr[i];
i++; //递增一下索引
}else{
tempArray[index] = arr[j];
j++; //递增一下索引
}
index++; //临时数组的索引也要递增
}
//处理剩余元素
while (i<=centerIndex){
tempArray[index]=arr[i];
i++;
index++;
}
while (j<=endIndex){
tempArray[index] = arr[j];
j++;
index++;
}
//经过上面的操作后,临时数组中的元素就排序好了
// System.out.println(Arrays.toString(tempArray));
//把临时数组中的元素放到原数组中
for (int k = 0; k < tempArray.length; k++) {
arr[startIndtx+k]=tempArray[k];
}
}
}
六、希尔排序
public class ShellSortDemo {
public static void main(String[] args) {
//希尔排序,是对插入排序的优化
int[] arr = {9, 4, 5, 6, 1, 0, 3, 2, 10, 20, 11, 24, 32, 13};
//insertSort3(arr);
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void shellSort(int[] arr) {
//定义序列的间隔为4
/* int h=4;
for (int i =h; i < arr.length; i++) {
for (int j = i; j >h-1;j-=h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
h = 2; //缩小间隔为2
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
h = 1; //缩小间隔为3
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
*/
//把上面的代码改进一下
/* for (int h = 4; h > 0; h /= 2) {
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
}
*/
//再来优化,我们这个间隔,可以取数组长度的一半
/* for (int h =arr.length/2; h > 0; h /= 2) {
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
}
*/
//间隔取成数组长度的一半,也不是很好,我们可以使用
//h=1
// h = 3 * h + 1 例如: 1,4,13,40,121,364
//算出第一次的最最大间隔
int jiange = 1;
while (jiange <= arr.length / 3) {
jiange = 3 * jiange + 1;
}
for (int h = jiange; h > 0; h = (h - 1) / 3) {
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
}
}
private static void insertSort3(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swapValue(arr, j, j - 1);
}
}
}
}
private static void insertSort2(int[] arr) {
//直接插入排序,可以看作是间隔为1的希尔排序
int h = 1;
for (int i = h; i < arr.length; i++) {
for (int j = i; j > h - 1; j -= h) {
if (arr[j] < arr[j - h]) {
swapValue(arr, j, j - h);
}
}
}
}
private static void swapValue(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
private static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
swapValue(arr, j, j - 1);
j--;
}
}
}
}
七、基数排序(只能用于非负数排序)
public class ArrayDemo2 {
public static void main(String[] args) {
//基数排序
int[] arr = {21,31,444,23,33,47,1000,900,124,987,0,100,0};
//int max=getMax(arr);
sortArr(arr);
System.out.println(Arrays.toString(arr));
}
private static void sortArr(int[] arr) {
//最大数有几位,我们就排几轮
int max = getMax(arr);
int len = String.valueOf(max).length();
//len=2;
//定义一个二维数组,长度为10
int[][] tempArr = new int[10][arr.length];
//再定义一个数组,长度和二维数组的长度一样,用于记录二维数组中的每一个桶位存了几个数字
int[] counts = new int[10];
for (int i = 0, n = 1; i < len; i++, n *= 10) {
//循环遍历,取每个位上的数字
for (int j = 0; j < arr.length; j++) {
//取每个位上的数字
int ys = arr[j] / n % 10;
//int count=counts[ys];
tempArr[ys][counts[ys]]=arr[j];
counts[ys]++;
// count++;//二维数组中的一维数组放了要一个数,就在统计数组对应的位置统计一下
// counts[ys] = count; //将累加后的值,赋值给统计数组
}
//取出每个桶中的元素,放入原来的数组
int index=0;
for (int k = 0; k < counts.length; k++) {
//取出统计数组在每个位置上统计的个数
if(counts[k]!=0){
for (int h = 0; h < counts[k]; h++) {
arr[index]=tempArr[k][h];
index++;
}
counts[k] = 0; //一趟完成后,把统计的个数清0
}
}
}
//for (int i = 0; i < tempArr.length; i++) {
// System.out.println(Arrays.toString(tempArr[i]));
//}
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
}
上一篇: ROS机器人建模与仿真(二)--机器人URDF模型优化
下一篇: 夏季睡眠不足影响情绪
推荐阅读
-
用Python代码实现插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序
-
Python算法-冒泡排序-选择排序-插入排序-快排-二叉树
-
Java数组排序总结(冒泡,选择,插入,希尔) JavaJ#算法Blog工作
-
Java数组排序总结(冒泡,选择,插入,希尔) JavaJ#算法Blog工作
-
稳定性分析与Java实现:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序
-
排序(插入、希尔、冒泡、快速、选择、堆排、归并、计数及排序性能比较和稳定性)
-
排序算法——选择,插入,冒泡,希尔,快排,归并
-
Java——(排序算法)冒泡、选择、插入、快排、归并、希尔、基数
-
排序算法总结(冒泡、选择、插入、希尔、快速、归并、基数、堆排序)
-
七大排序算法比较【冒泡、选择、插入、希尔、快排、归并,堆】