排序—冒泡，选择，插入排序

谁借莪１个温暖的怀抱￠ 2022-05-18 11:10 161阅读 0赞

## 排序—冒泡，选择，插入排序 ##

##### 这是三种非常简单的排序算法，但同时我们也必须要牢牢掌握，最近一直在写java，所以也想试着用java写一些算法题目，来巩固自己的语言基础。下面是分别使用冒泡排序，选择排序，插入排序的代码，每种排序算法写在了相对应的方法中。 #####

public class SimpleSort {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int[] array = new int[1000];
            for (int i = 0; i < n; i++){
                array[i] = scan.nextInt();
            }
            //array = bubbleSort(array,n);
            //array = slectSort(array,n);
            array = insertSort(array,n);
            print(array,n);
        }
    
        public static int[] bubbleSort(int[] array,int n){
            //冒泡排序
            boolean flag = false;
            for (int i = 0; i < n && flag == false; i++){
                flag = true;
                for (int j = 0; j < n-1; j++){
                    if (array[j] > array[j+1]){
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                        flag = false;
                    }
                }
            }
            return array;
        }
    
        public static int[] slectSort(int[] array,int n){
            //选择排序
            for (int i = 0; i < n-1; i++){
                int min = i;
                for (int j = i+1; j < n; j++){
                    if (array[j] < array[min]){
                        min = j;
                    }
                }
                if (min != i){
                    int temp = array[i];
                    array[i] = array[min];
                    array[min] = temp;
                }
            }
            return array;
        }
    
        public static int[] insertSort(int[] array,int n){
            //插入排序
            for (int i = 1; i < n; i++){
                int j = 0;
                int sentry = array[i];
                for (j = i-1; j >= 0 && sentry < array[j]; j--){
                        array[j+1] = array[j];
                    }
                     array[j+1] = sentry;
                }
            return array;
        }
    
        public static void print(int[] array,int n){
            for (int i = 0; i < n; i++){
                System.out.print(array[i] + " ");
            }
        }
    
    }

#### 1.冒泡排序 ####

*  就向这种排序算法的名字一样，冒泡排序其实就是依次比较相邻的两个元素的大小，把更大的（或更小的）放在后面，这样一轮之后最后一个元素就是列表中最大的(或更小的)，再一直重复到只剩第一个元素，这个过程一步步把最大(或最小)的元素放在最后，就像是冒泡。
 *  优化：设置一个标记值并赋值为false，每次内循环之前将其改为true，如果内循环中发生了数据交换（说明还处于无序状态），flag = true，那么继续执行下一轮交换。但如果内循环中没有发生数据交换(说明已经处于有序状态)那么就不需要再进行比较了，直接跳出循环输出。

#### 2.选择排序 ####

*  再了解了冒泡排序的原理之后，我们会发现有很多多余的比较(比如上一轮比较过的两个元素下一轮还有可能继续比较)。所以我们决定：每一轮选择列表中的**最大值（最小值）**,并将其放在未排序的列表的第一位，以此类推达到有序

#### 3.插入排序 ####

*  还有没有其他简单的排序算法呢？答案是有的。我们假设，有一个有序的列表，我们要插入一个数，只需要从后往前找，当发现有元素小于它时，把它插入到这个比他小的元素的后面一位，其余后面的元素全部后移一位(为这个插入的元素腾出位置)，这就是所谓的插入排序。这里我们先假设第一个元素有序(一个元素肯定时有序的)，然后将第二个元素插入其中形成一个两个元素的列表，再从第三个元素开始，重复前面的动作，直到最后一个元素被插入

--------------------

### 总结：虽然冒泡排序，选择排序，插入排序的时间复杂度都是O(n²)。但实际使用起来 其效率其实时 插入排序> 选择排序> 冒泡排序的，但不管怎么样，这三种排序都是最基础的排序，都必须要掌握 ###