排序算法第三讲 --- 插入排序(Python、C++、C)

待我称王封你为后i 2023-02-23 07:49 2阅读 0赞

**排序算法系列目录**

[排序算法第一讲 — 冒泡排序(Python、C++、C)][_ _Python_C_C]  
  [排序算法第二讲 — 选择排序(Python、C++、C)][_ _Python_C_C 1]  
  [排序算法第三讲 — 插入排序(Python、C++、C)][_ _Python_C_C 2]  
  [排序算法第四讲 — 快速排序(Python、C++、C)][_ _Python_C_C 3]  
  [排序算法第五讲 — 希尔排序(Python、C++、C)][_ _Python_C_C 4]  
  [排序算法第六讲 — 归并排序(Python、C++、C)][_ _Python_C_C 5]

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

**题目描述：**

给你一个整数数组 nums，请你将该数组采用插入排序方式进行升序排列。  
![insertionSort.gif][]

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

**解题思路:**

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

**代码：**

Python写法：

class Solution(object):
        def solution(self,  nums):
    	    for i in range(1, len(nums)):
    	        for j in range(i-1, -1, -1):
    	            if nums[i] < nums[j]:
    	                nums[i], nums[j] = nums[j], nums[i]
    	                i = j  # 特别注意
    	    return nums

C++写法：

#include<iostream>
    using namespace std;
    
    int main()
    {
        
    	int  nums[5];
    	int  i, j, temp;
    	for (i = 0; i < 5; i++)
    		cin >> nums[i];
    
    	for(i=1; i<5; i++){
        
    		for(j=i-1; j>-1; j--){
        
    			if (nums[i]<nums[j]){
        
    				temp = nums[i];
    				nums[i] = nums[j];
    				nums[j] = temp;
    				i = j;
    			}
    		}
    	}
    
    	for (i = 0; i < 5; i++)
    		cout << nums[i] <<" ";
    
    	printf("\n");
        return 0;
    }

C语言：

#include <stdio.h>
    
    int main()
    {
        
    	int  nums[5];
    	int  i, j, temp;
    	for (i = 0; i < 5; i++)
    		scanf("%d", &nums[i]);
    
    	for(i=1; i<5; i++){
        
    		for(j=i-1; j>-1; j--){
        
    			if (nums[i]<nums[j]){
        
    				temp = nums[i];
    				nums[i] = nums[j];
    				nums[j] = temp;
    				i = j;
    			}
    		}
    	}
    
    	for (i = 0; i < 5; i++)
    		printf("%d ", nums[i]);
    
    	printf("\n");
        return 0;
    }

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

**题目来源：**

[http://lab.csdn.net/\#/question/38?tagId=16][http_lab.csdn.net_question_38_tagId_16]

[_ _Python_C_C]: https://blog.csdn.net/weixin_43283397/article/details/107119915
[_ _Python_C_C 1]: https://blog.csdn.net/weixin_43283397/article/details/107139196
[_ _Python_C_C 2]: https://blog.csdn.net/weixin_43283397/article/details/107146712
[_ _Python_C_C 3]: https://blog.csdn.net/weixin_43283397/article/details/107160931
[_ _Python_C_C 4]: https://blog.csdn.net/weixin_43283397/article/details/107242305
[_ _Python_C_C 5]: https://blog.csdn.net/weixin_43283397/article/details/107246548
[insertionSort.gif]: https://www.runoob.com/wp-content/uploads/2019/03/insertionSort.gif
[http_lab.csdn.net_question_38_tagId_16]: http://lab.csdn.net/#/question/38?tagId=16