排序算法(随机)快速排序(递归)

1.快速排序

  快速排序的基本思路属于分治算法的一种，通过选择数组中的某一个元素作为分界点(key)，大于key的元素放置在数组右边，小于key的元素放置在数组的左边，然后通过递归调用该过程来实现排序算法。

  代码如下:

int Partition(int *A, int p, int q){
  int i = p;
  int key = A[i];
  for(int j = p+1; j <= q, j++){
    if(A[j]<key){
      i++;
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp; 
    }
  }
  int temp = A[i];
  A[i] = A[P];
  A[p] = temp;

  return i;
}

void QuickSort(int *A, int p, int q){
  if(p<q){
    int r = Partition(A, p, q);
    QuickSort(A, p, r-1);
    QuickSort(A, r+1, q);
  }else{
    return ;
  }
}

  代码中主要有两个函数Partition(int *A, int p, int q)和QuickSort(int *A, int p, int q),

  其中，Partition(int *A, int p, int q)中，指针A指向待排序的数组，p为待排序数组的起点，q为终点，函数中选用数组的起点A[p]作为分界点(key)，结果该函数调用后，数组A中大于key的元素在key的右边，小于key的元素在key的左边。

  QuickSort(int *A, int p , int q)函数为快速排序的实现函数，通过递归调用每次对数组进行分界Partition操作，最终实现对数组的排序。

 

2.随机快速排序

  在快速排序中每次对数组的分界操作Partition都是以数组的其实点作为分界点(key)，这样就带来了一个问题——当待排序数组是一个已排好序的数组时，快速排序的执行时间是O(n平方)，在执行 时间上比较耗时，于是就有了随机快速排序的思想。

  在随机快速排序中，每次对数组的分界操作Partition都是在数组中随机寻找一个元素作为分界点(key)，这样就避免了上诉问题，随机排序的平均在执行时间为O(n*lg(n))。比上面的O(n平方)有很大的提高。