大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
选择法排序
选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中最小的那个交换位置,以此类推,直到最后一个数字。
例如输入数组{7,5,4,8,6,2,3}
第一次排序通过查找最小的数字,交换7与2的位置;第二次查找5后面最小的数字,找到了3,交换5与3的位置;第三次查找4之后最小的数字,发现并没有数字比4小,交换4与4的位置(相当于没有改变);第四次查找8后面最小的数字5,交换8与5的位置。
起始值 | 7 | 5 | 4 | 8 | 6 | 2 | 3 |
---|---|---|---|---|---|---|---|
第一次排序 | 2 | 5 | 4 | 8 | 6 | 7 | 3 |
第二次排序 | 2 | 3 | 4 | 8 | 6 | 7 | 5 |
第三次排序 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
因为剩下的数字中,可能有不止一个数字比当前数字小,所以需要一个临时值来储存当前最小的数字,还需要一个标志位来记录当前最小数字对应的位号。实现代码如下:
for(i = 0;i < n-1;i++)
{
temp = a[i];
iPot = i;
for(j = i+1;j < 10;j++) //从每一个数字依次向后查找
{
if(a[j] < temp)
{
temp = a[j]; //记录当前查找到的最小值与最小值对应的位号
iPot = j;
}
}
a[iPot] = a[i];
a[i] = temp;
}
选择法排序逻辑简单,容易实现。共需要进行(n-1)!次比较,(n-1)次交换位置。计算量是固定的。对于较大的n运算速度较慢。
冒泡法排序
冒泡法排序是指:在排序时,每次比较数组中的相邻两个数组元素的值,将较小的数排在较大的数前面。
例如还是输入数组{7,5,4,8,6,2,3}
7 | 5 | 4 | 8 | 6 | 2 | 3 |
---|
先比较2与3的大小,此时无需交换位置。
再比较6与2的大小,将2排在6的前面。
7 | 5 | 4 | 8 | 2 | 6 | 3 |
---|
再比较2与8的大小,将2排在8的前面。
7 | 5 | 4 | 2 | 8 | 6 | 3 |
---|
来看看代码是怎么实现的
int a[10];
int temp;
for(int i = 0;i < 10;i++)
{
for(int j = 9;j > i;j--)
{
if(a[j] < a[j-1])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
这里的内循环for(int j = 9; j > i ; j –),只能从大到小递减来对比,这样才能保证可以把最小的数排到前面去。如果用for(int j = i+1;j < 9; j ++) 则无法保证把最小的数排到前面来。只有内外循环交错才能保证排序顺利进行。冒泡法排序是相对稳定的排序方法。
交换法排序
交换法排序是将每一位数与它之后的所有数字对比,如果发现比它小的数字,那么立即交换这两个数字的位置,连续向后对比直至最后一个数;然后再使用第二个数同样依次向后对比,直到排序完成。交换法排序和前面的选择法排序有些类似,选择法是找出后面最小的那个数字交换位置,而交换法则是后面只要有比当前数字小的值,立即交换位置,再继续对比。这样可以节约记录中间值和记录中间值对应位号的2个空间。但是需要更多次的交换运算。在数组基本有序时速度比选择法快。
int a[10];
for(i = 0;i <9;i++)
{
for(j = i+1;j < 10;j++)
{
if(a[j] < a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
插入法排序
插入法排序比较复杂,基本原理就是抽出一个数据,寻找相应的位置插入,再抽出一个数据,寻找相应的位置插入,直到完成排序。简单来说就是,对于一个数组来说,先取数组中的第二个数字,和第一个数字对比,如果比第一个数字小,则放到第一个数字前面;如果比第一个数字大,则放到第一个数字后面。然后取数组中第三个数字,与第二个数字和第一个数字对比,以此类推。
int a[10];
int iPos;
for(i = 1;i < 10;i++)
{
temp = a[i]; //待插入的数字
iPos = i-1;
while((iPos >= 0) && (a[iPos] > temp))
{
a[iPos+1] = a[iPos];
iPos--;
}
a[iPos+1] = temp;
}
假设现在有这样一段数列{1,2,3,6,9} 而下一个待插入的数是 a[5] = 4
也就是待插入值temp = 4,i = 5,iPos=4 那么函数是这样运行的:
先对比待插入的值temp 与 a[4] = 6 的大小,此时temp = 4,满足while循环,那么就把原来a[4]的值放在a[5]上
1 | 2 | 3 | 6 | 9 | |
---|---|---|---|---|---|
1 | 2 | 3 | 6 | 9 |
此时iPos自减,仍然满足while循环条件,继续执行while循环代码。再来对比temp与a[3]的大小,此时temp仍然为4,在while循环里并没有更改temp的值。发现a[3]还是小于temp,于是继续把a[3]也往后放一个,放到a[4]的位置。
1 | 2 | 3 | 6 | 9 | |
---|---|---|---|---|---|
1 | 2 | 3 | 6 | 9 |
此时iPos自减,但是因为a[2] = 3,那么a[2]的值比temp小,所以while循环结束,跳出循环。只需要将待插入的值temp的值填在此时空出来的a[iPos+1] 的位置即可。
1 | 2 | 3 | 4 | 6 | 9 |
---|
折半法排序
折半法排序又称为快速排序,是选取一个中间值,然后把比中间值小的数字放在左边,比中间值大的数字放在右边。然后两边分别递归使用这个过程。折半法排序对于较大的n时有较快的运算速度,但是折半法排序是不稳定的,对应有相同关键字的记录,排序后结果可能会颠倒次序。但是可以通过对这种排序方法的学习,来熟悉了解一些递归的思想,以及二分法的实现。
CelerityRun(int left,int right,int array[])
{
int i,j;
int middle;
int temp;
i = left;
j = right;
middle = array[((right - left) >> 1) + left]; //实际这里的middle可以取左右边界内任意的一个值
do
{
while((array[i] < middle) && (i < right))
{
i++;
}
while((array[j] > middle) && (j > left))
{
j--;
}
if(i<=j)
{
temp = array[i];
array[i] = array[j];
array[j] = array[i];
i++;
j--;
}
}while(i<=j)
if(left < j)
CelerityRun(left,j,array);
if(right > i)
CelerityRun(i,right,array);
}
在do while整个循环的过程中,middle的值是不变的
C语言中数组的排序算法——选择法、冒泡法、交换法、插入法、折半法
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/194157.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...