Bubble Sort - 冒泡排序

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

... 冒泡排序- 维基百科，自由的百科全书 ... Preface FAQ GuidelinesforContributing PartI-Basics BasicsDataStructure String LinkedList BinaryTree HuffmanCompression Queue Heap Stack Set Map Graph BasicsSorting BubbleSort SelectionSort InsertionSort MergeSort QuickSort HeapSort BucketSort CountingSort RadixSort BasicsAlgorithm DivideandConquer BinarySearch Math GreatestCommonDivisor Prime Knapsack Probability Shuffle Bitmap BasicsMisc BitManipulation PartII-Coding String ImplementstrStr TwoStringsAreAnagrams CompareStrings GroupAnagrams LongestCommonSubstring RotateString ReverseWordsinaString ValidPalindrome LongestPalindromicSubstring SpaceReplacement WildcardMatching LengthofLastWord CountandSay IntegerArray RemoveElement ZeroSumSubarray SubarraySumK SubarraySumClosest RecoverRotatedSortedArray ProductofArrayExcludeItself PartitionArray FirstMissingPositive 2Sum 3Sum 3SumClosest RemoveDuplicatesfromSortedArray RemoveDuplicatesfromSortedArrayII MergeSortedArray MergeSortedArrayII Median PartitionArraybyOddandEven KthLargestElement BinarySearch FirstPositionofTarget SearchInsertPosition SearchforaRange FirstBadVersion Searcha2DMatrix Searcha2DMatrixII FindPeakElement SearchinRotatedSortedArray SearchinRotatedSortedArrayII FindMinimuminRotatedSortedArray FindMinimuminRotatedSortedArrayII MedianoftwoSortedArrays Sqrtx WoodCut MathandBitManipulation SingleNumber SingleNumberII SingleNumberIII O1CheckPowerof2 ConvertIntegerAtoIntegerB FactorialTrailingZeroes UniqueBinarySearchTrees UpdateBits FastPower HashFunction HappyNumber Count1inBinary Fibonacci AplusBProblem PrintNumbersbyRecursion MajorityNumber MajorityNumberII MajorityNumberIII DigitCounts UglyNumber PlusOne PalindromeNumber TaskScheduler LinkedList RemoveDuplicatesfromSortedList RemoveDuplicatesfromSortedListII RemoveDuplicatesfromUnsortedList PartitionList AddTwoNumbers TwoListsSumAdvanced RemoveNthNodeFromEndofList LinkedListCycle LinkedListCycleII ReverseLinkedList ReverseLinkedListII MergeTwoSortedLists MergekSortedLists ReorderList CopyListwithRandomPointer SortList InsertionSortList PalindromeLinkedList LRUCache RotateList SwapNodesinPairs RemoveLinkedListElements BinaryTree BinaryTreePreorderTraversal BinaryTreeInorderTraversal BinaryTreePostorderTraversal BinaryTreeLevelOrderTraversal BinaryTreeLevelOrderTraversalII MaximumDepthofBinaryTree BalancedBinaryTree BinaryTreeMaximumPathSum LowestCommonAncestor InvertBinaryTree DiameterofaBinaryTree ConstructBinaryTreefromPreorderandInorderTraversal ConstructBinaryTreefromInorderandPostorderTraversal Subtree BinaryTreeZigzagLevelOrderTraversal BinaryTreeSerialization BinarySearchTree InsertNodeinaBinarySearchTree MinimumAbsoluteDifferenceinBST ValidateBinarySearchTree SearchRangeinBinarySearchTree ConvertSortedArraytoBinarySearchTree ConvertSortedListtoBinarySearchTree BinarySearchTreeIterator ExhaustiveSearch Subsets UniqueSubsets Permutations UniquePermutations NextPermutation PreviousPermuation PermutationIndex PermutationIndexII PermutationSequence UniqueBinarySearchTreesII PalindromePartitioning Combinations CombinationSum CombinationSumII MinimumDepthofBinaryTree WordSearch DynamicProgramming Triangle Backpack BackpackII MinimumPathSum UniquePaths UniquePathsII ClimbingStairs JumpGame WordBreak LongestIncreasingSubsequence PalindromePartitioningII LongestCommonSubsequence EditDistance JumpGameII BestTimetoBuyandSellStock BestTimetoBuyandSellStockII BestTimetoBuyandSellStockIII BestTimetoBuyandSellStockIV DistinctSubsequences InterleavingString MaximumSubarray MaximumSubarrayII LongestIncreasingContinuoussubsequence LongestIncreasingContinuoussubsequenceII MaximalSquare Graph FindtheConnectedComponentintheUndirectedGraph RouteBetweenTwoNodesinGraph TopologicalSorting WordLadder BipartialGraphPartI DataStructure ImplementQueuebyTwoStacks MinStack SlidingWindowMaximum LongestWords Heapify BigData TopKFrequentWords(MapReduce) TopKFrequentWords TopKFrequentWordsII KClosestPoints TopkLargestNumbers TopkLargestNumbersII ProblemMisc NutsandBoltsProblem StringtoInteger InsertInterval MergeIntervals MinimumSubarray MatrixZigzagTraversal ValidSudoku AddBinary ReverseInteger GrayCode FindtheMissingNumber MinimumWindowSubstring ContinuousSubarraySum ContinuousSubarraySumII LongestConsecutiveSequence PartIII-Contest GoogleAPAC APAC2015RoundB ProblemA.PasswordAttacker APAC2016RoundD ProblemA.DynamicGrid Microsoft Microsoft2015April ProblemA.MagicBox ProblemB.ProfessorQ'sSoftware ProblemC.IslandsTravel ProblemD.Recruitment Microsoft2015April2 ProblemA.LuckySubstrings ProblemB.NumericKeypad ProblemC.SpringOuting Microsoft2015September2 ProblemA.FarthestPoint AppendixIInterviewandResume Interview Resume Tags 本书使用GitBook发布 BubbleSort BubbleSort-冒泡排序 Implementation Python Java 复杂度分析 Reference 核心：冒泡，持续比较相邻元素，大的挪到后面，因此大的会逐步往后挪，故称之为冒泡。

Implementation Python #!/usr/bin/envpython defbubbleSort(alist): foriinxrange(len(alist)): print(alist) forjinxrange(1,len(alist)-i): ifalist[j-1]>alist[j]: alist[j-1],alist[j]=alist[j],alist[j-1] returnalist unsorted_list=[6,5,3,1,8,7,2,4] print(bubbleSort(unsorted_list)) Java publicclassSort{ publicstaticvoidmain(String[]args){ int[]unsortedArray=newint[]{6,5,3,1,8,7,2,4}; bubbleSort(unsortedArray); System.out.println("Aftersort:"); for(intitem:unsortedArray){ System.out.print(item+""); } } publicstaticvoidbubbleSort(int[]nums){ intlen=nums.length; for(inti=0;inums[j]){ inttemp=nums[j-1]; nums[j-1]=nums[j]; nums[j]=temp; } } } } } 复杂度分析 平均情况与最坏情况均为O(n2)O(n^2)O(n​2​​),使用了temp作为临时交换变量，空间复杂度为O(1)O(1)O(1). Reference 冒泡排序-维基百科，自由的百科全书 resultsmatching"" poweredby Noresultsmatching""