冒泡排序

最大的就沉下去，下一次忽略最后的

优化1：已经有序 用flag标记一下

优化2：后半截有序，不需要比较后面好的

稳定性 相同数位置不变

image.png

python （优化1）

def bubble_sort(arr):
    for i in range(1, len(arr)):
        flag = bool(1)
        for j in range(0,len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
                # 记录最后一次交换的位置
                
                flag = bool(0)
        if flag == 1:
            print("xiu")
            break
    return arr

Java(优化2)

    public int[] MySort (int[] array) {
        // write code here
        for(int end = array.length-1 ; end > 0 ; end--){
            # 记录最后一次交换的位置
            int sortedIndex = 1;
            for (int begin = 1 ; begin <= end ; begin++){
                if(array[begin] < array[begin - 1]){
                    int tmp = array[begin];
                    array[begin] = array[begin - 1];
                    array[begin - 1] = tmp;
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
        return array;
    }