Day7 排序：插入排序和冒泡排序

素颜马尾好姑娘i 2021-09-18 04:50 325阅读 0赞

常用的排序：  
冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡、插入、选择</td> 
   <td>O(n^2)</td> 
   <td>基于比较</td> 
  </tr> 
  <tr> 
   <td>快排、归并</td> 
   <td>O(nlogn)</td> 
   <td>基于比较</td> 
  </tr> 
  <tr> 
   <td>桶、计数、基数</td> 
   <td>O(n)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

如何分析一个排序算法？

1.  排序算法的执行效率  
    a. 最好情况、最坏情况和平均情况的时间复杂度  
    b. 时间复杂度的系数、常数、低阶  
    c. 比较次数和交换次数
2.  排序算法的内存消耗
3.  排序算法的稳定性

##### **冒泡排序** #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1]  
冒泡排序示例：

public void bubbleSort(int[] arr, int n) {
    	if(n <= 1) 
    		return;
    	for(int i = 0; i < n; i++) {
    		boolean flag = false;
    		for(int j=0; j < n-i-1; j++) {
    			if(a[j] > a[j+1]) {
    				int tmp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = tmp;
    				flag = true;
    			}
    		}
    		if (!flag) { 
    			break;
    		}
    	}
    }

三问：

1.  冒泡排序是原地排序算法吗？  
    是，因为只需要常量级的临时空间，空间复杂度为O(1)
2.  冒泡是稳定的排序算法吗？  
    为了保证稳定排序，所以在比较的时候，当==的时候，不交换位置
3.  冒泡排序的时间复杂度？  
    最好 O(n) 最坏O(n^2)  
    平均O(n^2) **利用有序度和逆序度进行计算**

##### **插入排序** #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 3]  
示例代码：

public void insertSort(int[] arr, int n) {
    	if(n <= 1) return;
    	for(int i=1;i<n;i++) {
    		int value = arr[i];
    		int j=i-1;
    		for(;j >= 0; --j) {
    			if(arr[j] > value) {
    				a[j+1] = a[j]; // 往后搬移数组, 空出来一个位置
    			} else {
    				break;
    			}
    		}
    		a[j+1] = value;
    	}
    }

三问：

1.  插入排序是原地排序算法吗？  
    是，因为只需要常量级的临时空间，空间复杂度为O(1)
2.  插入是稳定的排序算法吗？  
    是
3.  插入排序的时间复杂度？  
    最好 O(n) 最坏O(n^2)  
    平均O(n^2)

##### **选择排序** #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 4]  
选择排序空间复杂度为 O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n^2)，并且不是稳定的排序。  
示例代码：

public  void sort(int[] arr) {
            int temp = 0; // temp 保存最小的值
            int index = 0; // 保存 最小值 temp 的索引位置
            // 共有n轮循环
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                temp = arr[i]; // 保存当前的最小值
                index = i; // 记录最小值的位置
                // 开始遍历，寻找最小值
                // 从第 i+1 个开始
                for (int j = i + 1; j < n; j++) {
                    // 如果有比 temp 小的值，就将当前值给到temp值，即当前的最小值
                    if (temp > arr[j]) {
                        index = j;
                        temp = arr[j];
                    }
                }
                // 一轮比较之后，如果最小值的索引不等于当前的索引值的话，说明要交换位置
                if (index != i) {
                    // 交换位置 swap
                    arr[index] = arr[i];
                    arr[i] = temp;
                }
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]: /images/20210918/ad20d0fa6bd64fa1880b098f498e94ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1]: /images/20210918/57b0ae3e2e3d419c90087b405daed682.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 2]: /images/20210918/1d06955a572846a9bd244520fa236509.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 3]: /images/20210918/c18913254e314e7c8c14152ec85af5bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 4]: /images/20210918/2258950cff2c488cb544447fdc743701.png