冒泡排序

1：剖析排序算法的三个维度都是什么？答：执行效率（工夫、空间复杂度），内存耗费，算法稳定性 2：从算法执行效率这个维度登程从哪三个方面进行掂量？答：最好最坏和均匀复杂度、工夫复杂度系数、常数和低阶、比拟和替换、挪动次数。 3：原地排序是什么概念？答：排序时，除带排序元素组内部不占用额定的空间，即为原地排序。 4：什么事排序的稳定性、稳定性排序算法和不稳定性排序算法的区别在哪里？答：对于雷同元素，在排序前后地位不变，即为稳固算法。稳固与不稳固的区别在于雷同元素在排序前后的地位是否变动。 5：数组的满序度、有序度、逆序度概念是什么？如何计算？答：有序度是指有序元素的个数，逆序度是指反序元素对的个数，满序度是指在排序后续元素对的个数，两者之和就是满序度。 6：冒泡排序的实现思路是怎么样的，请实现冒泡排序算法？答：相邻元素进行比拟，有序则不替换，反序则替换，始终到最初一个元素，这样能够保障一个满足条件的元素被挪动到最终地位。下一轮从第二个元素开始，直到倒数第二个元素。代码：BubleSort.go package mainimport ( "fmt")func main() { var arr [5]int = [5]int{1,3,2,5,2} var arrLength = len(arr) for i:=0;i< arrLength;i++ { flag := false // 下一轮从第二个元素开始，直到倒数第二个元素 for j:=1;j<arrLength - 1 -i ;j++ { if(arr[j] > arr[j+1]) { arr[j],arr[j+1] = arr[j+1],arr[j] flag = true } } if(!flag) { break } } fmt.Println(arr)}7：冒泡排序的为什么是原地排序算法，为什么是稳固排序算法，最坏最好，均匀工夫复杂度各是多少？答：不占用额定空间。雷同元素比拟不替换则稳固，替换则不稳固。最好O(N),最坏O(n2),均匀O(N2) 8：插入排序的实现思路是怎么样的，请实现插入排序算法？答：将待排序元素组分成排序区和未排序区，将未排序区元素一次插入已排序区，并保障已排序区始终有序，晓得未排序区为空InsertSort.go package mainimport "fmt"func main() { arr := [5]int{5,4,3,2,1} arrLength := len(arr) for i:= 1;i< arrLength;i++ { tempValue := arr[i] j := i - 1 for ;j>=0;j-- { // 和曾经排序的做比拟 if(arr[j] > tempValue) { //右边大于左边 arr[j+1] = arr[j] // 则右移 } } arr[j+1] = tempValue } fmt.Println(arr)}9：插入排序为什么是原地排序算法，最好最坏，均匀复杂度各是多少？答：未应用额定空间排序。最好O(n),均匀O(n2) ...

冒泡排序（Bubble Sort）类型：交换排序时间复杂度（最坏）：O(n^2)时间复杂度（最好）：O(n)时间复杂度（平均）：O(n^2)空间复杂度：O(1)稳定性：稳定冒泡排序通过依次比较两个相邻元素的值，将数值较大的元素移动至数列尾部，每一轮的比较都能将无序数列中的最大值元素选出并移动到队尾，循环执行便可将数列按由大到小的顺序排列出来。因值大于才会发生交换，故为稳定排序。package mainimport ( “fmt”)func main() { var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8} BubbleSort(arr) fmt.Print(“sorted: “, arr)}// 冒泡排序func BubbleSort(arr []int) { length := len(arr) alreadyOrdered := true // 记录某次排序是否发生元素交换 // 最多需要 length-1 次外循环 for i := 0; i < length-1; i++ { // length-i 为待排序数列的长度 i 为有序数列的长度 for j := 0; j < (length-i)-1; j++ { if arr[j] > arr[j+1] { alreadyOrdered = false temp := arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } // 如果某次排序没有发生交换说明已有序 if alreadyOrdered { break } }} ...

导语冒泡排序是相对比较简单、常用的算法，同时在面试中也是最常被问到的问题。自认能力不够，不能有更深的理解，下面就把一些资料中的内容记录下来，文末有原文链接。冒泡排序冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序对 n 个项目需要 O(n2) 的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。以上是维基百科中的介绍，可以看到，原理并不复杂。但是在数据量大时，不是一个很好的选择。动图演示需要注意的是，下图与实例中的代码，顺序是相反的。实例<?php$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];function bubbleSort($arr){ if (!is_array($arr)) { return false; } $count = count($arr); if ($count < 2) { return $arr; } for ($i = 0; $i < $count; $i++) { for ($k = $i + 1; $k < $count; $k++) { // $arr[$i] 和 $arr[$k] 是相邻的两个值 if ($arr[$i] > $arr[$k]) { // 前者大于后者，调换位置 // 如果想要按照从大到小进行排序，改为 $arr[$i] < $arr[$k] $temp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $temp; } } } return $arr;}print_r(bubbleSort($arr));// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )参考资料：冒泡排序、PHP冒泡排序（Bubble Sort）算法详解、GIF演示排序算法。 ...

基本排序算法在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。这里简单的介绍三种最基本的排序，分别是：冒泡排序、选择排序以及插入排序排序的过程中，经常要用到交换元素位置，故抽离为公共函数 swap。// 交换位置export function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp;}冒泡排序冒泡排序是最简单的排序，一一对比相邻的两个数，顺序不对就交换过来，这样子，每一轮最大的值总会慢慢的被交换到最右侧。所以才会叫冒泡排序描述假设数组长度为 n比较相邻的两个数，如果第 1 个大于第 2 个，就交换位置重复第 1 步，一轮下来最大值被交换到第 n 个位置，也就是最右侧开启新一轮，重复 12 步，最大值会被冒泡到第 n-1 个位置重复上述步骤，直到所有都排序好例子：对 3, 1, 5, 2, 4 进行排序1,3,5,2,4 3 > 1 ,交换位置1,3,5,2,4 3 < 5 ,不变1,3,2,5,4 5 > 2 ,交换位置1,3,2,4,5 5 > 4 ,交换位置,第一轮结束1,3,2,4,5 1 < 3 ,不变1,2,3,4,5 3 > 2 ,交换位置1,2,3,4,5 …依次对比1,2,3,4,5 …1,2,3,4,5 … 结束代码实现// 冒泡排序export function bubbleSort(array) { for (let i = array.length - 1; i >= 1; i–) { let hasSwap = false; for (let j = 0; j <= i; j++) { if (array[j] > array[j + 1]) { swap(array, j, j + 1); hasSwap = true; } } if (!hasSwap) { // 这里用于优化，如果某一轮之后，没有进行任何交换，说明已经排序完成了，所以退出循环 break; } }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式小结冒泡算法是比较慢的排序之一，也是最容易实现的算法之一。复杂度稳定性：稳定时间复杂度： 平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)额外空间复杂度 O(1)选择排序选择排序是指每一轮从数组中取出最小值，然后跟第一个元素交换位置。然后再找出第二个最小值，跟第二个元素交换位置，。。。以此类推。直到倒数第二个位置例子对 3, 1, 5, 2, 4 进行排序// 这里只展示每一轮的结果3 1 5 2 4 //开始1 3 5 2 4 //第 1 轮1 2 5 3 4 //第 2 轮1 2 3 5 4 //第 3 轮1 2 3 4 5 //第 4 轮代码实现// 选择排序从开头开始，找出最小的值，放在第一个位置// 有点类似打扑克拍的时候，抽取每一张最小的放在最左边export function selectSort(array) { for (let i = 0; i < array.length - 1; i++) { let minIndex = i; let min = array[i]; for (let j = i + 1; j < array.length; j++) { if (array[j] < min) { min = array[j]; minIndex = j; } } swap(array, i, minIndex); }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式复杂度稳定性：不稳定时间复杂度： O(n^2)额外空间复杂度 O(1)插入排序插入排序的思想是，依次从数组中未排序的部分，取出数据，然后插入到已排序的部分。直到清空未排序的部分描述假设数组长度为 n , 从第 2 项开始从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素大于新元素，将该元素移到下一位置；重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤 25。代码实现export function insertSort(array) { for (let i = 0; i < array.length; i++) { let temp = array[i]; let j = i; while (j > 0 && array[j - 1] > temp) { // 将所有大于temp的往右移 array[j] = array[j - 1]; j–; } array[j] = temp; }}效果演示https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式复杂度稳定性：稳定时间复杂度：平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)额外空间复杂度 O(1)效果演示（汇总）https://global.chen4342024.co…注意打开开发者工具，切换到移动端模式总结这三种最基本的排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。在实际使用中，如果需要排序的数据比较多，是不推荐使用这 3 种排序的。毕竟他们的效率都不太理想在实际应用中，应该选择高级排序算法： 快速排序 …在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。大概是冒泡/选择排序的快 1 倍这是因为 插入排序需要比较的次数是 1+2+3+..+n = n * (n-1) /2,这是最坏的情况，大部分时候并不需要全部比较，所以平均下来只需要 n*(n-1)/4而冒泡/选择排序都需要n * (n-1)/2,所以平均下来，插入排序大概是冒泡/选择排序的快 1 倍 ...