Java集中常见的排序

发布于:2023-01-22 ⋅ 阅读:(15) ⋅ 点赞:(0) ⋅ 评论:(0)

排序,就是将一串数组(一个列表)中的元素(整数,数字,字符串等)按某种顺序(增大,减小,字典顺序等)重新排列。

下面介绍几种排序

1.冒泡排序

定义:冒泡排序就是从第一个元素开始,遍历数组,拿相邻的两个元素比较大小,大的排后面,小的移动到前面,通过一轮,得到最后的元素是最大的数.所以,这就需要到双层循环.外层循环控制排序轮数,内层循环用来比较相邻两个元素的大小.

例子1

使用冒泡排序排列班级的5个学生的成绩,下面给出主要的代码

public static void main(String[] args) {
//总循环次数为要数组的长度减 1
    for (int i = 0; i < score.length - 1; i++) {
        for (int j = 0; j < score.length - 1 - i; j++) {
            if (score[j] > score[j + 1]) {
                double temp = score[j + 1];
                score[j + 1] = score[j]; 
                score[j] = temp;
            }
            System.out.print(score[j] + " ");
        }
        for (int j = score.length - 1 - i; j < score.length; j++) {
            System.out.print(score[j] + " ");
        }
        System.out.println();
    }
}

因为一开始,就拿最先前面的两个元素做比较,所以最大循环轮数应该为数组的个数(长度)-1;然后内存循环用来比较相邻两个元素的大小.定义一个临时变量来存放数据,使两个元素之间能进行交换.

同时,冒泡排序的缺点也能看得出来:耗时,每次都需要从头开始比较.为了提高时间效率,下面介绍另一个排序方式.

2.快速排序

思路步骤:

首先需要任意选取一个数据(通常选用第一个数据),作为基准数;

再将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;

再对左右区间重复第二步,直到各区间只有一个数。

下面用图说明:

 第一张图是最先输入的数据,以第一个数据15作为分割点.

步骤二:这个过程,是通过遍历数据,分区,把比15小的数据移到这些比15大的数据的左边,分成两份,遍历完一轮,然后把15移到比15小的数据堆的右边

下面就接着重复步骤二

现在遍历15的左边,到了以11为基准数,遍历4,8,4,都比11小,第二个4和11交换位置.

 再到4做基准数,遍历4,8;8比4大,黄色的4移到中间做分割点.

至此,左边区间只有一个数据,左边快速排序完成;同理,右边数据也一样进行排序.

3.选择排序

很明显,就是遍历数组,找出一个最小/最大的元素,顺序放在已排好序的数列的最后/最前.代码原理是使用外层循环控制循环轮数,内层循环找出最值,然后交换位置

例子2

利用选择排序方法实现对学生的成绩:89,78,69,80,99进行排序,并输出已排序的数组元素。

public static void main(String[] args) {
        int arr[] = {89,78,69,80,99};

        for (int i = 0; i < arr.length - 1; i++) {
            //找到最小值的下标
            int min = i;

            for (int j = i + 1; j < arr.length; j++) {

                if (arr[j] < arr[min]) {
                    //最小值下标赋给遍历到的那个数
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
            
        }
    }
}

 总结:排序在java程序中中不可或缺,这个网站里面含有排序的动态过程,结合动画方便去理解,会明白很多排序(冒泡排序,选择排序,插入排序,归并排序,快速排序,计数排序,基数排序) - VisuAlgo