徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
安装
比浏览器更快的访问!
 

冒泡排序

指数 冒泡排序

冒泡排序(Bubble Sort--是一種簡單的排序算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。 冒泡排序對n個項目需要O(n^2)的比較次數,且可以原地排序。儘管這個演算法是最簡單瞭解和實作的排序算法之一,但它對於包含大量的元素的數列排序是很沒有效率的。 冒泡排序是與插入排序擁有相等的執行時間,但是兩種算法在需要的交換次數卻很大地不同。在最壞的情況,冒泡排序需要O(n^2)次交換,而插入排序只要最多O(n)交換。冒泡排序的實現(類似下面)通常會對已經排序好的數列拙劣地執行(O(n^2)),而插入排序在這個例子只需要O(n)個運算。因此很多現代的演算法教科書避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在內部迴圈第一次執行時,使用一個旗標來表示有無需要交換的可能,也可以把最優情況下的複雜度降低到O(n)。在這個情況,已經排序好的數列就無交換的需要。若在每次走訪數列時,把走訪順序反過來,也可以稍微地改進效率。有時候稱為雞尾酒排序,因為演算法會從數列的一端到另一端之間穿梭往返。 冒泡排序演算法的運作如下:.

6 关系: 原地算法鸡尾酒排序排序算法插入排序文本文件数组

原地算法

在電腦科學中,一個原地算法(in-place algorithm)基本上不需要額外輔助的資料結構,然而,允許少量額外的輔助變數來轉換資料的算法。當算法執行時,輸入的資料通常會被要輸出的部份覆蓋掉。不是原地算法有時候稱為非原地(not-in-place)或不得其所(out-of-place)。 一個算法有時候會錯誤地被稱為原地算法,只因為它用它的輸出資料會覆蓋掉它的輸入資料。事實上這條件既不充分(在快速排序案例中所展示的)也非必要;輸出資料的空間可能是固定的,或如果以輸出為串流資料而言,也甚至是可能無法被數清楚的。另一方面來看,有時候要決定一個算法是不是原地,而數它的輸出空間可能是比較可行的,像是底下的第一個的reverse範例;如此使得它更難去嚴格地定義原地算法。在理論上的應用像是log-space reduction,更是典型的總是忽略輸出的空間(在這些狀況,更重要的是輸出為僅能寫入)。.

新!!: 冒泡排序和原地算法 · 查看更多 »

鸡尾酒排序

鸡尾酒排序,也就是定向冒泡排序,雞尾酒攪拌排序,攪拌排序(也可以視作選擇排序的一種變形),漣漪排序,來回排序或快乐小時排序,是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。.

新!!: 冒泡排序和鸡尾酒排序 · 查看更多 »

排序算法

在計算機科學與數學中,一個排序算法(Sorting algorithm)是一種能將一串資料依照特定排序方式进行排列的一種算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法(例如搜尋算法與合併算法)中是重要的,如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上,排序算法的輸出必須遵守下列兩個原則:.

新!!: 冒泡排序和排序算法 · 查看更多 »

插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。.

新!!: 冒泡排序和插入排序 · 查看更多 »

文本文件

文本文件一般指只有字符原生编码构成的二进制计算机文件,與富文本相比,其不包含字样样式的控制元素,能够被最简单的文本编辑器直接读取。.

新!!: 冒泡排序和文本文件 · 查看更多 »

数组

在計算機科學中,陣列資料結構(array data structure),簡稱数组(Array),是由相同类型的元素(element)的集合所組成的資料結構,分配一块连续的内存来存储。利用元素的索引(index)可以计算出该元素對應的儲存地址。 最簡單的資料結構類型是一維陣列。例如,索引為0到9的32位元整數陣列,可作為在記憶體位址2000,2004,2008,...2036中,儲存10個變量,因此索引為i的元素即在記憶體中的2000+4×i位址。陣列第一個元素的記憶體位址稱為第一位址或基礎位址。 二维数组,对应于數學上的矩陣概念,可表示為二維矩形格。例如: a.

新!!: 冒泡排序和数组 · 查看更多 »

重定向到这里:

冒泡法排序冒泡排序法冒泡算法氣泡排序汽泡排序法泡沫排序

传出传入
嘿!我们在Facebook上吧! »