排序算法（一）选择排序+插入排序+冒泡排序--O(n2)的排序算法

野性酷女 2023-07-12 03:47 42阅读 0赞

### 文章目录 ###

*  选择排序
 *  插入排序
 *  冒泡排序
 *   *  冒泡排序的非优化版本
     *  冒泡排序的优化版本

首先是对于排序以及算法得一个相关概述，摘自网上一大神得博客，言简意赅，如下：

1.  稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2.  非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3.  原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4.  非原地排序：需要利用额外的数组来辅助排序。
5.  时间复杂度：一个算法执行所消耗的时间。
6.  空间复杂度：运行完一个算法所需的内存大小。  
    下面开始我对于排序的归纳与总结：

# 选择排序 #

> 排序过程：首先，找到数组中最小的元素，然后将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法就叫选择排序。

package sorting;
    import java.util.Scanner;
    /**
     * @ClassName SelectionSort.java
     * @Description 选择排序
     * @Author ZBW
     * @Date 2020年03月06日 20:26
     **/
    public class SelectionSort {
        public static int[] sort(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int index = i;
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] <= array[index]) {
                        index = j;
                    }
                }
                //进行交换
                int temp = 0;
                temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
            return array;
        }
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入待排序数据个数：");
            //输入需要排序的数据个数
            int n = in.nextInt();
            int[] array = new int[n];
            System.out.println("请输入待排序数据：");
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int[] res = sort(array);
            print(res);
        }
    	//打印结果
        public static void print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

*  观察上面排序函数sort()，其时间复杂度为**O(n2)**，空间复杂度为**O(1)**
 *  属于**原地排序**
 *  属于**非稳定排序**

# 插入排序 #

> 排序过程：
> 
> 1.  从数组第2个元素开始抽取元素。
> 2.  把它与左边第一个元素比较，如果左边第一个元素大于它，就继续与左边下一个元素比较下去，直到遇到小于它的元素，然后插到这个元素的右边。
> 3.  继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入，知道第n个元素，完成排序。

package sorting;
    
    import java.util.Scanner;
    
    /**
     * @ClassName InsertionSort.java
     * @Description 插入排序
     * @Author ZBW
     * @Date 2020年03月06日 21:22
     **/
    public class InsertionSort {
    
        private static int[] sort(int[] array) {
            if (array == null || array.length < 2) {
                return array;
            }
            for (int i = 1; i < array.length; i++) {
                int temp = array[i];
                int k = i - 1;
                while (k >= 0 && array[k] > temp) {
                    k--;
                }
                //k+1到i之前的元素都右移，来把k+1空出来
                for (int j = i; j > k + 1; j--) {
                    array[j] = array[j-1];
                }
                //在索引为k+1的地方插入
                array[k+1] = temp;
            }
            return array;
        }
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入待排序数据个数：");
            //输入需要排序的数据个数
            int n = in.nextInt();
            int[] array = new int[n];
            System.out.println("请输入待排序数据：");
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int[] res = sort(array);
            print(res);
        }
        public static void print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

*  观察上面排序函数sort()，算法时间复杂度为**O(n2)**，空间复杂度为**O(1)**
 *  属于**原地排序**
 *  属于**稳定排序**

# 冒泡排序 #

> 排序过程
> 
> 1.  把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….
> 2.  我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。
> 3.  除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

## 冒泡排序的非优化版本 ##

package sorting;
    
    import java.util.Scanner;
    
    /**
     * @ClassName BubbleSort.java
     * @Description 冒泡排序
     * @Author ZBW
     * @Date 2020年03月06日 21:27
     **/
    public class BubbleSort {
    
        private static int[] sort(int[] array) {
            if (array.length < 2) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                for (int j = 0; j < array.length - i -1; j++) {
                    if (array[j] > array[j+1]) {
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                }
            }
            return array;
        }
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入待排序数据个数：");
            //输入需要排序的数据个数
            int n = in.nextInt();
            int[] array = new int[n];
            System.out.println("请输入待排序数据：");
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int[] res = sort(array);
            print(res);
        }
        public static void print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

*  观察上面的sort()函数，时间复杂度为**O(n2)**，空间复杂度为**O(1)**
 *  属于**原地排序**
 *  属于**稳定排序**

## 冒泡排序的优化版本 ##

> 引入一个flag作为标志，加入一趟冒泡下来，并没有发生位置的交换，就证明该数组已经属于有序数组，则直接胜率去后面的比较冒泡操作

private static int[] sort(int[] array) {
            if (array.length < 2) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                boolean flag = true;
                for (int j = 0; j < array.length - i -1; j++) {
                    if (array[j] > array[j+1]) {
                        flag = false;
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                }
                if (flag) {
                    break;
                }
            }
            return array;
        }

*  观察上面的sort()函数，时间复杂度为**O(n2)**，空间复杂度为**O(1)**
 *  属于**原地排序**
 *  属于**稳定排序**

注意：优化版本相对于非优化版本，在数组已经有序的情况下，减少了一些多余的操作