交换排序——冒泡排序

冒泡排序

第一趟冒泡将最大的数冒在最后，第二趟将次大的数冒上去，以此类推。

void BubbleSort(int *arr, int n) { int end = n - 1; while (end > 0) { bool flag = false; //此处定义flag，若发生交换，则flag置为true。上一趟没有发生交换，意味着已经有序，无需再进行下一趟交换 for (int i = 0; i < n - 1; ++i) { if (arr[i]>arr[i + 1]) { swap(arr[i], arr[i + 1]); flag = true; } } if (!flag) { break; } --end; } }

冒泡排序的时间复杂度：O(N^2)[最好情况：O(N) 最坏情况：O(N^2)] 空间复杂度：O(1) 冒泡排序是一种稳定的排序算法。