冒泡排序
冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)操漠。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端浊伙。
冒泡排序還有一種優(yōu)化算法撞秋，就是立一個(gè) flag，當(dāng)在一趟序列遍歷中元素沒(méi)有發(fā)生交換嚣鄙，則證明該序列已經(jīng)有序吻贿。但這種改進(jìn)對(duì)于提升性能來(lái)說(shuō)并沒(méi)有什么太大作用。
1. 算法步驟
- 比較相鄰的元素哑子。如果第一個(gè)比第二個(gè)大舅列，就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素作同樣的工作卧蜓，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)帐要。這步做完后，最后的元素會(huì)是最大的數(shù)弥奸。
- 針對(duì)所有的元素重復(fù)以上的步驟榨惠，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟盛霎，直到?jīng)]有任何一對(duì)數(shù)字需要比較赠橙。
bubbleSort.gif
2.代碼
#include <stdio.h>
void
swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void
bubble_sort(int arr[], int len)
{
int i, j, temp;
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
int
main()
{
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = (int) sizeof(arr) / sizeof(*arr);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
轉(zhuǎn)載于菜鳥(niǎo)教程
2020.10.19 14:40 深圳
