关于冒泡排序看这篇就够了!
简介
冒泡排序(bubble sort)是基于交换的排序，在执行过程序中元素一个一个往后移动，就好像水中气泡一个一个向上冒一样，由此而得名
冒泡排序
void bobble_sort(int *array, int length)
{
for (int i = 0; i < length-1; ++i) {
for (int j = 0; j < length - i - 1; ++j) {
if (array[j] > array[j+1]) {
int swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
}
}
}
}
冒泡排序V2
对于排序来说，如果元素已经是有序的情况完全可以结束排序
void bobble_sort2(int *array, int length)
{
for (int i = 0; i < length-1; ++i) {
bool isSorted = true;
for (int j = 0; j < length - i - 1; ++j) {
if (array[j] > array[j+1]) {
int swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
冒泡排序V3
在对第一层循环优化的情况下，如果我们想要在提升算法性能就需要对第三层动手，这次引入sortBorder变量来标识需要排序的元素范围，从而跳过有序元素
void bobble_sort3(int *array, int length)
{
int sortBorder = length - 1;
for (int i = 0; i < length-1; ++i) {
bool isSorted = true;
int sortBorderTmp = 0;
for (int j = 0; j < sortBorder; ++j) {
if (array[j] > array[j+1]) {
int swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
isSorted = false;
sortBorderTmp = j;
}
}
sortBorder = sortBorderTmp;
if (isSorted) {
break;
}
}
}
鸡尾酒排序
从复杂度来看鸡尾酒排序跟v3版本没什么区别，只是多了个好听的名字
void cocktail_sort(int *array, int length)
{
int swap = 0;
for (int i = 0; i < length / 2; ++i) {
// 奇数轮
bool isSorted = true;
for (int j = i; j < length-1; ++j) {
if (array[j] > array[j+1]) {
swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
isSorted = false;
}
}
if (isSorted) {
break;
}
// 偶数轮
isSorted = true;
for (int j = length-i-1; j > i; j--) {
if (array[j]<array[j-1]) {
swap = array[j];
array[j-1] = array[j];
array[j] = swap;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}