首页 > 代码库 > 算法笔记_008:选择排序和冒泡排序【蛮力法】

算法笔记_008:选择排序和冒泡排序【蛮力法】

目录

1 问题描述

2 解决方案

2.1 选择排序原理简介

2.2 具体编码(选择排序)

2.3 冒泡排序原理简介 

2.4 具体编码(冒泡排序)

 


1 问题描述

给定一个可排序的n元素序列(例如,数字、字符和字符串),将它们按照非降序方式重新排列。

2 解决方案

2.1 选择排序原理简介

选择排序开始的时候,我们从第一个元素开始扫描整个列表,找到它的最小元素,然后和第一个元素交换,将最小元素和第一个元素交换位置;然后,我们从第二个元素开始扫描剩下的n-1个元素,找到这n-1个元素中的最小元素,将最小元素和第二个元素交换位置;然后从第三个元素开始扫描...一般来说,就是从第i个元素开始扫描,找到第n-i+1个元素中的最小元素,将最小元素与第i个元素交换位置。这样,在进行n-1次遍历后,该列表就排好序了。

2.2 具体编码(选择排序)

package com.liuzhen.chapterThree;

public class SelectionSort {
    
    public static void getSelectionSort(int[] a){
        int min = 0;     //用于存放n-i序列中最小元素序号
        int temp = 0;    //交换数组元素值的中间变量
        //打印输出未排序前数组序列
        System.out.print("排序前:          ");
        for(int p = 0;p < a.length;p++)
            System.out.print(a[p]+"\t");
        System.out.println();
        
        for(int i = 0;i < a.length-1;i++){
            min = i;
            for(int j = i+1;j < a.length;j++){
                if(a[j] < a[min])
                    min = j;
            }
            //交换a[i]和a[min]的值
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
            //打印输出每一次选择排序结果
            System.out.print("排序第"+(i+1)+"趟:");
            for(int p = 0;p < a.length;p++)
                System.out.print(a[p]+"\t");
            System.out.println();
        }
    }
    
    public static void main(String args[]){
        int[] a = {89,45,68,90,29,34,17};
        getSelectionSort(a);
    }
}

运行结果:

排序前:          89    45    68    90    29    34    17    
排序第1趟:17    45    68    90    29    34    89    
排序第2趟:17    29    68    90    45    34    89    
排序第3趟:17    29    34    90    45    68    89    
排序第4趟:17    29    34    45    90    68    89    
排序第5趟:17    29    34    45    68    90    89    
排序第6趟:17    29    34    45    68    89    90    

 

2.3 冒泡排序原理简介

我们从列表的第一个元素开始,比较列表中相邻的两个元素,如果第一个元素大于第二元素,则交换这两个元素的位置,否则就从第二个元素位置开始重复上一步操作。重复多次以后,最大的元素就“沉到”列表的最后一个位置。这样一直做,直到n-1遍以后,该列表就排好序了。

2.4 具体编码(冒泡排序)

package com.liuzhen.chapterThree;

public class BubbleSort {
    
    public static void getBubbleSort(int[] a){
        int temp;      
        //打印输出未排序前数组序列
        System.out.print("排序前:          ");
        for(int p = 0;p < a.length;p++)
            System.out.print(a[p]+"\t");
        System.out.println();            
        for(int i = 0;i < a.length-1;i++){            
            for(int j = 0;j < a.length-1-i;j++){
                if(a[j+1] < a[j]){
                    //交换a[j]和a[j+1]的值
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
            //打印输出每一次选择排序结果
            System.out.print("排序第"+(i+1)+"趟:");
            for(int p = 0;p < a.length;p++)
                System.out.print(a[p]+"\t");
            System.out.println();
        }
    }
    
    public static void main(String args[]){
        int[] a = {89,45,68,90,29,34,17};
        getBubbleSort(a);
    }
}

运行结果:

排序前:          89    45    68    90    29    34    17    
排序第1趟:45    68    89    29    34    17    90    
排序第2趟:45    68    29    34    17    89    90    
排序第3趟:45    29    34    17    68    89    90    
排序第4趟:29    34    17    45    68    89    90    
排序第5趟:29    17    34    45    68    89    90    
排序第6趟:17    29    34    45    68    89    90    

 

算法笔记_008:选择排序和冒泡排序【蛮力法】