【无标题】

• 一.前提
• • Ⅰ.内部排序，外部排序、稳定性
  • Ⅱ.冒泡排序实现
  • Ⅲ.插入排序实现
  • Ⅳ.定理--引出对冒泡、插入排序的增强算法

1. 内部排序：将数据加载到内存中进行排序
2. 外部排序：数据不能完全加载到内存中，需要在内存之外进行排序
3. 稳定性：在比较两个相等元素的时候，不会交换他们的位置
   eg：[10,10]–>在进行比较后两数相等，并不会交换这两数的位置

package com.angle.sort;

import java.util.Arrays;


public class Bubbling_Sort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 1, 2, 7, 5, 3, 7, 34, 31, 2, 7, 5, 3, 7, 34, 31, 3, 7, 34, 31, 2, 7, 5, 3, 7, 34, 31};
        System.out.println(Arrays.toString(arr));
        bubbling_sort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    
    public static void bubbling_sort(int[] arr, int n) {
        //
        int flag = 1;

        //排序次数：n-1次
        for (int i = 1; i < n; i++) {
            //比较交换：如果待排序数组有10个，那么只需要比较9次
            for (int j = 0; j < n - i; j++) {
                //升序：小->大
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    //第一次排序如果没有交换，说明是有序的
                    flag = 0;
                }
            }
            if (flag == 1) {
                break;
            }
        }
    }

    //交换
    public static void swap(int[] arr, int index1, int index2) {
        int temp;
        temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

冒泡排序：
最好情况：有序T=O(N)
最坏情况：无序T=(N²)

package com.angle.sort;

import java.util.Arrays;


public class Insert_Sort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 1, 2, 7, 5, 3, 7, 34, 31, 2, 7, 5, 3, 7, 34, 31, 3, 7, 34, 31, 2, 7, 5, 7, 34, 31};
        System.out.println(Arrays.toString(arr));
        insert_sort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    
    public static void insert_sort(int[] arr, int n) {
        //记录插入比较元素的数据
        int temp;
        //取第二个元素开始，第一个元素开始没意义
        for (int i = 1; i < n; i++) {
            temp = arr[i];
            //由插入的元素temp从后往前进行比较(升序)
            for (int j = i; j > 0 && temp < arr[j - 1]; j--) {
                swap(arr, j - 1, j);
            }
        }
    }

    //交换
    public static void swap(int[] arr, int index1, int index2) {
        int temp;
        temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

插入排序：
最好情况：有序T=O(N)
最坏情况：无序T=O(N²)

逆序对：对于小表iarr[j]这样的称为逆序对

1. 定理一：任何N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
2. 定理二：任何以交换相邻两元素排序的算法，其平均时间复杂度为O(N²) 最好也就是N²
3. 这就意味着：要提高算法效率，我们必须
   逆序对的时候不止消除1个
   每次交换相隔较远的元素