三种基础排序算法（冒泡排序、选择排序、插入排序）

矫情吗；* 2023-02-12 05:54 205阅读 0赞

### 1、冒泡排序： ###

冒泡排序是一种简单的排序算法。  
从前往后，依次比较2个相邻的数，把较大数放到后面，然后再与下一位数两两比较，将较大的数放到后面。直至到达数组的末端，第一次循环结束。此时，数组的最后一位就是最大的值。  
第二次循环：从头到尾，继续两两相比，将较大的数放置在靠后的位置，到数组的倒数第二位结束，此时，数组当中的倒数第二位的值就是第二大的。  
。。。。。  
动图演示如下：  
![动图演示][20200524222452415.gif]

#### 代码： ####

import java.util.Random;
    public class Test {
        
        public static void main(String[] args) {
        
            //生成一个不重复的随机数组
            int aa[] = new int[100];
            Random rand = new Random();
            for (int i = 0; i <aa.length; ) {
        
                aa[i]= rand.nextInt(100)+1;
                for (int j = 0; j <i ; ) {
        
                    if(aa[j]==aa[i]){
        
                        aa[i]=rand.nextInt(100)+1;
                        j=0;
                    }else {
        
                        j++;
                    }
                }
                i++;//如果不重复就继续生成下一个随机数
            }
            //第一轮：
            //从第一个数开始比较2个相邻的数，把大的挪向靠后的位置，
            //再继续比较，将较大的挪到处于靠后的位置，循环到最后一位数时，这个数组的末端就是最大的值
            //第二轮：从第一个数开始，比较两个相邻的数，将较大的数挪到靠后的位置
            for (int i = 0,t; i <aa.length ; i++) {
        
                for (int j = 0; j <aa.length-1-i; j++) {
        
                    if(aa[j]>aa[j+1]){
        
                        t=aa[j];
                        aa[j]=aa[j+1];
                        aa[j+1]=t;
                    }
                }
            }
            for (int i : aa) {
        
                System.out.print(i+"\t");
            }
        }
    }

### 2、选择排序 ###

以从小到大排序为例，本人习惯于将较小的数放置于数组的开头。  
第一次：以第一个元素为基准，从第二个元素开始往后找，找到最小的元素，与第一个元素交换。  
第二次：以第二个元素为基准（此时第一个元素已经是数组中最小的元素了），从第三个元素开始往后找，找到最小的元素，与第二个元素交换。  
第三次：以第三个元素为基准（此时第一、二两个元素已经是有序状态了），从第四个元素开始往后找，找到最小的元素，与第三个元素交换。  
。。。。  
动图演示如下![在这里插入图片描述][20200524223746520.gif]

#### 代码： ####

import java.util.Random;
    public class 选择排序 {
        
        public static void main(String[] args) {
        
            //生成一个不重复的随机数组
            int aa[] = new int[100];
            Random rand = new Random();
            for (int i = 0; i <aa.length; ) {
        
                aa[i]= rand.nextInt(100)+1;
                for (int j = 0; j <i ; ) {
        
                    if(aa[j]==aa[i]){
        
                        aa[i]=rand.nextInt(100)+1;
                        j=0;
                    }else {
        
                        j++;
                    }
                }
                i++;
            }
            System.out.println("排序之前：");
            for (int i : aa) {
        
                System.out.print(i+"\t");
            }
            //选择法，选择最小的值与第一个值交换位置
            for (int i = 0,j=0,minLx,minval; i <aa.length ; i++) {
        
                //假设最小值的下标为minLx，将后面的数与之一一比较
                minLx=i;
                minval = aa[i];//minval存储假定的最小值
                for (j = i+1; j <aa.length; j++) {
        
                    if (aa[j]<minval){
        
                        minLx = j;
                        minval = aa[j]; //发现比假定值小的，将该值存进假定最小值minval中
                    }
                }
                //循环结束之后，minval的值就是最小，minlx的值就是最小值的下标
                //进行值交换
                aa[minLx] = aa[i];
                aa[i] = minval;
            }
            System.out.println("\n 排序后：");
            for (int i : aa) {
        
                System.out.print(i+"\t");
            }
        }
    }

### 3、插入排序： ###

从数组的开头两两（A和B）相比，将较小的（假定为B）元素，插入到A元素之前的相应位置。  
![在这里插入图片描述][20200524225348516.gif]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NTY2Njcz_size_16_color_FFFFFF_t_70]

#### 代码： ####

public class 插入法排序_重写 {
        
        public static void main(String[] args) {
        
            //创建随机数组
            int[] aa = new int[100];
            Random rand = new Random();
    
            for (int i = 0; i < aa.length; i++) {
        
                aa[i] = rand.nextInt(100) + 1;
                for (int j = 0; j < i; ) {
        
                    if (aa[j] == aa[i]) {
        
                        aa[i] = rand.nextInt(100) + 1;
                        j=0;
                        continue;
                    } else{
        
                        j++;
                    }
                }
            }
            System.out.println("排序之前");
            for (int i : aa) {
        
                System.out.print(i+"\t");
            }
            //插入排序
            for (int i = 1,t,j; i <aa.length ; i++) {
        
                if(aa[i]>aa[i-1]){
        
                    continue;
                }
                //两两相邻的数对比，如果后面的数较小
                //就将较小的数保存下来，将前面比他大的数依次往后挪
                t =aa[i];
                for (j = i-1; j >=0&&(t<=aa[j]) ; j--) {
        //
                    aa[j+1]=aa[j];
                }
                aa[j+1]=t;
            }
            System.out.println("\n排序后：");
            for (int i : aa) {
        
                System.out.print(i+"\t");
            }
        }
    }

注：图片来源：https://www.cnblogs.com/onepixel/articles/7674659.html

[20200524222452415.gif]: https://img-blog.csdnimg.cn/20200524222452415.gif
[20200524223746520.gif]: https://img-blog.csdnimg.cn/20200524223746520.gif
[20200524225348516.gif]: https://img-blog.csdnimg.cn/20200524225348516.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NTY2Njcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200524230342330.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NTY2Njcz,size_16,color_FFFFFF,t_70