目录
一、冒泡排序
1.冒泡排序的原理
2.实现冒泡排序
1.交换函数
通过原理的讲解不难看出，冒泡排序要实现多次的交换，因此我们可以写一个简单的交换函数
void Swap(int* x, int* y)
{
int tmp = *x;
//创建中间变量储存x
*x = *y;
*y = tmp;
}2.单躺排序
void BobbleSort(int* arr, int n)
//传递数组和数组元素个数
{
int j = 0;
for (j = 0; j < n - 1; j++)
//j<n-1避免越界
{
if (arr[j] > arr[j + 1])
//不断地进行比较，一遇到大的就进行交换，会将最大的数移动到数组的最后
{
Swap(&arr[j + 1], &arr[j]);
}
}
}3.冒泡排序实现
一趟排好一个数，那么我们一共有n个数，那么循环次数就可以修改成n次
void BobbleSort(int*arr,int n)
//传递数组和数组元素个数
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++)
//n次排序排n个数
{
for (j = 0; j < n - 1; j++)
//j<n-1避免越界
{
if (arr[j] > arr[j + 1])
//不断地进行比较，一遇到大的就进行交换，会将最大的数移动到数组的最后
{
Swap(&arr[j + 1], &arr[j]);
}
}
}
}4.测试
int main()
{
int arr[] = { 9,6,7,5,2,3,4,1,8};
int size = sizeof(arr) / sizeof(arr[0]);
BobbleSort(arr,size);
int i = 0;
for (i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}5.升级冒泡排序
6.升级版代码
void BobbleSort(int*arr,int n)
//传递数组和数组元素个数
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++)
//n次排序排n个数
{
int flaw = 1;
for (j = 0; j < n -i- 1; j++)
//j<n-1避免越界
{
if (arr[j] > arr[j + 1])
//不断地进行比较，一遇到大的就进行交换，会将最大的数移动到数组的最后
{
Swap(&arr[j + 1], &arr[j]);
flaw = 0;
}
}
if (flaw == 1)
{
return;
}
}
}7.升级版测试
二、选择排序
1.选择排序的原理
2.实现选择排序
1.单躺排序
第一趟排序我们找到最大值和最小值然后把它们放在对应的位置即可
void SelectSort(int*arr,int n)
{
int max = 0;
int min = 0;
//max和min均储存下标
int i = 0;
for (i = 0; i < n; i++)
{
if (arr[max] < arr[i])
{
max = i;
}
if (arr[min] > arr[i])
{
min = i;
}
}
Swap(&arr[0] = &arr[min]);
//将最小值放到最前面
Swap(&arr[n-1],&arr[max]);
//将最大值放到最后
}2.选择排序实现
void SelectSort(int* arr, int n)
{
int i = 0; int j = 0;
for (j = 0; j < n / 2; j++)
{
int max = j; int min = j;
//max和min均储存下标
for (i = j; i < n - j; i++)
{
if (arr[max] < arr[i])
{
max = i;
}
if (arr[min] > arr[i])
{
min = i;
}
}
Swap(&arr[j], &arr[min]);
//将最小值放到最前面
Swap(&arr[n - 1 - j], &arr[max]);
//将最大值放到最后
}
}3.测试
![冒泡排序和选择排序-LMLPHP]( "冒泡排序和选择排序-LMLPHP")
4.修改
为什么会出错呢，仔细思考，你会发现，若是max和j相等的话，j先和min进行交换，那么此时的j就不再是最大值的下标了，自然会出错，因此，当max和j相等的时候，应该在交换之后使max更新为min，更新到真正最大值的下标。
void SelectSort(int* arr, int n)
{
int i = 0; int j = 0;
for (j = 0; j <n / 2; j++)
{
int max = j; int min = j;
//max和min均储存下标
for (i = j; i < n-j; i++)
{
if (arr[max] < arr[i])
{
max = i;
}
if (arr[min] > arr[i])
{
min = i;
}
}
Swap(&arr[j], &arr[min]);
//将最小值放到最前面
if (j == max)
//更新
{
max = min;
}
Swap(&arr[n - 1 - j], &arr[max]);
//将最大值放到最后
}
}5.测试
至此，冒泡排序和选择排序讲解完成，感谢各位友友的来访，祝各位友友前程似锦O(∩_∩)O