C语言数组排序——冒泡排序、选择排序、插入排序

骑猪看日落 2021-11-02 11:30 420阅读 0赞

一、冒泡排序

原理解析：（以从小到大排序为例）在一排数字中，将第一个与第二个比较大小，如果后面的数比前面的小，则交换他们的位置。

然后比较第二、第三个……直到比较第n-1个和第n个，此时，每一次比较都将较大的一个数往后移动，所以第n个数是所有数中最大的一个。

之后再重复以上过程，直到将所有数据按从小到大顺序排列好。

编程实现：通过两个嵌套的循环实现。外层循环执行一次，内层循环执行一遍。

其中，内层循环控制比较时的下标，外层循环控制比较的总次数。

注意：

1、每多排好一个数，可以将内层循环次数减少一次，从而程序运行提高效率。

2、总共只需为n-1个数排序，剩下的一个为最小值，不需再排序。

对于从大到小排序是同样的原理。

代码：

\#include <stdio.h>

int main()

/\* 定义一个未序一维数组 \*/

int a\[10\] = \{ 1,2,3,6,5,4,7,0,8,-3\};

/\* 外层循环 控制比较“趟数”，每一趟排好一个数 \*/

for( int i = 9; i > 0; i-- )

/\* 内存循环 控制冒泡“次数”，每次向后冒泡 \*/

/\* 次数受外层循环控制，每趟少冒泡一次\*/

for (int j =0; j<i; j++)

/\* 当前元素为a\[j\] 如果当前元素大于下一个元素a\[j+1\]，交换值 \*/

if (a\[j\] > a\[j+1\] )

/\* 使用位运算 不通过第三方变量交换两个变量的值 \*/

a\[j\] = a\[j\]^a\[j+1\];

a\[j+1\] = a\[j\]^a\[j+1\];

a\[j\] = a\[j\]^a\[j+1\];

/\* 遍历输出已序数组 \*/

for (int i = 0; i < 10; i++)

printf("%d ",a\[i\]);

return 0;

二、选择排序

选择排序可以看做是冒泡排序的优化。在选择排序中，内层循环只负责寻找最大值的下标并保存，不需要频繁交换值。

原理解析：1、在n个数中，先找到最大的数并记录其下标，然后将这个数与第n个数交换值，如果刚好第n个数是最大数则不用交换。

2、重复第一步，直到所有数排好顺序

编程实现：两层循环嵌套，内循环寻找最大值的下标。

注意：选择最大值可以假定第0个元素是最大的，碰到比他大的值就更新 int maxIndex;

每次循环之前，maxIndex必须归0。

代码：

\#include <stdio.h>  
void main()  
\{  
　　int a\[10\] = \{ 5, 1, 6, 9, -8, 3, 4, 6, 10, 7 \};  
　　int maxindex = 0 ,  temp;  
　　for (int j = 9; j > 0; j--)  
　　\{  
　　　　maxindex = 0;  
　　　　for (int i = 1; i <= j; i++)  
　　　　\{  
　　　　　　if (a\[maxindex\] < a\[i\])  
　　　　　　\{  
　　　　　　　　maxindex = i;  
　　　　　　\}  
　　　　\}  
　　　　if (maxindex != j)  
　　　　\{  
　　　　　　temp = a\[maxindex\];  
　　　　　　a\[maxindex\] = a\[j\];  
　　　　　　a\[j\] = temp;  
　　　　\}  
　　\}  
　　for (int i = 0; i<10; i++)  
　　　　printf("%d ", a\[i\]);  
\}

三、插入排序

原理解析：将元素插入到已序数组中的相应位置，未排序数组将第一个元素视为已序数组。

代码实现：将第一个元素视为已序数列，按排序规则选择位置插入。两层循环嵌套，内层循环控制比较的次数。

代码：

\#include <iostream>  
using namespace std;

int main()  
\{  
　　int temp = 0;  
　　int a\[10\] = \{ 0 \};  
　　cout << "请输入十个数:" << endl;  
　　for (int i = 0; i < 10; i++)  
　　　　cin >> a\[i\];

// for循环，进行9次循环；  
　　for (int i = 1; i < 10; i++)  
　　// for循环，在每次大的循环中，a\[i\]从a\[1\]依次与它前面的数比较；  
　　for (int j = i - 1; j >= 0; j--)  
　　　　//如果a\[j + 1\]>a\[j\],则把这两个数组元素互换，目的把最大的数放到前边；  
　　　　if (a\[j + 1\] > a\[j\])  
　　　　\{  
　　　　　　temp = a\[j + 1\];  
　　　　　　a\[j + 1\] = a\[j\];  
　　　　　　a\[j\] = temp;  
　　　　\}else  
　　　　　　break;

//输出排好顺序的十个数；  
　　for (int i = 0; i < 10; i++)  
　　　　cout << a\[i\] << " ";

return 0;  
\}

转载于:https://www.cnblogs.com/ZhenXin0101/p/11328110.html