排序（冒泡，选择和插入）

冒泡排序

基本原理

冒泡排序：相邻的两个元素进行比较。
从小到大排：如果a[j]>a[j+1],交换a[j]和a[j+1]顺序;从大到小排：如a[j]<a[j+1],交换a[j]和a[j+1]顺序。
比较次数：外循环比较次数为a.length-1次，内循环比较次数a.length-i-1次。

实例:
（这里以升序为例）

public static void main(String[] args) {
        int [] a= {8,9,3,2,1};
        for (int i = 0; i < a.length-1; i++) {
            for (int j = 0; j < a.length-i-1; j++) {
                if(a[j]>a[j+1]){
                    int temp =a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }

        }
        System.out.println(Arrays.toString(a));
    }

运行结果：

平均时间复杂度：O（n^2）
稳定性：稳定

选择排序

基本原理

选择排序：这里以升序排序为例。
第一趟比较从第一个元素开始,依次和后面的所有元素进行比较,每找到一个比他小的元素就交换一次位置,第一趟结束后最小的数被找出。
第二趟用第二个元素与剩余元素比较,并按规则交换顺序。
每一趟结束后总有一个元素已经排好序,所以内循环会从第i个元素开始比较。
实例:

    public static void main(String[] args) {
        int [] a ={8,9,3,1,2};
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                if(a[i]>a[j]){
                    int temp =a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }
            }
            System.out.println(Arrays.toString(a));
        }
       //System.out.println(Arrays.toString(a));
    }

运行结果：

改进后的选择排序

原理

这里以升序排序为例。
在原有的选择排序基础上，设置一个变量记录当前次数中的最小值,不用每找到一个比他小的就交换顺序。
实例：

  public static void main(String[] args) {
        int [] a={9,6,8,9,2};
        for (int i = 0; i < a.length; i++) {
            int indexmin=i;
            for (int j = i; j <a.length ; j++) {
                if(a[indexmin]>a[j]){
                 indexmin=j;
                }
            }
            int temp =a[i];
            a[i]=a[indexmin];
            a[indexmin]=temp;
        }
        System.out.println(Arrays.toString(a));
    }
    

运行结果：

平均时间复杂度：O（n^2）
稳定性：不稳定

插入排序

基本原理

插入排序：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序
实例:

public static void main(String[] args) {
        int [] a = {8,9,7,6,5,4,3,2,1,0};
        for (int i = 0; i < a.length-1; i++) {
            int current = a[i+1];
            int p=i;//需要排序的前面有几个数字
            while(p>=0&&a[p]>current){
                a[p+1]=a[p];
                p--;
            }
            a[p+1]=current;

        }
        System.out.println(Arrays.toString(a));
    }

运行结果：

平均时间复杂度：O（n^2）
稳定性：稳定

本文地址：https://blog.csdn.net/crraxx/article/details/109818093