排序算法学习笔记（一）

待我称王封你为后i 2023-09-29 12:38 13阅读 0赞

**目录**

一：冒泡排序

二：选择排序

三：插入排序

四：希尔排序

--------------------

## 一：冒泡排序 ##

**1.1 基本介绍：**

> 冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），一次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部。
> 
> 因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。

![96f9474cb33b4601a06d2c29abe04ced.png][]

**小结：**

>  *  一共进行数组的大小-1次大的循环。
>  *  每一趟排序的次数在逐渐的减少。
>  *  如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序，这个就是优化。

package BubbleSort;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class BubbleSort {
        public static void bubbleSort(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                boolean flag = false;
                for (int j = 0; j < arr.length - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        flag = true;
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            Random r=new Random();
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=r.nextInt(10000);
            }
            long time1 = System.currentTimeMillis();
            bubbleSort(arr);
            long time2 = System.currentTimeMillis();
            System.out.println((time2-time1)/1000);
            //冒泡排序算法执行时间：12s
        }
    }

## 二：选择排序 ##

**2.1 基本介绍：**

> 选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

![341327b9a279406a9cbd626782b7904b.png][]

![9529e986257a497887c8e8966eb4d08c.png][]

说明：

> 1.  选择排序一共有数组大小-1轮排序。
> 2.  每一轮排序，又是一个循环的规则。
> 3.  先假定当前这个数是最小数。
> 4.  然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标。
> 5.  当遍历到数组的最后时，就得到本轮最小数和下标。
> 6.  交换。

package SelectSort;
    
    import java.util.Arrays;
    import java.util.Random;
    public class SelectSort {
        public static void main(String[] args) {
            Random r=new Random();
           // int[] arr={101,34,119,1,-1,90,123};
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=r.nextInt(10000);
            }
          //  System.out.println("排序前的数组："+ Arrays.toString(arr));
            long time1 = System.currentTimeMillis();
            selectSort(arr);
         //   System.out.println("排序后的数组："+ Arrays.toString(arr));
            long time2 = System.currentTimeMillis();
            System.out.println((time2-time1)/1000);
            //选择排序算法执行时间：2s
        }
        //选择排序，从小到大
        public static void selectSort(int[] arr){
            for(int i=0;i<arr.length-1;i++){
                int minIndex=i;
                int min=arr[i];
                for(int j=i+1;j<arr.length;j++){
                    if(min>arr[j]){
                        min=arr[j];
                        minIndex=j;
                    }
                }
               if(minIndex!=i){
                  arr[minIndex]=arr[i];
                  arr[i]=min;
               }
            }
        }
    }

## 三：插入排序 ##

**3.1 插入排序介绍：**

> 插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

**3****.2 插入排序法思想：**

> 插入排序的基本思想是：将n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

![f078fac7905f4c079db431747528a09c.png][]

package InsertSort;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class InsertSort {
        public static void main(String[] args) {
           /* int[] arr={12,1,6,88,55};
    
            System.out.println("排序前的数组："+ Arrays.toString(arr));
            InsertSort(arr);
            System.out.println("排序后的数组："+ Arrays.toString(arr));*/
            Random r=new Random();
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=r.nextInt(10000);
            }
            long time1 = System.currentTimeMillis();
            InsertSort(arr);
            long time2 = System.currentTimeMillis();
            System.out.println((time2-time1)/1000);
            //插入排序算法的执行时间大概为零点几秒
        }
        /*
        插入排序
         */
        public static void InsertSort(int[] arr){//从小到大排序
            for(int i=1;i<arr.length;i++){
                int InsertVal=arr[i];// 待插入的元素
                int InsertValIndex=i-1; //待插入的元素的前一个索引
                while (InsertValIndex>=0&&InsertVal<arr[InsertValIndex]){
                    //当待插入元素大于前面的元素，则进行插入，
                    // 如果索引到达-1时，说明带插入元素是该子数组中最小的元素
                    arr[InsertValIndex+1]=arr[InsertValIndex];//将元素右移
                    InsertValIndex--;
                }
                arr[InsertValIndex+1]=InsertVal;//将待插入元素进行插入
            }
        }
    }

## 四：希尔排序 ##

**4.1 导入问题：**

![63f6b87684c84aae8b8c5babb08f1b54.png][]

**4.2 希尔排序的概述：**

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

**4.3 希尔排序示意图：**

![20180606180430304][]

**4.4 希尔排序实例：**

![dc8e48687fe04ae6ac28a7fa26143846.png][]

**（1）希尔排序【交换式】代码实现：**

package ShellSort;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class ShellSort {
        public static void main(String[] args) {
            //希尔排序算法[交换式]测速：
            Random r=new Random();
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=r.nextInt(10000);
            }
            long time1 = System.currentTimeMillis();
            shellSort2(arr);
            long time2 = System.currentTimeMillis();
            System.out.println("希尔排序算法执行时间："+(time2-time1));
    
             /*
            int[] arr={8,9,1,7,2,3,5,4,6,0};
            System.out.println("排序前的数组："+Arrays.toString(arr));
            //[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
    
         //   shellSort1(arr);
            shellSort2(arr);
    
              */
        }
        //使用逐步推导的方法来编写希尔排序
        public static void shellSort1(int[] arr){
            int temp=0;
            //希尔排序的第一轮排序
            //因为第一轮排序，是将10个数据分成了5组
            for(int i=5;i<arr.length;i++){
                //遍历各组中所有的元素（共5组，每组有两个元素），步长5
                for(int j=i-5;j>=0;j-=5){
                    //如果当前元素大于加上步长后的那个元素，说明交换
                    if(arr[j]>arr[j+5]){
                        temp=arr[j];
                        arr[j]=arr[j+5];
                        arr[j+5]=temp;
                    }
                }
            }
            System.out.println("第一轮排序后的数组："+ Arrays.toString(arr));
            //[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
    
    
            //第二轮排序：
            for(int i=2;i<arr.length;i++){
                for(int j=i-2;j>=0;j-=2){
                    if(arr[j]>arr[j+2]){
                        temp=arr[j];
                        arr[j]=arr[j+2];
                        arr[j+2]=temp;
                    }
                }
            }
            System.out.println("第二轮排序后的数组："+ Arrays.toString(arr));
            //[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
    
            //第三轮排序：
            for(int i=1;i<arr.length;i++){
                for(int j=i-1;j>=0;j--){
                    if(arr[j]>arr[j+1]){
                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
                }
            }
            System.out.println("第三轮排序后的数组："+Arrays.toString(arr));
            //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        }
        //根据前面的逐步分析，使用循环处理
        public static void shellSort2(int[] arr){
            int temp=0;
            for(int gap=arr.length/2;gap>=1;gap/=2){
                for(int i=gap;i<arr.length;i++){
                    for(int j=i-gap;j>=0;j-=gap){
                        if(arr[j]>arr[j+gap]){
                            temp=arr[j];
                            arr[j]=arr[j+gap];
                            arr[j+gap]=temp;
                        }
                    }
                }
            }
        //    System.out.println("希尔排序后的数组："+Arrays.toString(arr));
            //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        }
    }

**（2）希尔排序【移位式】代码实现：**

package ShellSort;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class ShellSort02 {
        public static void main(String[] args) {
            //希尔排序算法【移位式】执行时间测试：
            Random r=new Random();
            int[] arr=new int[80000];
            for(int i=0;i<arr.length;i++){
                arr[i]=r.nextInt(800000);
            }
            long time1 = System.currentTimeMillis();
            ShellSort(arr);
            long time2 = System.currentTimeMillis();
            System.out.println("希尔排序算法执行时间："+(time2-time1));
            //执行时间：16ms
            /*
            int[] arr={8,9,1,7,2,3,5,4,6,0};
            System.out.println("排序前的数组："+ Arrays.toString(arr));
            ShellSort(arr);
            System.out.println("排序后的数组："+Arrays.toString(arr));
    
             */
        }
    
        public static void ShellSort(int[] arr) {
            //增量gap，并逐步的缩小增量
            for (int gap = arr.length / 2; gap > 0; gap /= 2) {
                //从第gap个元素，逐个对其所在的组进行直接排序
                for (int i = gap; i < arr.length; i++) {
                    int j = i;
                    int temp = arr[j];
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j]=arr[j-gap];
                        j -= gap;
                    }
                    //当退出循环后，就给temp找到插入的位置
                    arr[j]=temp;
                }
            }
        }
    }

--------------------

[96f9474cb33b4601a06d2c29abe04ced.png]: https://img-blog.csdnimg.cn/96f9474cb33b4601a06d2c29abe04ced.png
[341327b9a279406a9cbd626782b7904b.png]: https://img-blog.csdnimg.cn/341327b9a279406a9cbd626782b7904b.png
[9529e986257a497887c8e8966eb4d08c.png]: https://img-blog.csdnimg.cn/9529e986257a497887c8e8966eb4d08c.png
[f078fac7905f4c079db431747528a09c.png]: https://img-blog.csdnimg.cn/f078fac7905f4c079db431747528a09c.png
[63f6b87684c84aae8b8c5babb08f1b54.png]: https://img-blog.csdnimg.cn/63f6b87684c84aae8b8c5babb08f1b54.png
[Link 1]: https://so.csdn.net/so/search?q=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F&spm=1001.2101.3001.7020
[20180606180430304]: https://img-blog.csdn.net/20180606180430304
[dc8e48687fe04ae6ac28a7fa26143846.png]: https://img-blog.csdnimg.cn/dc8e48687fe04ae6ac28a7fa26143846.png