JAVA入门学习 —数组排序的方法

2023-10-12 18:34

短信预约 -IT技能 免费直播动态提醒

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};for (int i = 0; i < a.length-1; i++) {for (int j = 0; j < a.length-1-i; j++) {if (a[j]>a[j+1]) {int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}System.out.println(Arrays.toString(a));}}

2.选择排序(Select Sort)

选择排序的思想：
首先，找到数组中最小(最大)的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小(最大)的元素，拎出来，和数组的第二个元素交换位置，如此循环，知道整个数组排序完成。
在这里插入图片描述

import java.util.Arrays;//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。public class SelectSort_02 {public static void main(String[] args) {        //标记第一个为待比较的数        //然后从后面遍历与第一个数比较        //如果小,就交换最小值        //保存最小元素的下标        //找到最小值后，将最小的值放到第一的位置，进行下一遍循环        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};        for (int i = 0; i < a.length - 1; i++) {            int index = i;            for (int j = i + 1; j < a.length; j++) {                if (a[j] < a[index]) {                    index = j;                }            }            int temp = a[index];            a[index] = a[i];            a[i] = temp;        }        System.out.println(Arrays.toString(a));    }}

3.插入排序(Insert Sort)

插入排序的思想：
       和我们打扑克牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。
       那如果我们不是从牌堆中摸牌，而是左手里面初始化就是一堆乱牌呢？一样的套路，我们把牌往手的右边挪一挪，把手的左边空出一点位置来，然后再乱牌中抽一张出来，插入到左边，再抽一张出来，插入到左边，每次插入都插入到适合的位置时刻保持左手里的牌是有序的，知道右边的牌抽完，则排序完毕。
       在第一轮中，从未排序区域随机拿出一个数字，既然是随机，那我们就获取第一个，然后插入到已排序区域中，此时已排序区域是空，那么就不做比较，默认自身已经是有序的了(在写代码时候，从下标为1的元素开始即可)。
在这里插入图片描述

import java.util.Arrays; //插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。    public static void main(String[] args) {        //长度不减1，是因为要留多一个位置方便插入数        //定义待插入的数        //找到待插入数的前一个数的下标        //拿a[i]与a[i-1]的前面数组比较        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};        for (int i = 0; i < a.length; i++) {            int insertValue = a[i];            int insertIndex = i - 1;            while (insertIndex >= 0 && insertValue < a[insertIndex]) {                a[insertIndex + 1] = a[insertIndex];                insertIndex--;            }            a[insertIndex + 1] = insertValue;        }        System.out.println(Arrays.toString(a));    }}

4.希尔排序(Shell Sort)

希尔排序的思想：
首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序。
增量这里可以有所不同，比如有10个数要进行排序，你设置的增量是4，那么a[0],a[4]与a[8]，a[1],a[6]与a[9]是一组，分组进行插入排序，之后再缩小增量，再进行插入排序。
在这里插入图片描述

import java.util.Arrays;//希尔排序：插入排序的升级public class ShellSort_04 {        //将整个数组分为若干个子数组        //遍历各组的元素        //交换元素        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};        for (int gap = a.length / 2; gap > 0; gap = gap / 2) {            for (int i = gap; i < a.length; i++) {                for (int j = i - gap; j >= 0; j = j - gap) {                    if (a[j] > a[j + gap]) {                        int temp = a[j];                        a[j] = a[j + gap];                        a[j + gap] = temp;                    }                }            }        }        System.out.println(Arrays.toString(a));    }}