LeetCode_CC150
  • Introduction
  • LeetCode
    • Single Number
    • Contains Duplicate
    • Happy Number
    • Valid Anagram
    • Contains Duplicate II
    • Count Primes
    • Isomorphic Strings
    • Word Pattern
    • Island Perimeter
    • Find the Difference
    • Palindrome Permutation
    • Two Sum III - Data structure design
    • Number of Boomerangs
    • Longest Palindrome
    • Logger Rate Limiter
    • Find All Anagrams in a String
    • Keyboard Row
    • Distribute Candies
    • Shortest Word Distance
    • Majority Element
    • Plus One
    • Best Time to Buy and Sell Stock
    • Best Time to Buy and Sell Stock II
    • Pascal's Triangle
    • Remove Element
    • Rotate Array
    • Pascal's Triangle II
    • Two Sum II - Input array is sorted
    • Third Maximum Number
    • Max Consecutive Ones
    • K-diff Pairs in an Array
    • Maximum Product of Three Numbers
    • Maximum Distance in Arrays
    • Shortest Unsorted Continuous Subarray
    • Roman to Integer
    • Count and Say
    • Valid Parentheses
    • Longest Common Prefix
    • Valid Palindrome
    • Length of Last Word
    • Repeated Substring Pattern
    • Number of Segments in a String
    • Valid Word Abbreviation
    • Longest Uncommon Subsequence I
    • Student Attendance Record I
    • Reverse Words in a String III
    • Arranging Coins
    • Guess Number Higher or Lower
    • Search Insert Position
    • Min Stack
    • Diameter of Binary Tree
    • Unique Binary Search Trees
    • Unique Binary Search Trees II
    • Binary Tree Zigzag Level Order Traversal
    • Nim Game
    • Add Digits
    • Fizz Buzz
    • Climbing Stairs
    • Array Partition I
    • Power of Three
    • Power of Four
    • Power of Two
    • Ugly Number
    • Find All Numbers Disappeared in an Array
    • Find All Duplicates in an Array
    • Minimum Moves to Equal Array Elements
    • Meeting Rooms
    • Subsets
    • Subsets II
    • Count Complete Tree Nodes
    • Minimum Size Subarray Sum
    • Maximum Size Subarray Sum Equals k
    • Sparse Matrix Multiplication
    • Meeting Rooms II
    • Letter Combinations of a Phone Number
    • Binary Tree Vertical Order Traversal
    • Find the Celebrity
    • Merge Intervals
    • One Edit Distance
    • Multiply Strings
  • Array&String
    • Subarray Sum
    • Maximum Subarray
    • Intersection of Two Arrays
    • Intersection of Two Arrays II
    • Partition List
    • Merge Sorted Array
    • Two Sum
    • 3Sum
    • Product of Array Except Self
    • Rotate Image
    • Spiral Matrix
  • Linked List
    • Merge Two Sorted Lists
    • Insert into a Cyclic Sorted List
    • Sort List
    • Linked List Cycle
    • Copy List with Random Pointer
    • Add Two Numbers
    • Delete Node in a Linked List
    • Reverse Linked List
    • Odd Even Linked List
    • Intersection of Two Linked Lists
    • Palindrome Linked List
    • Insertion Sort List
    • Remove Linked List Elements
    • Remove Duplicates from Sorted List
    • Swap Nodes in Pairs
    • Remove Nth Node From End of List
  • Binary Search
    • Missing Number
    • Valid Perfect Square
    • 744. Find Smallest Letter Greater Than Target
    • Sqrt(x)
    • First Bad Version
    • Pow(x, n)
    • Find the Duplicate Number
    • Find Minimum in Rotated Sorted Array
    • Find Minimum in Rotated Sorted Array II
    • Total Occurrence of Target
    • Search in a Big Sorted Array
    • Longest Increasing Subsequence
    • Find Peak Element
    • Search in Rotated Sorted Array
    • Search a 2D Matrix
    • Search a 2D Matrix II
    • Closest Number in Sorted Array
    • Search in Rotated Sorted Array II
    • Search for a Range
    • Maximum Number in Mountain Sequence
    • Last Position of Target
    • K Closest Numbers In Sorted Array
    • Sqrt(x) II
  • Binary Tree
    • Maximum Depth of Binary Tree
    • Invert Binary Tree
    • Same Tree
    • Binary Tree Paths
    • Lowest Common Ancestor of a Binary Search Tree
    • Balanced Binary Tree
    • Convert Sorted Array to Binary Search Tree
    • Symmetric Tree
    • Path Sum
    • Minimum Depth of Binary Tree
    • Binary Tree Preorder Traversal
    • Binary Tree Inorder Traversal
    • Binary Tree Level Order Traversal
    • Binary Tree Level Order Traversal II
    • Minimum Subtree
    • Flatten Binary Tree to Linked List
    • Binary Tree Longest Consecutive Sequence
    • Subtree with Maximum Average
    • Number of Islands
    • Serialize and Deserialize Binary Tree
    • Clone Graph
  • Data Structure
    • Hash Table
    • Bubble Sort
    • Selection Sort
    • Binary Search
    • Merge Sort
    • Binary Tree
    • 递归
    • DFS BFS
    • python技巧
  • two pointers
    • Reverse Vowels of a String
    • Reverse String
    • Remove Duplicates from Sorted Array
    • LeetCode 11. Container With Most Water
    • Strobogrammatic Number
    • Move Zeroes
    • Implement strStr()
  • 哈希表
    • Ransom Note
    • Minimum Index Sum of Two Lists
    • Longest Harmonious Subsequence
    • Untitled
Powered by GitBook
On this page
  • 复杂度分析
  • Reference
  • https://einsqiang.gitbooks.io/python-algorithm/content/basics_sorting/bubble_sort.html

Was this helpful?

  1. Data Structure

Bubble Sort

PreviousHash TableNextSelection Sort

Last updated 5 years ago

Was this helpful?

Start at the beginning of the array and swap the first two elements if the first is greater than the second. Then we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.

核心：冒泡，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。

冒泡排序对个项目需要()的比较次数，且可以排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤，除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

复杂度分析

平均情况与最坏情况均为 O\(n^2\), 使用了 temp 作为临时交换变量，空间复杂度为 O\(1\).+

Reference

O
原地
https://einsqiang.gitbooks.io/python-algorithm/content/basics_sorting/bubble_sort.html
n^{2}
n