冒泡排序的基本思想

我不是女神ヾ 2022-01-21 03:11 248阅读 0赞

1．冒泡排序的基本思想 冒泡排序是交换排序中一种简单的排序方法。

它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a\[j\]>a\[j+1\]），则将其交换，最终达到有序化;

其处理过程为：

（1）将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。

（2）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序将其交换，从而使得关键字值小的记录向上”飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。 每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。

2．原始的冒泡排序算法 对由n个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为 有序序列，第一趟定位第n个记录，此时有序区只有一个记录；第二趟定位第n-1个记录，此时有序区有两个记录；以此类推，算法框架为： for（i=n；i>1；i—） \{ 定位第i个记录； \}

下面给出完整的冒泡排序算法：
     
    for (i=n;i>1；i--） {
     
    		for (j=1;j<=i-1;j++) {
     
    				if（a[j].key>a.[j+1].key） {
     
    							temp=a[j];
     
              					 a[j]=a[j+1];
     
                 				a[j+1]=temp;
           			 }
        		}
     }

附加段python的冒泡排序
    def bubble_sort(origin_items, comp=lambda x, y: x > y):
        """高质量冒泡排序(搅拌排序)"""
        items = origin_items[:]
        for i in range(len(items) - 1):
            swapped = False
            for j in range(i, len(items) - 1 - i):
                if comp(items[j], items[j + 1]):
                    items[j], items[j + 1] = items[j + 1], items[j]
                    swapped = True
            if swapped:
                swapped = False
                for j in range(len(items) - 2 - i, i, -1):
                    if comp(items[j - 1], items[j]):
                        items[j], items[j - 1] = items[j - 1], items[j]
                        swapped = True
            if not swapped:
                break
        return items

地址映射：[https://blog.csdn.net/ldqchat/article/details/79513191][https_blog.csdn.net_ldqchat_article_details_79513191]

[https_blog.csdn.net_ldqchat_article_details_79513191]: https://blog.csdn.net/ldqchat/article/details/79513191