快速排序

#include <iostream>
using namespace std;

void QuickSort(int * array, int len)
 {
  if(len == 1)
    return;
  // 按照最坏的可能，为2个子数组分配空间
  int * left = new int[len], * right = new int[len];
  // 设置两个子数组长度的初值（为0）
  int left_idx = 0, right_idx = 0;
  // 1.拆分
  int key = array[0];
  for(int i = 0; i < len; i++)
  {
    if(array[i] < key)
      left[left_idx++] = array[i];
    if(array[i] > key)
      right[right_idx++] = array[i];
  }
  // 2.对子数组进行排序
  QuickSort(left, left_idx);
  QuickSort(right, right_idx);
  // 3.合并子数组
  int idx = 0;
  for(int i = 0; i < left_idx; i++)
    array[idx++] = left[i];
  array[idx++] = key;
  for(int i = 0; i < right_idx; i++)
    array[idx++] = right[i];
  // 释放临时空间
  delete[] left;
  delete[] right;
 }