搜尋
首頁常見問題冒泡排序、快速排序和堆排序的時間複雜度是多少

冒泡排序、快速排序和堆排序的時間複雜度是多少

Apr 15, 2021 pm 05:23 PM
冒泡排序堆排序快速排序

冒泡排序的時間複雜度:最好情況是“O(n)”,最壞情況是“O(n2)”。快速排序的時間複雜度:最好情況是“O(nlogn)”,最壞情況是“O(n2)”。堆排序的時間複雜度是「O(nlogn)」。

冒泡排序、快速排序和堆排序的時間複雜度是多少

本教學操作環境:windows7系統、Dell G3電腦。

冒泡排序(Bubble Sort)

時間複雜度

最好的情況:陣列本身是順序的,外層迴圈遍歷一次就完成O(n)

最壞的情況:數組本身是逆序的,內外層遍歷O(n2)

#空間複雜度
開啟一個空間交換順序O(1)
##穩定性
穩定,因為if判斷不成立,就不會交換順序,不會交換相同元素

  • 冒泡排序它在所有排序演算法中最簡單。然而, 從運行時間的角度來看,冒泡排序是最糟糕的一個,它的

    複雜度是O(n2)

  • 冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。元素項向上移動至正確的順序,就好像

    氣泡升至表面一樣,冒泡排序因此得名。

  • 交換時,我們用一個中間值來儲存某一交換項的值。其他排序法也會用到這個方法,因此我 聲明一個方法放置這段交換程式碼以便重複使用。使用ES6(ECMAScript 2015)**增強的物件屬性-物件陣列的解構賦值語法,**這個函數可以寫成下面這樣:

  • [array[index1], array[index2]] = [array[index2], array[index1]];
具體實作:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {//外循环(行{2})会从数组的第一位迭代 至最后一位,它控制了在数组中经过多少轮排序
    for (let j = 0; j < arr.length - i; j++) {//内循环将从第一位迭代至length - i位,因为后i位已经是排好序的,不用重新迭代
      if (arr[j] > arr[j + 1]) {//如果前一位大于后一位
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交换位置
      }
    }
  }
  return arr;
}

快速排序

時間複雜度 最好的情況:每個base值都剛好平分整個數組,
O(nlogn) 最糟的情況:每一次base值都是陣列中的最大/最小值,
O(n2)

空間複雜度# 快速排序是遞歸的,需要藉助棧來保存每一層遞歸的呼叫訊息,所以空間複雜度和遞歸樹的深度一致
最好的情況:每一次base值都剛好平分整個數組,遞歸樹的深度
O(logn) 最糟的情況:每個base值都是陣列中的最大/最小值,遞迴樹的深度
O(n)

穩定性 快速排序是
不穩定的,因為可能會交換相同的關鍵字。 快速排序是遞歸的,
特殊情況:left>right,直接退出。

步驟:

(1) 首先,從陣列中選取中間一項作為

主元base,一般取第一個值

(2) 建立

兩個指標,左邊一個指向數組第一個項,右邊一個指向數組最後一個項。 移動右邊指標直到找到一個比主元小的元素,接著,移動左指標直到我們找到一個比主元大的元素,然後交換它們 ,重複這個過程,直到左邊指針遇見了右指針。這個過程將使得比主元小的值都排在主元之前,而比主元大的值都排在主元之後。這一步叫作劃分運算

(3)然後

交換主元和指標停下來的位置的元素(等於說是把這個元素歸位,這個元素左邊的都比他小,右邊的都比他大,這個位置就是他最終的位置)

(4) 接著,演算法對劃分後的小數組(較主元小的值組成的子數組,以及較主由元大的值組成的子數組)重複之前的兩個步驟(

遞歸方法),

遞歸的出口為

left/right=i,也就是:

left>i-1 / i+1>right

此時,子數組數組已排序完成。

歸位示意圖:


冒泡排序、快速排序和堆排序的時間複雜度是多少

具體實作:

function quicksort(arr, left, right) {
  if (left > right) {
    return;
  }
  var i = left,
    j = right,
    base = arr[left]; //基准总是取序列开头的元素
  //   var [base, i, j] = [arr[left], left, right]; //以left指针元素为base
  while (i != j) {
    //i=j,两个指针相遇时,一次排序完成,跳出循环
    // 因为每次大循环里面的操作都会改变i和j的值,所以每次循环/操作前都要判断是否满足i<j>= base) {
      //寻找小于base的右指针元素a,跳出循环,否则左移一位
      j--;
    }
    while (i 參考:https://www.cnblogs.com/venoral/p/5180439. html<p></p>
<h2>堆排序<strong></strong>
</h2>堆的概念<p></p>
<ul>
<li>堆是一个完全二叉树。</li>
<li>完全二叉树: 二叉树除开最后一层,其他层结点数都达到最大,最后一层的所有结点都集中在左边(左边结点排列满的情况下,右边才能缺失结点)。</li>
<li>大顶堆:根结点为最大值,每个结点的值大于或等于其孩子结点的值。</li>
<li>小顶堆:根结点为最小值,每个结点的值小于或等于其孩子结点的值。</li>
<li>堆的存储: 堆由数组来实现,相当于对二叉树做层序遍历。如下图:<br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/70c3cf834e3b712407f805e79c392ea0-1.png?x-oss-process=image/resize,p_40" class="lazy" alt="冒泡排序、快速排序和堆排序的時間複雜度是多少"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/024/70c3cf834e3b712407f805e79c392ea0-2.png?x-oss-process=image/resize,p_40" class="lazy" alt="冒泡排序、快速排序和堆排序的時間複雜度是多少">
</li>
</ul>
<p><strong>时间复杂度</strong><br> 总时间为<code>建堆时间</code>+<code>n次调整堆</code> —— <code>O(n)+O(nlogn)=O(nlogn)</code><br><code>建堆时间</code>:从最后一个非叶子节点遍历到根节点,复杂度为<code>O(n)</code><br><code>n次调整堆</code>:每一次调整堆最长的路径是从树的根节点到叶子结点,也就是树的高度<code>logn</code>,所以每一次调整时间复杂度是<code>O(logn)</code>,一共是<code>O(nlogn)</code></p>
<p><strong>空间复杂度</strong><br> 堆排序只需要在交换元素的时候申请一个空间暂存元素,其他操作都是在原数组操作,空间复杂度为<code>O(1)</code></p>
<p><strong>稳定性</strong><br> 堆排序是<code>不稳定</code>的,因为可能会交换相同的子结点。</p>
<p><strong>步骤一:建堆</strong></p>
<ul>
<li>以升序遍历为例子,需要先将将初始二叉树转换成大顶堆,要求满足:<code>树中任一非叶子结点大于其左右孩子</code>。</li>
<li>实质上是调整数组元素的位置,不断比较,做交换操作。</li>
<li>找到第一个非叶子结点——<code>Math.floor(arr.length / 2 - 1)</code>,从后往前依次遍历</li>
<li>对每一个结点,检查结点和子结点的大小关系,调整成大根堆</li>
</ul><pre class='brush:php;toolbar:false;'>// 建立大顶堆
function buildHeap(arr) {
  //从最后一个非叶子节点开始,向前遍历,
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    headAdjust(arr, i, arr.length); //对每一个节点都调整堆,使其满足大顶堆规则
  }
}

步骤二:调整指定结点形成大根堆

  • 建立childMax指针指向child最大值节点,初始值为2 * cur + 1,指向左节点
  • 当左节点存在时(左节点索引小于数组length),进入循环,递归调整所有节点位置,直到没有左节点为止(cur指向一个叶结点为止),跳出循环,遍历结束
  • 每次循环,先判断右节点存在时,右节点是否大于左节点,是则改变childMax的指向
  • 然后判断cur根节点是否大于childMax,
  • 大于的话,说明满足大顶堆规律,不需要再调整,跳出循环,结束遍历
  • 小于的话,说明不满足大顶堆规律,交换根节点和子结点,
  • 因为交换了节点位置,子结点可能会不满足大顶堆顺序,所以还要判断子结点然后,改变curchildMax指向子结点,继续循环判断。

冒泡排序、快速排序和堆排序的時間複雜度是多少

//从输入节点处调整堆
function headAdjust(arr, cur, len) {
  let intialCur = arr[cur]; //存放最初始的
  let childMax = 2 * cur + 1; //指向子树中较大的位置,初始值为左子树的索引

  //子树存在(索引没超过数组长度)而且子树值大于根时,此时不符合大顶堆结构,进入循环,调整堆的结构
  while (childMax < len) {
    //判断左右子树大小,如果右子树更大,而且右子树存在,childMax指针指向右子树
    if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
    //子树值小于根节点,不需要调整,退出循环
    if (arr[childMax] < arr[cur]) break;
    //子树值大于根节点,需要调整,先交换根节点和子节点
    swap(arr, childMax, cur);
    cur = childMax; //根节点指针指向子节点,检查子节点是否满足大顶堆规则
    childMax = 2 * cur + 1; //子节点指针指向新的子节点
  }
}

步骤三:利用堆进行排序

  • 从后往前遍历大顶堆(数组),交换堆顶元素a[0]和当前元素a[i]的位置,将最大值依次放入数组末尾。
  • 每交换一次,就要重新调整一下堆,从根节点开始,调整根节点~i-1个节点(数组长度为i),重新生成大顶堆
    冒泡排序、快速排序和堆排序的時間複雜度是多少
    冒泡排序、快速排序和堆排序的時間複雜度是多少
// 堆排序
function heapSort(arr) {
  if (arr.length <= 1) return arr;
  //构建大顶堆
  buildHeap(arr);
  //从后往前遍历,
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, i, 0); //交换最后位置和第一个位置(堆顶最大值)的位置
    headAdjust(arr, 0, i); //调整根节点~i-1个节点,重新生成大顶堆
  }
  return arr;
}

完整代码:

// 交换数组元素
function swap(a, i, j) {
  [a[i], a[j]] = [a[j], a[i]];
}
//从输入节点处调整堆
function headAdjust(arr, cur, len) {
  let intialCur = arr[cur]; //存放最初始的
  let childMax = 2 * cur + 1; //指向子树中较大的位置,初始值为左子树的索引

  //子树存在(索引没超过数组长度)而且子树值大于根时,此时不符合大顶堆结构,进入循环,调整堆的结构
  while (childMax < len) {
    //判断左右子树大小,如果右子树更大,而且右子树存在,childMax指针指向右子树
    if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++;
    //子树值小于根节点,不需要调整,退出循环
    if (arr[childMax] < arr[cur]) break;
    //子树值大于根节点,需要调整,先交换根节点和子节点
    swap(arr, childMax, cur);
    cur = childMax; //根节点指针指向子节点,检查子节点是否满足大顶堆规则
    childMax = 2 * cur + 1; //子节点指针指向新的子节点
  }
}
// 建立大顶堆
function buildHeap(arr) {
  //从最后一个非叶子节点开始,向前遍历,
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    headAdjust(arr, i, arr.length); //对每一个节点都调整堆,使其满足大顶堆规则
  }
}
// 堆排序
function heapSort(arr) {
  if (arr.length <= 1) return arr;
  //构建大顶堆
  buildHeap(arr);
  //从后往前遍历,
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, i, 0); //交换最后位置和第一个位置(堆顶最大值)的位置
    headAdjust(arr, 0, i); //调整根节点~i-1个节点,重新生成大顶堆
  }
  return arr;
}

更多编程相关知识,请访问:编程视频!!

以上是冒泡排序、快速排序和堆排序的時間複雜度是多少的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)