数据结构与算法——Java实现排序算法（一）

梦里梦外; 2024-03-30 09:35 8阅读 0赞

**目录**

一、排序算法

1.1 排序算法基本介绍

1.2 衡量程序执行的方法

1.2.1 事后统计法

1.2.2 事前估算的方法

二、 时间复杂度

2.1 时间频度

2.2 时间复杂度

2.2.1 常见的时间复杂度

2.2.2 常数阶O(1)

2.2.3 对数阶O(log2底n)

2.2.4 线性阶O(n)

2.2.5 线性对数阶O(nlogN)

2.2.6 平方阶O(n方)

2.2.7 立方阶O(n三次方）、K次方阶O(n的k次方)

2.3 平均时间复杂度和最坏时间复杂度

三、空间复杂度

四、冒泡排序算法

4.1 思路分析

4.2 代码实现

4.2.1 方式1

4.2.2 方式2

4.2.3 优化

五、选择排序算法

5.1 思路分析

5.2 代码实现

六、插入排序

6.1 思路分析

6.2 代码实现

6.3 插入排序存在的问题

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

## 一、排序算法 ##

### 1.1 排序算法基本介绍 ###

**将一组数据，依指定的顺序进行排列的过程。**

**分类：**

*  **内部排序：**将需要处理的所有数据都加载到内部储存器中进行排序
 *  **外部排序：**数据量过大，无法全部加载到内存，需要借助外部存储进行排序。先加载一部分排序，完成之后再加载一部分排序合并。

**常见的排序算法**

![ccdc72375c8a49cdb87292e877779ce5.png][]

### 1.2 衡量程序执行的方法 ###

#### 1.2.1 事后统计法 ####

这种方法可行但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，**这种方式要在同一台计算机的相同状态下运行才能比较哪个算法更快**

#### 1.2.2 事前估算的方法 ####

通过分析某个**算法的时间复杂度**来判断哪个算法更优

## 二、 时间复杂度 ##

### 2.1 时间频度 ###

**时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，**哪个算法中语句执行次数多，它花费的时间就对。一个算法中的**语句执行次数成为语句频度或时间频度，记为T(n).**

![319e90444946470599f15271b27cd25c.png][]

**忽略常数项**![af9b16426ec7439fb4fc21fd6aace110.png][]

**忽略低次项**![0a1ebd43df7946c0a1d5d2cc938a3257.png][]

**忽略系数**

![7b5888f541934730ba012333e4c27db6.png][]

### 2.2 时间复杂度 ###

一般情况下，算法中的基本操作语句的执行次数是问题规模n的某个函数，用T(n)表示，若某个辅助函数f(n)，使得n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)和T(n)的同数量级函数。记作T(n)=0(f(n)）,**称0(f(n)）为算法的渐进时间复杂度，简称时间复杂度。**

![3abdebad224c41ea89ab1f858963df1e.png][]

#### 2.2.1 常见的时间复杂度 ####

**常数阶其实是最好的**

![cc2a1cb9099143a284c3dde8876246a9.png][]

#### **2.2.2 常数阶O(1)** ####

**无论代码执行多少行，只要没有循环等复杂结构，那这个代码的时间复杂度都是O(1)**

![4762f42b9ba94c808f76b18ae751e003.png][]

上述的代码在执行过程中，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码多长，即是有几万几十万行，都可以用O(1)来表示它的时间复杂度

#### 2.2.3 对数阶O(log2底n) ####

这个地方牵扯了高中的一个基础知识，如果不太懂可以看看log相关数学基础知识

![bf0c7d9680bb42bd85c1f68afc7fb7a0.png][]

#### 2.2.4 线性阶O(n) ####

此代码f**or循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的**

因此这类代码可以用**O(n)**来表示它的时间复杂度

int i;
    int j;
    for(i =1;i<=n;i++){
       j=i;
       j++;
    
    }

#### 2.2.5 线性对数阶O(nlogN) ####

这个也是很好理解的， 单个while循环是O(log2底n)，但是外面的for循环是O(n)，所以为O(nlogn)

for(m =1;m<n;m++){
       i=1;
       while(i<n){
         i=i*2;
       }
    
    }

#### 2.2.6 平方阶O(n方) ####

for(x=1;i<=n;x++){
    
       for(i=1;i<=n;i++){
           j=i;
           j++;  
       }
    
    }

![550ccf38dafc479495f154c5aaef064b.png][]

#### 2.2.7 立方阶O(n三次方）、K次方阶O(n的k次方) ####

三层for循环、多层for循环

### 2.3 平均时间复杂度和最坏时间复杂度 ###

*  **平均时间复杂度**：指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
 *  **最坏时间复杂度**：最坏情况下的时间复杂度，**一般讨论的时间复杂度均是最坏情况下的时间复杂度。**

**原因是，**最坏情况下的时闻复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

*  平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:).

![39ebd91465d643e88cff52bc9b983f3b.png][]

## 三、空间复杂度 ##

*  类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为**该算法所耗费的存储空间，它也是问题规模 n 的函数。**
 *  **空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。**有的算法需要占用的2)临时工作单元数与解决问题的规模 n有关，它随着 的增大而增大，当n 较大时，将占用较多的存储单元，例如快速排序和归并排序算法，基数排序就属于这种情况
 *  **在做算法分析时，****主要讨论的是时间复杂度。****从用户使用体验上看，更看重的程序执行的速度一些缓存产品(redis,memcache)和算法(基数排序)本质就是用空间换时间**

## 四、冒泡排序算法 ##

**基本思想：通过对待排序序列从前往后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换**

**简言之： 较大元素从前往后移动。**

**优化：（这里是等冒泡排序写好后再进行优化 ）**因为排序过程中，哥哥元素不断接近自己的位置，如果一趟下来没有进行交过，就说明序列有序。因此在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的麻烦。

### 4.1 思路分析 ###

![0693a8a47f4d44c9a8a2a08fe614baef.png][]

**为什么会循环数组大小的n-1次呢？**

**因为最后一个就不用比了，一定是最小的，放在原位置就行了，比也没有用，这是在这个位置**

### 4.2 代码实现 ###

#### 4.2.1 方式1 ####

**第一个for循环相当于是第几趟排序，第二个for循环相当于第几趟排序里面的小交换**

public class BubbleSort {
        public static void main(String[] args) {
            int arr[] ={3,9,-1,10,-2};
            int temp;
    
    //      外层在此时循环arr.length-1次，因为剩下一个数不用比也知道他是最小的了
            for(int i=arr.length-1;i>0;i--){
    //          下面的for循环就是找出每次比较结果中最大的放到右侧
    //          如果i是4的话，就比较4次,我们筛选出来的最大的就不用比较了
                for(int j=0;j<i;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));
            
        }
    }

#### 4.2.2 方式2 ####

int arr[] ={3,9,-1,10,-2};
            int temp;
    
            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]){
                        temp =arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                    }
    
                }
            }
            System.out.println(Arrays.toString(arr));

#### 4.2.3 优化 ####

int arr[] ={3,9,-1,10,-2};
            boolean flag =false;
            int temp;
    
            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){
    //               如果运行到这里是false，说明根本没走上面的for循环进行交换，即顺序已经确定
    //               说明我们的第二个for循环中一次也没交换，说明已经成功排序完成了
                    break;
                }else {
    //              重置flag，以防对下次判断产生影响
                    flag = false;
                }
            }
            System.out.println(Arrays.toString(arr));

## 五、选择排序算法 ##

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

### 5.1 思路分析 ###

**简要的说：**我们**并不需要每一次比较都交换两个数**，我们只需要转换最小的那个数和我们想要换到的那个位置上的数就行，这样省去中间很多次的交换

![ea02f62b407947e1873dcb236786295b.png][]

### 5.2 代码实现 ###

**效率要比冒泡排序算法快很多很多**

int arr[] ={3,9,-1,10,-2};
            boolean flag =false;
            int temp;
    //      我们先把数组下标为0的数定为最小的数
            int min ;
            int index=0;
    
    //      数组中有几个数，就要有n-1次大排序
            for(int i=0;i<arr.length-1;i++){
                min=arr[i];
                index=i;
    //          一直比到尾部，所以是j<arr.length
    //          我们把最小的放到左边，所以已经放的就不放了，故从 j=i开始
                for( int  j=i;j<arr.length;j++){
                    if(arr[j]<min){
    //                 这样的目的就是找出最小数
                        min = arr[j];
                        index=j;
                    }
                }
                if(index !=i){
                    arr[index] = arr[i];
                    arr[i]= min;
    
                }
    //            if(arr[i] != min){
    //                temp = arr[i];
    //                arr[i]=arr[index];
    //                arr[index]=temp;
    //            }
            }
            System.out.println(Arrays.toString(arr));

## 六、插入排序 ##

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

### 6.1 思路分析 ###

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

**下面是从小到大的排序方法**

![bf3db4fd03ab4b36904f0a72ddb64e97.png][]

### 6.2 代码实现 ###

public class InsertSort {
        public static void main(String[] args) {
            int[] arr ={101,34,119,1};
            insertSort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static  void insertSort(int[] arr){
    //      代表我们接下来要插入的数据
            int insertVal;
    //      我们要将数据插入在下标为几处
            int insertIndex;
    
    //      这个和之前的不一样，我们这里i<arr.length，一定要注意
    //      我们要从i=1开始遍历插入，因为插入第一个的时候根本就不需要比较，直接插入记性
    //      因为我们省去了i=0这一次循环，故我们循环结束条件是i<arr.length
            for(int i=1;i<arr.length;i++){
    
                insertVal=arr[i];
    //          初始时是待插入位置的前一个位置，是i的前一个，故是i-1
                insertIndex=i-1;
    
    //          insertIndex>=0 保证下标不越界
    //          insertVal<arr[insertIndex]
    //          循环一下，目的就是找到要插入的前一个位置index
                while(insertIndex>=0 && insertVal<arr[insertIndex]){
    //              insertVal<arr[insertIndex]表示我们还没有找到插入的位置，因为我们想把大的一次性插入到位
    //              所以我们先要让insertIndex位置处的数往后移动一个元素
    //              有人回想，那这样insertIndex+1，insertIndex这两处这不都是一个样的数了？
    //              没关系，我们最终会把insertIndex位置处的元素替换成insertVal
                    arr[insertIndex+1] =arr[insertIndex];
                    insertIndex--;
                }
    
    //          当我们退出while循环的时候，说明插入的位置找到了
    //          为什么要insertIndex+1？因为我们while循环最后一次执行完成之后-1了
    //          换句简单的来说，insertIndex本来我们规定的含义就是我们插入的前一个位置，则insertIndex+1便是我们要插入的位置
                if(insertIndex+1!=i){
                    arr[insertIndex+1] = insertVal;
                }
    
            }
        }
    }

### 6.3 插入排序存在的问题 ###

![4298e4cb8ae349a495ae037355340414.png][]

**如果有一个数很小，而这个数恰好在后面，则需要移动很多次才可以完成这个操作**

##  ##

[ccdc72375c8a49cdb87292e877779ce5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b6026094810441aeafa0149e8611b105.png
[319e90444946470599f15271b27cd25c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9b79cb2cb5fa4a0793b604fe3e4c629c.png
[af9b16426ec7439fb4fc21fd6aace110.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/53f986706ca04f8495d69bb472b92fcd.png
[0a1ebd43df7946c0a1d5d2cc938a3257.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c99d92f40cce4dc9aead0d9b23494a94.png
[7b5888f541934730ba012333e4c27db6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/89fc6540cd3640c8892cb224c06c1919.png
[3abdebad224c41ea89ab1f858963df1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4efb7e42485540bf88bff93860438d68.png
[cc2a1cb9099143a284c3dde8876246a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bee7e4acebe1414e80f871f5df7c19a4.png
[4762f42b9ba94c808f76b18ae751e003.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5276856c23ac4d57a641fc5b51fe3551.png
[bf0c7d9680bb42bd85c1f68afc7fb7a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/301c58d5d9d341a78b093324582407d0.png
[550ccf38dafc479495f154c5aaef064b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bc0437f3d1694e25b0eea4094f1b6a6d.png
[39ebd91465d643e88cff52bc9b983f3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/29ccea5953a14805a428be0df5105c4e.png
[0693a8a47f4d44c9a8a2a08fe614baef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/198cc55b7d67411784b7e7267a301061.png
[ea02f62b407947e1873dcb236786295b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/67eaac32f2734036891c59b47616f51c.png
[bf3db4fd03ab4b36904f0a72ddb64e97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/be493fb9a0344342a4ad6091b4f4cf85.png
[4298e4cb8ae349a495ae037355340414.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8ad9fb744c994a4b9738102f91e7d6f7.png