Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

第 91 期(算法-排序):经典排序算法之快速排序 #94

Open
wingmeng opened this issue Aug 20, 2019 · 0 comments
Open

第 91 期(算法-排序):经典排序算法之快速排序 #94

wingmeng opened this issue Aug 20, 2019 · 0 comments

Comments

@wingmeng
Copy link
Collaborator

快速排序

快速排序(Quick sort)是一个基于交换的排序算法,它采用分治的策略,所以也称其为分治排序。

  • 原理: 通过一趟排序将待排序列分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,再分别对这两部分记录继续进行排序,直至整个序列有序。
  • 复杂度: 时间复杂度:O(nlogn),空间复杂度:O(logn)(主要由递归而产生的对栈空间的影响)
  • 稳定性: 快速排序是不稳定的排序算法,因为比较和交换是跳跃进行的。

quickSort

算法分析:

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
function quickSort(arr, left, right) {
  var len = arr.length,
      partitionIndex,
      left = typeof left != 'number' ? 0 : left,
      right = typeof right != 'number' ? len - 1 : right;

  if (left < right) {
      partitionIndex = partition(arr, left, right);
      quickSort(arr, left, partitionIndex-1);
      quickSort(arr, partitionIndex+1, right);
  }

  return arr;
}

// 分区操作
function partition(arr, left, right) {
  // 设定基准值(pivot)
  var pivot = left, 
      index = pivot + 1;

  for (var i = index; i <= right; i++) {
      if (arr[i] < arr[pivot]) {
          swap(arr, i, index);
          index++;
      }       
  }

  swap(arr, pivot, index - 1);
  return index-1;
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant