排序算法-2（javascript） 快速排序的实现

快速排序

快速排序是冒泡排序的优化，与冒泡排序不同的是，使用了分治法，进行优化。会随机选取一个值pivot（基准元素），与其它值进行比较，将小于这个值的值全部放到一边，大于这个值的值放到另一边。然后再对两边的序列区间重复进行此操作，直至成为有序队列为止。

• 时间复杂度为：nlogn
• 空间复杂度为：logn
• 是不稳定的排序方法

快排的实现

单边循环法

比如对于初始序列：[8, 9, 6, 3, 2, 7]
实现过程思路：

1. 使用一个mark指针，用来表示小于基准元素的区域边界，初始时，指向pivot（基准元素，一般我们可以取第1位），也就是mark指向8，[8(mark), 9, 6, 3, 2, 7]
2. 从基准元素下一位x开始遍历，如果x > pivot，也就是9 > 8，不做任何操作，，[8(mark), 9(x), 6, 3, 2, 7]，继续遍历
3. 遍历的下一位, [8(mark), 9, 6(x), 3, 2, 7]，此时6 < 8，代表着这个数要移动到pivot的左侧，所以此时mark往右移一位，用来放置这个数，然后x和mark指向的数进行位置交换，也就是6和9交换，得到[8, 6(mark), 9(x), 3, 2, 7]
4. 继续[8, 6(mark), 9, 3(x), 2, 7]，x = 3，x < pivot，mark向右移一位指向9，3和mark指向的数9交换，交换后得到 [8, 6, 3(mark), 9(x), 2, 7]
5. 继续，[8, 6, 3(mark), 9, 2(x), 7], x = 2, 2 < 8，mark+1指向9，9与2交换，得到[8, 6, 3, 2(mark), 9(x), 7]
6. 继续[8, 6, 3, 2(mark), 9, 7(x)]，7 < 8，mark+1指向9，9与7交换，得到[8(pivot), 6, 3, 2, 7(mark), 9(x)]，此时x已是遍历的最后一位，所以这时将pivot与mark位置进行交换, [7, 6, 3, 2, 8, 9]，这样就完成了第一轮的快排，此时8左边的数都是小于8的，右边的数都是大于8的
7. 再递归对8左右两边序列[7,6,3,2]、[9]进行1-6步骤进行快速，直至成为整个数组变成有序队列

/*
* 快速排序
* 单边循环法的递归实现
*/
function singleQuickSort(arr, startIndex, endIndex) {
  // 健壮性判断
  if(!Array.isArray(arr)) throw new Error("请输入一个数组")
  if(!arr.length) return []
  if(startIndex >= endIndex) return;
  // 基准元素
  let pivot = arr[startIndex];
  // 标记指针,用于表示小于基准元素的区域边界
  let mark = startIndex;
  for(let i = startIndex + 1; i <= endIndex; i++) {
    if(arr[i] < pivot) {
      mark++;
      [ arr[mark], arr[i] ] = [ arr[i], arr[mark] ]
    }
  }
  [ arr[startIndex], arr[mark] ] = [ arr[mark], arr[startIndex] ]
  
  singleQuickSort(arr, startIndex, mark - 1)
  singleQuickSort(arr, mark + 1, endIndex)
  return arr
}

const arr = singleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr) // [ 2, 3, 6, 7, 8, 9 ]

双边循环法

双边循环法，顾名思义，就是用双指针的方法来遍历元素
实现过程：
如：[8, 2, 6, 3, 9, 7]

1. 假如随机值定基准元素pivot为第一个数8，定义一个左指针（指向第一个数），和一个右指针（指向最后一个），则8先与最后一个值进行比较，8比7大，所以两值交换位置[7, 2, 6, 3, 9, 8]
2. 此时左指针往右移一位，2与8比，2比8小，位置不变，左指针继续往右移动一位
3. 此时左指针往右移一位，6与8比，6比8小，位置不变，左指针继续往右移动一位
4. 3和8比，左指针继续往右移动一位
5. 9和8比，交换位置[7, 2, 6, 3, 8, 9]，此时左指针不变，右指针向左移一位，至此左右指针相同，第一轮比较结束，注意，结束的条件是左指针位置大于等于右指针；比8小的数都在8的左边，比8大的数都在8的右边
6. 对左边[7, 2, 6, 3]和右边的序列[9]分别再重复1-4步，直至都成为有序序列

/*
* 快速排序
* 双边循环法的递归实现
*/
function doubleQuickSort(arr, startIndex, endIndex) {
  // 健壮性判断
  if(!Array.isArray(arr)) throw new Error("请输入一个数组")
  if(!arr.length) return []
  if(startIndex >= endIndex) return arr;
  // 基准元素
  const pivot = arr[startIndex]
  // 左指针
  let left = startIndex
  // 右指针
  let right = endIndex
  // 只要左右指针不重合，就会继续循环
  while(left != right) {
    // 从最右边开始比较，如果right元素大于基准元素，则右指针向左移一位
    while(left < right && pivot <= arr[right]) {
      right--;
    }
    // 如果右边元素小于基准元素，则交换位置，然后左指针向右移一位
    if(arr[right] < pivot) {
      [ arr[left], arr[right] ] = [ arr[right], arr[left] ]
      left++;
    }
    // 然后开始比较基准元素和左边元素，如果左边元素小于基准元素，左指针向右移一位    
    while(left < right && pivot >= arr[left]) {
      left++;
    }
    // 如果左边元素大于基准元素，则交换位置，然后右指针向左移一位
    if(arr[left] > pivot) {
      [ arr[left], arr[right] ] = [ arr[right], arr[left] ]
      right--;
    }
  }
  // 当left===right时，就是基准元素所在的最终位置,此时 arr[left] === arr[right] === pivot;
  // 递归遍历左边和右边的无序队列
  doubleQuickSort(arr, startIndex, left-1)
  doubleQuickSort(arr, left + 1, endIndex)
  return arr;
}

const arr2 = doubleQuickSort([8, 9, 6, 3, 2, 7], 0, 5)
console.log(arr2) // [ 2, 3, 6, 7, 8, 9 ]

排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现