冒泡排序

老码农空杯修行记 2020-09-05

737

算法原理

从底部元素开始，每次一个向上冒，冒的过程中与上面的元素相遇，相遇时比较，若满足某一个条件就交换，不满足就不交换，无论是否交换，最终这两个元素中上面的元素继续沿着这个思路向上冒，每次冒完之后顶部最大或最小；接下来排除最顶部的这个元素，在剩下的区间内继续冒。

要点

两层循环，外层循环 索引 i 表示冒几轮泡，内层循环 索引 j 用来管理每轮冒泡的区间，并且每轮冒泡都是从最底下开始，得出两个索引取值区间

i ∈ [0, n-1)


# -1 当前元素和后一个元素比较，
# 若不排除最后一个，会越界
j ∈ [0, n-i-1)

时间复杂度

n²

推演

待排序列

5, 8, 2, 9, 6

要求：从小到大，按照升序排列
总计 4 轮冒泡
排序：上部待比较元素(黄色)、冒泡元素(红色)、已排序(绿色)、未排序元素(灰色)

第一轮冒泡：i=0，j ∈ [0，4)，5 开始向上冒，遇到 8，5 > 8 不成立，不交换，8 向上冒，遇到 2，8 > 2 成立，交换位置，8 接着向上冒，以此类推得出第一轮冒泡结果

第二轮冒泡：i=1，j ∈ [0，3)，绿色部分已排好序，不参与冒泡，从底部5 开始按照第一轮的逻辑向上冒

第三轮冒泡：i=2，j ∈ [0，2)，绿色部分已排好序，不参与冒泡，从底部 2 开始按照第一轮的逻辑向上冒

第四轮冒泡：i=3，j ∈ [0，1)，绿色部分已排好序，不参与冒泡，从底部 2 开始按照第一轮的逻辑向上冒

第5轮：i=4， 超出区间，即冒泡完毕，到此整个序列有序

代码演示

// 
// golang language
// 
func BubbleSort(bubbles []int) {
  size := len(bubbles)


  // 冒泡轮次
    bubbleCircle := size - 1


  for i:=0; i<bubbleCircle; i++ {


    // 冒泡区间
    bubbleRange := size - i - 1


    for j:=0; j<bubbleRange; j++ {
      // 决定下一个继续向上冒的元素
      if bubbles[j] > bubbles[j+1] {
        bubbles[j], bubbles[j+1] = bubbles[j+1], bubbles[j]
      }
    }
  }
}

# 
# python language
# 
def bubble_sort(bubbles):
    size
    
    # 冒泡轮次
    bubble_circle = size - 1


    for i in range(bubble_circle):
        # 冒泡区间
        bubble_range
        
        for j in range(bubble_range):
            # 比较决定下一个冒泡的元素
            if bubbles[j] > bubbles[j+1]:
                bubbles[j], bubbles[j+1] = bubbles[j+1], bubbles[j]

// 
// c/c++ language
//


// 比较函数接口
typedef void (*swap_t)(void*, size_t i, size_t j);


// 比较函数实现
bool compare(void *d, size_t i, size_t j) {
    int *arr = (int*)d;
    return arr[i] < arr[j];
}


// 交换元素接口
typedef void (*swap_t)(void*, size_t i, size_t j);


// 交换元素实现
void swap(void *d, size_t i, size_t j) {
    int *arr = (int*)d;
    if (arr[i] == arr[j]) {
        return;
    }


    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}




template <class T, int size>
void Sort<T, size>::bubble_sort(T *data) {
    for (int i=size-1; i>0; i--) {
        for (int j=0; j<i; j++) {
            if (this->compare_(data, j, j+1)) {
                this->swap_(data, j, j+1);
            }
        }
    }
}

‍

数据库

文章转载自老码农空杯修行记，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

冒泡排序

评论