java数组三种排序方式

2023-02-18 00:00:00 数组 排序 三种

java数组三种排序方式

      • 一、冒泡排序
      • 二、插入排序:
      • 三、选择排序
      • 三种算法排序的稳定性分析

一、冒泡排序

动图演示:
《java数组三种排序方式》

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

排序思路:
第一步:将倒数第一个和倒数第二个数进行比较,如果小,则互换;
第二步:将倒数第二个和倒数第三个数进行比较,如果小,则互换;

第N步:筛选出最小的一个数,然后从剩下的数中按照上面的方法反复操作,得到需要的序列。

代码实现

import java.util.Arrays;

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        for (int i = 0; i < array.length-1; i++) {  //控制循环次数,比长度少一次。
            for (int j = 0; j < array.length-i-1; j++) {  //后面排好的值不需要进行比较,所以减去i。
                if(array[j]>array[j+1]) { 
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果
《java数组三种排序方式》

二、插入排序:

动图演示:
《java数组三种排序方式》

在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

例:六个数12 15 9 20 6 31 24 用直接插入排序,如下图:
《java数组三种排序方式》
思路:

第一步:从给出的六个数中,随便拿出一个数,比如12,形成一个有序的数据序列(一个数当然是有序的数据序列了,不看12之外的数,就当其他的数不存在);
第二步:从剩下的五个数中挑出一个数来,比如15,和刚才的12作比较,12<15,因此,放在12后面,形成数据序列12 15;
第三步:从剩下的四个数中挑出一个数来,比如9,和刚才的有序数据序列12 15作比较,9 < 12 < 15,因此,放在最前面,形成数据序列9 12 15;

第N步,经过这样一个一个的插入并对比,就形成了上图所示的排序结果。在一个元素插入时,首先要和数据序列中最大的元素作比较,如果遇到相同的,则放在相同元素的后面。

代码实现

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        int temp=0;
        for(int i=1;i<array.length;i++){ 
            int j=i-1;
            temp=array[i];
        for(;j>=0&&temp<array[j];j--){ 
            array[j+1]=array[j];//将大于temp的值整体后移一个单位 
        }
            array[j+1]=temp;
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果
《java数组三种排序方式》

三、选择排序

动图演示:
《java数组三种排序方式》

在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

思路:

第一步:从四个数找到最小的,和初始状态排在第一位的移动互换;
第二步:从剩下三个数中找到最小的,和初始状态排在第二位的移动互换;

第N步:重复上述查找最小和互换的步骤,直到最后一个为止。

代码实现

public class TestDemo { 
    public static void main(String[] args) { 
        int [] array = { 7,14,3,22,1,6,15,60,5};
        for (int i = 0; i < array.length-1; i++) {  //i为要比较的元素。
            for (int j = i+1; j < array.length; j++) {  //i后的每一次元素。
                if(array[i]>array[j]) //两者比较,将较小值放在前面位置。
                { 
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

测试结果
《java数组三种排序方式》

三种算法排序的稳定性分析

  1. 直接插入排序:一般插入排序,比较是从有序序列的最后一个元素开始,如果比它大则直接插入在其后面,否则一直往前比。如果找到一个和插入元素相等的,那么就插入到这个相等元素的后面。插入排序是稳定的。
  2. 选择排序:在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。光说可能有点模糊,来看个小实例:858410,第一遍扫描,第1个元素8会和4交换,那么原序列中2个8的相对前后顺序和原序列不一致了,所以选择排序不稳定。
  3. 冒泡排序:由前面的内容可知,冒泡排序是相邻的两个元素比较,交换也发生在这两个元素之间,如果两个元素相等,不用交换。所以冒泡排序稳定。

部分内容转载自: https://blog.csdn.net/zwqjoy1.

    原文作者:是阿星啊
    原文地址: https://blog.csdn.net/qq_40587263/article/details/115342774
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章