冒泡排序基本介绍
冒泡排序（Bubble Sorting）：是一种计算机科学领域的较简单的排序算法。它的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）, 依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。故名“冒泡排序”。
冒泡排序原理
- 外层循环 0到n-1 //控制比较轮数 n 表示元素的个数
- 内层循环 0到n-i-1 //控制每一轮比较次数
- 两两比较做交换
第一次找到一个最大的，在剩下的数据中找到最大的
对于一组N个元素数据，每次从待排数据中 比较相邻元素中交换最大数值，最大值最终移到后部
代码
//冒泡排序
void bubble_sort(int *array, int length){
int times = 0;
int temp;
for (int i = 0; i< length; i++) {
int flag = 0;
for (int j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = 1;
}
times++;
}
if (flag == 0) {
break;
}
}
printf("\n排序后：");
for (int i = 0; i< length; i++) {
printf("%d ", array[i]);
}
printf("冒泡执行了：%d", times);
}
冒泡排序的优化（1）
- 一共进行数组的大小-1 次大的循环
- 每一趟排序的次数在逐渐的减少
- 在冒泡排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是
优化
冒泡排序优化（2）-双向冒泡排序（鸡尾酒排序）
上面的代码已经进行过优化，加了排序中，没有发生一次交换，提前结束冒泡排序的标识flag。
- 1、正常的冒泡排序
- 2、在第一轮排序结束后，从后往前排除最小数
- 3、最终就是排好的数据
void doubleBubble_sort(int *array, int lenght) {
int times = 0;
int temp;
for (int i = 0; i < lenght/2; i++) {
int flag = 0;
for (int j = 0; j < lenght - i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = 1;
}
times ++;
}
if (flag == 0) {
break;
}
for (int j = lenght - i - 1; j > i; j--) {
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
flag = 1;
}
times ++;
}
if (flag == 0) {
break;
}
}
printf("\n排序后：");
for (int i = 0; i< lenght; i++) {
printf("%d ", array[i]);
}
printf("双向冒泡执行了：%d", times);
}
选择排序
工作原理是：
- 1、第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，
- 2、然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
- 3、以此类推，直到全部待排序的数据元素的个数为零。
代码
//选择排序
void select_sort(int *array, int length) {
int temp;
for (int i = 0; i< length - 1; i++) {
for (int j = i + 1; j <length; j++) {
if (array[i] > array[j]) {
temp = array[i];
array[j] = array[j];
array[j] = temp;
}
}
}
printf("\n排序后：");
for (int i = 0; i< length; i++) {
printf("%d ", array[i]);
}
}
