버블정렬, 퀵정렬, 힙정렬의 시간복잡도는 어떻게 되나요?-일반적인 문제-php.cn

버블 정렬의 시간 복잡도: 최선의 경우는 "O(n)"이고 최악의 경우는 "O(n2)"입니다. 퀵 정렬의 시간 복잡도: 최선의 경우는 "O(nlogn)"이고 최악의 경우는 "O(n2)"입니다. 힙 정렬의 시간 복잡도는 "O(nlogn)"입니다.

버블정렬, 퀵정렬, 힙정렬의 시간복잡도는 어떻게 되나요?

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

버블 정렬

시간 복잡성

최상의 사례: 배열 자체는 순차적이며 외부 루프는 O(n)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을 완료하기 위해 한 번 순회됩니다.

최악의 시나리오: 배열 자체는 역순이며 내부 및 외부 레이어 순회 O(n2)

Space Complexity
버블정렬, 퀵정렬, 힙정렬의 시간복잡도는 어떻게 되나요? 공간 교환 시퀀스 O(1) 생성

안정성

안정적, 판단이 사실이 아닐 경우 순서가 바뀌지 않고, 같은 요소도 바뀌지 않기 때문입니다

버블 정렬은 모든 정렬 알고리즘 중 가장 간단한 정렬 알고리즘입니다. 그러나 실행 시간 관점에서 볼 때 버블 정렬은 최악이며 복잡도는 O(n2)입니다.
버블 정렬은 인접한 두 항목을 비교하고 첫 번째 항목이 두 번째 항목보다 크면 서로 바꿉니다. 마치
거품이 표면으로 떠오르는
것처럼 항목이 올바른 순서로 위로 이동하므로 이름이 버블 정렬입니다. 🎜
🎜교환 시 특정 교환 아이템의 가치를 저장하기 위해 중간 가치를 사용합니다. 다른 정렬 방법도 이 방법을 사용하므로 재사용을 위해 이 교환 코드를 배치하는 방법을 선언합니다. ES6(ECMAScript 2015) 사용 ** 향상된 객체 속성 - 객체 배열의 구조 분해 할당 구문 ** 이 함수는 다음과 같이 작성할 수 있습니다: 🎜

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
    while (i < j && arr[j] >= base) {
      //寻找小于base的右指针元素a，跳出循环，否则左移一位
      j--;
    }
    while (i < j && arr[i] <= base) {
      //寻找大于base的左指针元素b，跳出循环，否则右移一位
      i++;
    }
    if (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; //交换a和b
    }
  }
  [arr[left], arr[j]] = [arr[j], arr[left]]; //交换相遇位置元素和base，base归位
  //   let k = i;
  quicksort(arr, left, i - 1); //对base左边的元素递归排序
  quicksort(arr, i + 1, right); //对base右边的元素递归排序
  return arr;
}

로그인 후 복사

🎜빠른 정렬🎜 🎜 🎜시간 복잡도🎜🎜 가장 좋은 경우: 기본 값이 전체 배열과 정확히 동일할 때마다 O(nlogn)🎜 최악의 경우: 기본 값이 배열의 최대값일 때마다 / 최소값, O(n2)🎜🎜🎜공간 복잡도🎜🎜 퀵 정렬은 재귀적이며 각 재귀 수준의 호출 정보를 저장하기 위해 스택을 사용해야 하므로 공간 복잡도와 깊이가 🎜 최선의 경우: 기본 값이 전체 배열과 정확히 동일할 때마다 재귀 트리의 깊이는 O(logn)🎜 최악의 경우: 기본 값이 항상 는 배열 값의 최대/최소이고 재귀 트리의 깊이는 O(n)🎜🎜🎜stability🎜🎜입니다. 빠른 정렬은 불안정합니다. 교환됩니다. 🎜 퀵 정렬은 재귀적입니다. 🎜 특별한 경우: 왼쪽>오른쪽, 직접 종료합니다. 🎜🎜🎜단계: 🎜🎜🎜(1) 먼저 배열에서 중간 항목을 🎜pivot🎜 베이스로 선택하고 일반적으로 🎜첫 번째 값🎜을 사용합니다. 🎜🎜(2) 🎜두 개의 포인터🎜를 만듭니다. 왼쪽 포인터는 배열의 첫 번째 항목을 가리키고 오른쪽 포인터는 배열의 마지막 항목을 가리킵니다. 🎜피벗보다 작은 요소🎜를 찾을 때까지 오른쪽 포인터를 이동한 다음 피벗보다 큰 요소🎜를 찾을 때까지 🎜왼쪽 포인터를 이동한 다음 🎜교체🎜하고 왼쪽 포인터가 오른쪽과 만날 때까지 이 과정을 반복합니다. 포인터. 이 프로세스를 수행하면 피벗보다 작은 값이 피벗 앞에 정렬되고 피벗보다 큰 값이 피벗 뒤에 정렬됩니다. 이 단계를 🎜파티션 작업🎜이라고 합니다. 🎜🎜(3) 그런 다음 🎜 피벗 요소와 포인터가 멈춘 위치에서 요소 🎜를 교환합니다(이는 이 요소 🎜를 해당 위치 🎜로 되돌리는 것과 같습니다. 이 요소의 왼쪽에 있는 요소는 그것보다 작습니다. 오른쪽에 있는 요소가 그것보다 큽니다. 이 위치가 그의 최종 위치입니다.🎜🎜(4) 그런 다음 알고리즘은 이전 두 단계를 반복합니다( 🎜재귀 방법🎜), 🎜🎜재귀 종료는 <코드>왼쪽/오른쪽입니다. =i, 즉: 🎜

// 建立大顶堆
function buildHeap(arr) {
  //从最后一个非叶子节点开始，向前遍历，
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    headAdjust(arr, i, arr.length); //对每一个节点都调整堆，使其满足大顶堆规则
  }
}

로그인 후 복사

🎜이 시점에서 하위 배열 배열이 정렬되었습니다. 🎜🎜 원점 복귀 다이어그램: 🎜🎜🎜🎜 구체적인 구현: 🎜

//从输入节点处调整堆
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; //子节点指针指向新的子节点
  }
}

로그인 후 복사

🎜 참조: https://www.cnblogs.com/venoral/p/5180439.html🎜🎜🎜Heap sort🎜🎜🎜힙의 개념🎜

堆是一个完全二叉树。
完全二叉树：二叉树除开最后一层，其他层结点数都达到最大，最后一层的所有结点都集中在左边（左边结点排列满的情况下，右边才能缺失结点）。
大顶堆：根结点为最大值，每个结点的值大于或等于其孩子结点的值。
小顶堆：根结点为最小值，每个结点的值小于或等于其孩子结点的值。
堆的存储：堆由数组来实现，相当于对二叉树做层序遍历。如下图：

时间复杂度
总时间为建堆时间+n次调整堆 —— O(n)+O(nlogn)=O(nlogn)
建堆时间：从最后一个非叶子节点遍历到根节点，复杂度为O(n)
n次调整堆：每一次调整堆最长的路径是从树的根节点到叶子结点，也就是树的高度logn，所以每一次调整时间复杂度是O(logn)，一共是O(nlogn)

空间复杂度
堆排序只需要在交换元素的时候申请一个空间暂存元素，其他操作都是在原数组操作，空间复杂度为O(1)

稳定性
堆排序是不稳定的，因为可能会交换相同的子结点。

步骤一：建堆

以升序遍历为例子，需要先将将初始二叉树转换成大顶堆，要求满足：树中任一非叶子结点大于其左右孩子。
实质上是调整数组元素的位置，不断比较，做交换操作。
找到第一个非叶子结点——Math.floor(arr.length / 2 - 1)，从后往前依次遍历
对每一个结点，检查结点和子结点的大小关系，调整成大根堆

// 建立大顶堆
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!