排序之冒泡排序
冒泡排序
原始思想
bool bubble(int* arr, int lo, int hi)
{bool sorted = true;while (++lo < hi) {if (arr[lo - 1] > arr[lo]) {mySwap2(arr[lo - 1], arr[lo]);sorted = false;}}return sorted;
}
void bubbleSort(int* arr, int lo, int hi)
{while (!bubble(arr, lo, hi--));
}
[lo,hi),通过一个标志记录逆序的元素 ,该标志控制外层循环
改进
可以把原始数组看成无序的前缀和有序的后缀,一开始有序的后缀可能没有,为0,
在实际排序中可能会出现前缀有部分是有序的,不用进行排序,
int bubblePlus(int* arr, int lo, int hi)
{int last = lo;while (++lo < hi) {if (arr[lo - 1] > arr[lo]) {last = lo;mySwap2(arr[lo - 1], arr[lo]);}}return last;
}