Your bubble sort examples for O(n) and O(n log n) are the same (the first needs to be un-optimized). Also, I believe the optimized bubble sort is O(n²/2), not O(n log n).

For your second suggestion, loops that can break out early are still O(n) in the worst case, as no guarantee can be made that all other elements will not be considered before the target element.