冒泡，选择，插入，希尔排序算法

梦里梦外; 2022-11-13 06:22 101阅读 0赞

#### 一、冒泡排序 ####

##### 1、算法步骤 #####

*  比较相邻的元素，如果第一个比第二个大，就交换他们的位置
 *  对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对处理完，最后的元素为最大的元素
 *  重复以上的步骤，最后比较元素为从最后一个元素依次递减。直到没有元素比较  
    ![在这里插入图片描述][fc1a81ca0d12458fc9aba855d15b259d.png_pic_center]

##### 2、java代码 #####

public class MaoPaoSort { 
        public static void main(String[] args) { 
            int[] arr = { 5,2,4,10,0,3,1};
            maopao(arr);
            for (int i:arr){ 
                System.out.println(i);
            }
        }
    
        public static void maopao(int[] arr){ 
            //从从到尾开始遍历
            for (int i = 0; i < arr.length; i++) { 
                //从头开始遍历把最大值放在最后面
                for (int j = 1; j < arr.length - i; j++) { 
                    int temp = arr[j - 1];
                    //如果前面比后面数据大，则交换数据
                    if (temp > arr[j]) { 
                        arr[j - 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    
    }

复杂度分析

时间复杂度：
    最坏情况：O(n2)
    最好情况：O(n)
    平均情况：O(n2)
    
    空间复杂度：O(1)
    
    稳定性：稳定
    复杂性：简单

#### 二、选择排序 ####

##### 1、算法步骤 #####

*  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。  
    ![在这里插入图片描述][8c42ffa5ab7186aa7f09e4ce68e338b9.png_pic_center]

##### 2、java算法 #####

/** * 选择排序算法 */
    public class SelectSort { 
        public static void main(String[] args) { 
            int[] arr = { 5,2,4,10,0,3,1};
            selectsort(arr);
            System.out.println("排序后数组：");
            for (int i:arr){ 
                System.out.println(i);
            }
        }
        public static void selectsort( int[] arr){ 
            //记录最小值的索引
            int min = 0;
            //遍历 n-1 轮，最后一个数不用遍历比较
            for (int i = 0; i < arr.length - 1; i++) { 
                min = i; //初始最小值为每轮循环的第一个数
                //遍历初始最小值后的所有数
                for (int j = i + 1; j < arr.length; j++) { 
                    if (arr[min] > arr[j]) {  //判断是否存在比最小值小的数
                        min = j; //记录下标
                    }
                }
                if (min != i) {  //判断最小值的索引是否等于初始最小值的索引
                    int temp = arr[min]; //不是则进行最小值交换
                    arr[min] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }
    
    解析：
    第 1 趟排序： index = 0, min = 0, 交换后 --> 0,2,4,10,5,3,1
    第 2 趟排序： index = 1, min = 6, 交换后 --> 0,1,4,10,5,3,2
    第 3 趟排序： index = 2, min = 6, 交换后 --> 0,1,2,10,5,3,4
    第 4 趟排序： index = 3, min = 5, 交换后 --> 0,1,2,3,5,10,4
    第 5 趟排序： index = 4, min = 6, 交换后 --> 0,1,2,3,4,10,5
    第 6 趟排序： index = 5, min = 6, 交换后 --> 0,1,2,3,4,5,10

*  时间复杂度：O(n2)
 *  空间复杂度（O1）

#### 三、插入排序 ####

##### 1、 算法步骤 #####

*  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 *  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）  
    ![在这里插入图片描述][a25adfc3e4352177d55c693997e6d87e.png_pic_center]

##### 2、 java代码 #####

/** * 插入排序算法 */
    public class InsertSort { 
        public static void main(String[] args) { 
            int[] arr = { 5,2,4,10,0,3,1};
            quickSort(arr);
            System.out.println("排序后数组：");
            for (int i:arr){ 
                System.out.println(i);
            }
        }
    
        private static void quickSort(int[] arr) { 
            for (int i = 1; i < arr.length; i++) { 
                // 记录要插入的数据
                int tmp = arr[i];
                // 从已经排序的序列最右边的开始比较，找到比其小的数
                int j = i;
                while (j > 0 && tmp < arr[j - 1]) { 
                    arr[j] = arr[j - 1];
                    j--;
                    // 存在比其小的数，插入
                    arr[j] = tmp;
                }
            }
        }
    }
    
    解析：
    2,5,4,10,0,3,1  tmp=2,5>2交换
    2,4,5,10,0,3,1  tmp=4,5>4交换
    2,4,5,10,0,3,1  tmp=10,5<10,不交换
    2,4,5,10,0,3,1  tmp=0,10>0,交换,循环比较前面的数
    2,4,5,0,10,3,1
    2,4,0,5,10,3,1
    2,0,4,5,10,3,1
    0,2,4,5,10,3,1
    依此类推...

复杂度

时间复杂度：
    最坏情况：O(n2)
    最好情况：O(n)
    平均情况：O(n2)
    
    空间复杂度：O(1)
    稳定性：稳定

#### 四、希尔排序 ####

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

##### 1、算法步骤 #####

初始时，有一个长度为7无序序列。

*  在第一趟排序中，设 step = N / 2 = 3(取整数)，即相隔距离为 3 的元素组成一组，可以分为 3 组。按照直接插入排序的方法对每个组进行排序。
 *  第二趟排序中，把上次的 step 缩小一半，即 step = step / 2 = 1 。即每相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。  
    ![在这里插入图片描述][20200705212524499.gif_pic_center]

##### 2、 java代码 #####

//希尔排序
    public class ShellSort { 
        public static void main(String[] args) { 
            int[] arr = { 5,2,4,10,0,3,1};
            shellSort(arr);
            System.out.println("排序后数组：");
            for (int i:arr){ 
                System.out.println(i);
            }
        }
        public static void shellSort(int[] arr) { 
            int length = arr.length;
            int temp;
            for (int step = length / 2; step >= 1; step /= 2) { 
                for (int i = step; i < length; i++) { 
                    temp = arr[i];
                    int j = i - step;
                    while (j >= 0 && arr[j] > temp) { 
                        arr[j + step] = arr[j];
                        j -= step;
                    }
                    arr[j + step] = temp;
                }
            }
        }
    }
    
    **过程解析：**
    5  2  4  10  0  3  1  ----step=3
    5        10           ----第1次比较,tmp=10,arr[0]<10,不交换
       0         2        ----第2次比较,tmp=0,arr[1]=2>temp,交换
          3         4     ----第3次比较,tmp=3,arr[2]=4>temp,交换
             1        10  ----第4次比较,tmp=1,arr[3]=10>temp,交换
    1        5        10  ----第5次比较,tmp=1,arr[0]=5>temp,交换
    step为3，比较后的数据如下：
    1  0  3  5   2  4  10
    
    接下来 step=3/2=1,
    0,1,3,5,2,4,10   -第6次比较，1>0,交换
    0,1,3,5,2,4,10   -第7次比较，1<3,不交换
    0,1,3,5,2,4,10   -第8次比较，3<5,不交换
    0,1,3,2,5,4,10   -第9次比较，5>2,交换
    0,1,2,3,5,4,10   -第10次比较，3>2,交换
    0,1,2,3,5,4,10   -第11次比较，1<2,不交换
    0,1,2,3,5,4,10   -第12次比较，0<1,不交换
    0,1,2,3,4,5,10   -第13次比较，5>4,交换
    0,1,2,3,4,5,10   -第14次比较，5<10,不交换，结束

复杂度  
![在这里插入图片描述][20210326105432205.png]

时间复杂度：
    最坏情况：O(n2)
    最好情况：O(n1.3)
    平均情况：O(nlogn-O(n2))
    
    空间复杂度：O(1)
    稳定性：不稳定

[fc1a81ca0d12458fc9aba855d15b259d.png_pic_center]: /images/20221022/224e259d0e0946269a69791a18c54441.png
[8c42ffa5ab7186aa7f09e4ce68e338b9.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/8c42ffa5ab7186aa7f09e4ce68e338b9.png#pic_center
[a25adfc3e4352177d55c693997e6d87e.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/a25adfc3e4352177d55c693997e6d87e.png#pic_center
[20200705212524499.gif_pic_center]: https://img-blog.csdnimg.cn/20200705212524499.gif#pic_center
[20210326105432205.png]: https://img-blog.csdnimg.cn/20210326105432205.png