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

冒泡排序的時間複雜度：最好情況是“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="https://img.php.cn/upload/article/000/000/024/70c3cf834e3b712407f805e79c392ea0-1.png" alt="冒泡排序、快速排序和堆排序的時間複雜度是多少"><br><img src="https://img.php.cn/upload/article/000/000/024/70c3cf834e3b712407f805e79c392ea0-2.png" 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:js;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，
• 大于的话，说明满足大顶堆规律，不需要再调整，跳出循环，结束遍历
• 小于的话，说明不满足大顶堆规律，交换根节点和子结点，
• 因为交换了节点位置，子结点可能会不满足大顶堆顺序，所以还要判断子结点然后，改变cur和childMax指向子结点，继续循环判断。

//从输入节点处调整堆
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中文網其他相關文章！