标签：arr arrIndex int insertIndex gap 算法排序数据结构

排序

冒泡排序法（交换）

基本原理：依次比较相邻元素的值，使值较大的元素逐渐前移或者后移，因为每一轮排序后值最大的元素一定是后移了一位。

xxx

//手写冒泡排序法
public static void bubbleSort(int arr[]){
    int temp = 0;//定义交换用的临时变量
    boolean flag = false;//定义一个局部变量
    for (int i = 0; i < arr.length - 1; i++) {//比较的轮次
        for (int j = 0; j < arr.length - 1 - i; j++) {//比较的具体数字
            if(arr[j] > arr[j + 1]){
                flag = true;
                temp = arr[j];//就是一个很简单的清空的思想
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if(!flag){//一旦出现已经不需要再交换的轮次，直接退出,对于大规模处理能够节省很多时间。
            break;
        }else{
            flag = false;
        }
    }
}

冒泡排序法的核心其实就是双重循环，知道每一轮要比较哪些内容就好。

选择排序法（交换）

基本原理：就是一个简单的迭代思想，每一轮逐步缩小范围

 //手写选择排序法
    public static void selectSort(int arr[]){
        for (int i = 0; i < arr.length - 1; i++) {//比较的轮次
            int minIndex = i;
            boolean flag = false;//设置一个索引便于后期优化
            int min = arr[minIndex];//暂时的最小值
            for (int j = i + 1; j < arr.length - 1; j++) {//找到最小值
                if (arr[j] < min){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){//就是将最小值与i交换
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

插入排序法（移位）

基本思想：将元素看成一个有序表和一个无序表，将无序表中的元素插入到有序表中（所以只要找到一个有序列表就好做了）

//重写插入排序
    public static void insertSort(int arr[]){
        int insertVal = 0;//待插入的数
        int insertIndex = 0;//待插入的索引
        for (int i = 1; i < arr.length ; i++) {
            insertVal = arr[i];//要插入的数字
            insertIndex = i - 1;//要比较的索引
            //用一个循环找到要插入的索引（因为是无序表向有序表插入，所以还是蛮容易的）
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];//肯定要向往前插入了，那么就要后推一步
                insertIndex--;//向前查找
            }
            if(insertIndex + 1 != i){//等于i就相当于不需要移动了，节省资源
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

注意：其实就是一个思想：就是后面的空出一个位置，然后前面的往后退，留出一个位置用来插入。

希尔排序法（移位）

注意：希尔排序是对简单插入排序的一种改进，由于当需要插入的数较小时，简单插入排序需要后移过多位数，即为缩小增量插入排序。

原理：

 //手工书写希尔排序算法
    public static void shellSort3(int arr[]){
        //首先进行希尔排序的分组
        for(int gap = arr.length / 2; gap > 0; gap /= 2){
            for (int i = gap; i < arr.length; i++) {//对分组进行插入排序
                int arrIndex = i;//要比较的索引
                int arrVal = arr[arrIndex];//要插入的数据,提前保存一下
                if(arr[arrIndex] < arr[arrIndex - gap]){
                    while(arrIndex - gap >= 0 && arrVal < arr[arrIndex - gap]){
                        arr[arrIndex] = arr[arrIndex - gap];//移位，相当于覆盖了
                        arrIndex -= gap;//待插入位置向前移动
                    }
                    arr[arrIndex] = arrVal;//找到索引后插入
                }
            }
        }
    }

快速排序法（递归）

思路：是对冒泡排序的改进：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码

 public static void fastSort(int[] arr,int begin,int end){
        if(begin > end)//代表该轮已经排序完毕，返回上一轮
            return;
        int tmp = arr[begin];//定义基准变量
        int i = begin;//左边的哨兵指针
        int j = end;//右边的哨兵指针
        while(i != j){//哨兵指针寻找的过程
            while(arr[j] >= tmp && j > i)
                j--;
            while(arr[i] <= tmp && j > i)
                i++;
            if(j > i){//将两个哨兵指针的值对换
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //其实就是完成基准数与第一个数的交换，temp为辅助变量
        arr[begin] = arr[i];//将基准变量的值赋给第一个变量
        arr[i] = tmp;//将基准变量的值赋给i
        fastSort(arr, begin, i-1);//左右两边的递归排序
        fastSort(arr, i+1, end);
    }

本质上就是两个哨兵指针的不断查询与交换，通过递归完成

帮助理解原理的两篇博文

快速排序法

快速排序法图解

不同排序算法的复杂度比较

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度
冒泡排序	O(n²)	O(n)	O(n²)	O(1)
选择排序	O(n²)	O(n²)	O(n²)	O(1)
插入排序	O(n²)	O(n)	O(n²)	O(1)
希尔排序	O(nlog₂ⁿ)	O(nlog₂ⁿ)	O(nlog₂ⁿ)	O(1)
快速排序	O(nlog₂ⁿ)	O(nlog₂ⁿ)	O(n²)	O(logⁿ):涉及到递归

——因为for循环和while循环如果完全执行就是n次的复杂度，这种最好情况就是不需要完全执行，比如冒泡排序法比较了一轮就退出。就是执行循环和不执行循环的区别。

标签：arr,arrIndex,int,insertIndex,gap,算法,排序,数据结构
From： https://www.cnblogs.com/robyn2022/p/16863105.html

排序——数据结构与算法学习

排序