算法分享-冒泡、插入、选择排序

冒泡、插入、选择排序（C语言）

以下排序算法默认从小到大的升序排序。

冒泡排序

思路

从数组的第一个数a[0]开始，向后遍历，每次比较a[i]和a[i+1]的值

若a[i]大于a[i+1]，就交换两个位置的数的值。

重复上述1和2的操作至a[n-2]。

优化

第三部改为重复上述操作直至不再出现值的交换。（若一次遍历没有值得交换，说明该数组从左到右是升序）

代码

voidbubbleSort(inta[],intn)

{

if(n

return;

for(inti=;i

{

intflag=;

for(intj=;j

{

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

{

inttemp=a[j];

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

a[j+1]=temp;

flag=1;

}

}

if(!flag)

break;

}

}

插入排序

思路讲解

所谓插入排序，就是把a[1]值插入到a[0]中，然后a[2]插入到a[0]--a[1]的数组中，依次向后遍历，直至将a[n-1]插入到a[0] -- a[n-2]的数组中。

保存a[i]的值，因为a[0]到a[i-1]已经使用插入排序排好序了，此时从后往前数值依次变小，判断a[i-1],a[i-2]...等等数中，小于a[i]的值，将a[i]插入该数位置之后。

思路

先用num保存a[i]的值，每次执行插入操作时，判断a[i]与a[i-k]的值的大小，（k从1到i）

若a[i]小于a[i-1]，将a[i]的值后移一位到a[i+1]的位置，然后继续比较a[i]与a[i-2]的值.

若a[i]大于a[i-k]，则直接退出

循环2和3步骤

将a[i]的值插入a[i+1]的位置

图解

代码

voidbubbleSort(inta[],intn)

{

if(n

return;

for(inti=;i

{

intflag=;

for(intj=;j

{

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

{

inttemp=a[j];

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

a[j+1]=temp;

flag=1;

}

}

if(!flag)

break;

}

}

选择排序

思路

选择排序最好理解

将数组的第一个数a[0]与其他数a[1]到a[n-1]做比较

如果小于a[0]就和a[0]交换。这样，一次的循环就可以把数组最小的数放在a[0].

再一次遍历a[1]到a[n-1]。

代码

// 插入排序，a 表示数组，n 表示数组大小

voidinsertionSort(inta[],intn)

{

if(n

return;

for(inti=1;i

{

intvalue=a[i];

intj;

for(j=i-1;j>=;j--)

{

if(value

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

else

break;

}

a[j+1]=value;

}

}

总代码

#include

#include

//函数声明

voidinitArray(inta[],intn);

voidprintArray(inta[],intn);

voidbubbleSort(inta[],intn);

voidinsertionSort(inta[],intn);

voidchoose(inta[],intn);

intmain()

{

inta[5];

//冒泡排序

initArray(a,5);

printf("原数组：");

printArray(a,5);

bubbleSort(a,5);

printf("冒泡排序后数组：");

printArray(a,5);

//插入排序

initArray(a,5);

printf("原数组：");

printArray(a,5);

insertionSort(a,5);

printf("插入排序后数组：");

printArray(a,5);

//选择排序

initArray(a,5);

printf("原数组：");

printArray(a,5);

choose(a,5);

printf("选择排序后数组：");

printArray(a,5);

return;

}

voidinitArray(inta[],intn)

{

for(inti=;i

a[i]=rand()%100+10;

}

//数组输出函数

voidprintArray(inta[],intn)

{

for(inti=;i

{

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

}

printf("\n");

}

// 冒泡排序，a 表示数组，n 表示数组大小

voidbubbleSort(inta[],intn)

{

if(n

return;

for(inti=;i

{

intflag=;

for(intj=;j

{

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

{

inttemp=a[j];

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

a[j+1]=temp;

flag=1;

}

}

if(!flag)

break;

}

}

// 插入排序，a 表示数组，n 表示数组大小

voidinsertionSort(inta[],intn)

{

if(n

return;

for(inti=1;i

{

intvalue=a[i];

intj;

for(j=i-1;j>=;j--)

{

if(value

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

else

break;

}

a[j+1]=value;

}

}

// 选择排序，a 表示数组，n 表示数组大小

voidchoose(inta[],intn)

{

for(inti=;i

{

for(intj=i+1;j

{

if(a[i]>a[j])

{

inttemp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

}

以上就是全部内容！！！

Over