C语言|排序问题一、排序问题

65 阅读 0 评论 43 点赞

我是靠谱客的博主犹豫大雁，这篇文章主要介绍C语言|排序问题一、排序问题，现在分享给大家，希望可以做个参考。

这篇文章主要和大家分享三种基础的排序算法——冒泡排序、选择排序、快速排序

一、排序问题

1.冒泡排序

冒泡排序的主要思想是通过两两相邻的元素进行比较，通过元素的大小决定是否交换。一趟冒泡排序的结果是一定有一个最大数会排到最后一个元素；因此对n个数进行排序，需要进行n-1躺冒泡排序。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void bubble_sort(int arr[],int x)//注意形参arr传递的是地址
int i=0;
for(i=0;i<sz-1;i++)//冒泡排序的趟数
{
int j=0;
int float=1;//如果float的值没有发生改变，说明上一躺的冒泡排序就达到了结果
for(j=0;j<sz-1-i;j++)//最后i个数的顺序已经排好，使用只需要排余下的sz-1-i个数
{
if(arr[j]>arr[j+1])
{
int tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
float=0;
}
//进行一次冒泡排序
if(float==1)
break;
}
}
int main()
{
int arr[]={9,8,7,6,5,4,3,2,1,0};
int sz=sizeof(arr)/sizeof(arr[0]);
bubble_sort(arr，sz);
return 0;
}

2.选择排序

选择排序的主要思路是：先从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的元素的个数为零。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main()
{
int j=0;
int i=0;
int tmp=0;
int k;
int arr[]={4,5,6,72,1,7,9,3}
int sz=sizeof(arr)/sizeof(arr[0])-1;
for(i=0;i<=sz;i++)
{
k=i;
for(j=i+1;j<=sz;j++)
{
if(arr[j]>arr[k])
{
k=j;
}//找到最大的数的下标
}
if(k!=i)
{
tmp=arr[k];
arr[k]=arr[i];
arr[i]=tmp;//交换数值
}
}
for(i=;i<=sz;i++)
{
printf("%d",arr[i]);
}
return 0;
}

3.快速排序

快速排序的思路：选择一个关键数据（一般选择第一个）。然后先从左到右，直到找到第一个大于关键数据的数，并把这个数放在关键数据的后面。然后从右到左，直到找到第一个小于关键数据的数，并放在关键数据的前面。直到把所有比关键数据大的数都放在它的后面，把所有比关键数据小的数放在它的前面，这为一次快速排序；然后对关键数据左边和右边的数组分别再进行同样的操作......反复进行，每次选择合适的关键数据，最后就可以得到一个从小到大的排序；

初始数组：

第一次排序，以3为关键数据，把数组分为大于3和小于3的两部分。

第二次排序，左边以2为关键数据，右边以5为关键数据

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#incldue<string.h>
void fast(int left;int right)//left,right分别是数组的第一个元素的索引和最后一个元素的索引
{
if(left>=right)//已经排序完成
{
return 0;
}
int i=left;
int j=right;
int key=arr[i];//关键数据
while(i<j)//i>j说明排序完成
{
while(i<j)
{
if(arr[j]>=key)
j--;//从最后往前寻找小于key的数
else
{
arr[i]=arr[j];
break;
}
}
while(i<j&&key>=arr[i])
i++;
arr[j]=arr[i];
}
arr[i]=key;
fast(left,i-1);
fast(i+1,right);
}