快速排序递归详解

01

—

前言

我们熟知常见的排序算法有：冒泡排序、选择排序、归并排序、插入排序、快速排序等；每种都有其不同的特点以及解法，并且每种排序都可以找到不同算法思路来解答，拿快速排序来讲，有递归和非递归的解法，以下就讲讲递归的快速排序的解法。

02

—

快速排序概念

快速排序（Quick Sort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对着两部分记录继续进行排序，以达到整个序列有序。

过程解析：待排序的数组序列arr[]，假设要从小到大以此从左至右给数组排序，取出其中一个arr[left]为基准元素，通常取第一个为基准元素poivt，先从数组的最右边arr[end-1]开始往左移动，直到找到第一个比基准元素小(arr[right]<poivt)的值，把它arr[right]放到arr[left]的位置；接下来再从左往右移动，直到找到比基准元素大的值arr[i]，把它放到上述arr[right]的位置；当left指针与right指针指向同一个位置的时候，表明这趟（第一趟）排序已完成。

运用递归：运用递归的思想，其实也是分而治之的思想，来解决整个数组的排序。

从上图可以看到，完整的快速排序是建立在一趟快速排序之上的，它的具体步骤如下：

首先对待排序序列进行一趟快速排序（假设从左至右一次递增）；

一趟排序下来之后，基准元素的左边都是比它小的元素，右边都是比它大的元素；

再对基准元素左边的序列进行快速排序，对右边也进行快速排序；

重复步骤2、3，直到序列排序完成。

从快速排序的步骤中我们不难发现：快速排序其实使用的是分而治之的思想，它的排序过程是一个递归调用的过程。

03

—

代码详解

思路分析，核心的排序逻辑如下：

public static int partion(int[] arr,int left,int end){
  int povit = arr[left];//选取第一个为基准元素
  while(left < end){
    //从右向左开始移动，直到找到第一个比基准元素小的值
    while(left <end && arr[end] >= povit){
      end --;
    }
    arr[left] = arr[end];//将右边比基准元素小的值放在left的位置
    //从左向右开始移动，直到找到第一个比基准元素大的值
    while(left < end && arr[left] <= povit){
      left ++;
    }
    arr[end] = arr[left];//将左边比基准元素大的值放在end位置
  }
  //当第一趟排序完毕时，left和end指向同一个值，此时返回left位置，left=end且值是即基准元素
  arr[left] = povit;
  return left;
}

以数组：{10,5,7,12,1,9,13,8,6,3,11}为例要进行排序，从左至右依次递增。

1、选择10为基准元素povit，从右边开始向左边移动指针，找到第一个比10小的数为3，这时把3放到10的位置。

2、再从左边开始移动指针，也就是3的位置开始移动，找到比10大的值是12，把12放到之前（原来）3的位置处。

3、循环整个数组，当left指针和rigth指针指向同一个位置（left=right）时，这时第一趟排序完成，把基准元素的值赋值给当前指针位置，并返回。

第一趟完成排序后为：{3,5,7,6,1,9,8,10,13,12,11}

4、重复1和2两个步骤，以返回的值为基准元素点，递归调用上述3个步骤，最终完成

完整的代码程序，就是对一组数组进行递归的调用，如下：

public static int partion(int[] arr,int left,int end){
  int povit = arr[left];//选取第一个为基准元素
  while(left < end){
    //从右向左开始移动，直到找到第一个比基准元素小的值
    while(left <end && arr[end] >= povit){
      end --;
    }
    arr[left] = arr[end];//将右边比基准元素小的值放在left的位置
    //从左向右开始移动，直到找到第一个比基准元素大的值
    while(left < end && arr[left] <= povit){
      left ++;
    }
    arr[end] = arr[left];//将左边比基准元素大的值放在end位置
  }
  //当第一趟排序完毕时，left和end指向同一个值，此时返回left位置，left=end且值是即基准元素
  arr[left] = povit;
  return left;
}


public static void quickSort(int arr[],int left,int end){
  if(left < end){
    int pivot = partion(arr,left,end);

    //对左半部分递归
    quickSort(arr,left,pivot-1);

    //对右半部分递归
    quickSort(arr,pivot+1,end);
  }
}

最终得到结果：{1,3,5,6,7,8,9,10,11,12,13}

04

—

总结

采用分而治之的递归思想是解决快速排序一个比较好的方案，递归的思想不止是用到排序里面，也可以用于查找里面，比如当需要在大数据量之中查找某个某个值时，也可以运用这种思想，从而达到提升查询效率。