10.4 10.5 选择排序、插入排序、冒泡排序

末蓝、 2022-05-15 03:13 113阅读 0赞

![70][]

![70 1][]

> 选择排序：先找最小值，然后交换位置。

![70 2][]

#include<iostream>
    using namespace std;
    
    int SelectionSort(int a[], int size)
    {
    	for(int i = 0; i < size - 1; ++ i)//最后一次不用比较 
    	{
    		int tmpMin = i;//假设第i个数最小 
    		for(int j = i; j < size; ++ j)//寻找未比较数中的最小值 
    		{
    			if(a[j] < a[tmpMin])
    				tmpMin = j;
    		}
    		int tmp;//交换位置 
    		tmp = a[tmpMin];
    		a[tmpMin] = a[i];
    		a[i] = tmp;
    	}
    }
    
    int main()
    {
    	int n, a[10];
    	cin >> n;
    	for(int i = 0; i < n; ++ i)
    		cin >> a[i];
    	SelectionSort(a,n);
    	for(int i = 0; i < n; ++ i)
    		cout << a[i] << " ";
    	return 0;
    }

![70 3][]

![70 4][]

[选择排序][Link 1]（这种方法好一些）

![70 5][]

> 插入排序：左边为有序部分，右边为无序部分。将无序部分的第一个数与有序部分比较，插入到有序部分中即可。

![70 6][]

#include<iostream>
    using namespace std;
    
    int InsertSort(int a[], int size)
    {
    	for(int i = 1; i < size; ++ i)//无序部分（让无序部分的每一个数分别与有序部分比较） 
    	{
    		for(int j = 0; j < i; ++ j)//有序部分 
    		{
    			if(a[i] < a[j])//如果发现无序部分的数小于有序部分的某个数
    			{
    				int tmp = a[i];//必须要这一步，否则后面这一步会改变a[i]的值 
    				for(int k = i; k > j ; -- k)//将有序部分的这个数及其以后的数依次往后移  
    					a[k] = a[k-1];
    				a[j] = tmp;
    				break;//变为有序序列后即可跳出循环 
    			}
    		}
    	}
     } 
     
    int main()
    {
    	int n, a[10];
    	cin >> n;
    	for(int i = 0; i < n; ++ i)
    		cin >> a[i];
    	InsertSort(a,n);
    	for(int i = 0; i < n; ++ i)
    		cout << a[i] << " ";
    	return 0;
    }

![70 3][]

[插入排序][Link 2]

![70 7][]

> 冒泡排序：整个数组都是无序序列，依次将相邻两个数比较，得到有序序列的第一个数（右边）

![121415da1aevwg0gzfva0i.png][]

![70 8][]

#include<iostream>
    using namespace std;
    
    void BubbleSort(int a[], int size)//从大到小排序
    {
    	for(int i = 0; i < size - 1; ++ i)
    	{
    		for(int j = 0; j < size - i; ++ j)//j < size - i，无序部分（左）需要两两比较排序 
    		{
    			if(a[j] < a[j + 1])
    			{
    				int tmp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = tmp;
    			} 
    		}
    	}
    } 
    int main()
    {
    	int n, a[10];
    	cin >> n;
    	for(int i = 0; i < n; ++ i)
    		cin >> a[i];
    	BubbleSort(a,n);
    	for(int i = 0; i < n; ++ i)
    		cout << a[i] << " ";
    	return 0;
    }

![70 9][]

#include<iostream>
    using namespace std;
    
    void BubbleSort(int a[], int size)
    {
    	for(int i = size - 1; i > 0; -- i)
    	{
    		for(int j = 0; j < i; ++ j)//j < size - i，无序部分（左）需要两两比较排序 
    		{
    			if(a[j] < a[j + 1])//改变大小于符号即可改变排序规则 
    			{
    				int tmp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = tmp;
    			} 
    		}
    	}
    } 
    int main()
    {
    	int n, a[10];
    	cin >> n;
    	for(int i = 0; i < n; ++ i)
    		cin >> a[i];
    	BubbleSort(a,n);
    	for(int i = 0; i < n; ++ i)
    		cout << a[i] << " ";
    	return 0;
    }

![70 10][]

> 这两种写法都正确，但是自我比较倾向于第二种写法。两种写法主要还是影响第二个for循环的表达方式，第二个for循环主要是指无序序列的范围，无序序列中的元素需要两两比较来交换数据。

很详细的冒泡排序：[https://www.cnblogs.com/ahalei/p/3563964.html][https_www.cnblogs.com_ahalei_p_3563964.html]

![70 11][]

[70]: /images/20220515/62601b4c3a894f47b101be90bc7a1933.png
[70 1]: /images/20220515/6420bafff4de4cdea9c7dbef71c995a2.png
[70 2]: /images/20220515/d723a07732f345adb29e763b359dba1b.png
[70 3]: /images/20220515/3fd790b40a4a44958c10508408a96248.png
[70 4]: /images/20220515/e7ceb1fb2e32441d897c6296defff35a.png
[Link 1]: https://blog.csdn.net/yanyanwenmeng/article/details/71155402
[70 5]: /images/20220515/230b18a5ebc7481ab27498bcc07849e4.png
[70 6]: /images/20220515/a680ac0ac18644888732d255e99fd4c4.png
[Link 2]: https://blog.csdn.net/yanyanwenmeng/article/details/71155228
[70 7]: /images/20220515/56fa87b322904e4cae44a340bff1ad88.png
[121415da1aevwg0gzfva0i.png]: http://bbs.ahalei.com/data/attachment/forum/201402/23/121415da1aevwg0gzfva0i.png
[70 8]: /images/20220515/9896f39096664a569a317ff0e67bc026.png
[70 9]: /images/20220515/433c842897d44f8fba213f7b878a688d.png
[70 10]: /images/20220515/b9d14ea8a90742efa9fdc425b2827033.png
[https_www.cnblogs.com_ahalei_p_3563964.html]: https://www.cnblogs.com/ahalei/p/3563964.html
[70 11]: /images/20220515/7b90854009f6480392cd0b5aeb07ab41.png