数据结构-挖坑填数+分治法解决快速排序问题（java+c）

看到网上有很多的讲解，决定自己整理一遍 首先上定义

一、定义 1.分治法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法

简单的说就是，大的问题划分成一块一块的几个小问题，把小的问题解决了合并起来就是原问题的解

有人会问，递归和分治一样吗？其实他们是有区别的，递归是自己调用自己而分治是上面说的那样，因为递归和分治经常要一起用到，所以有些人误解递归和分治是一样的

2.挖坑填数

推荐：https://blog.csdn.net/MoreWindows/article/details/6684558?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param

3.快速排序思想

快速排序（quick sort）是由冒泡排序改进而得的，他的基本思想是在待排序的n个元素中任意取一个元素（通常取第一个元素）作为基准，把该元素放入适当位置后，数据序列被此元素划分为两部分。 所有关键字比该元素关键字小的元素放置在前一部分，所有比它大的元素放置在后一部分，并把该元素排在这两部分的中间（成为元素归位），这个过程称为一趟快速排序，即一趟划分。

之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或空为止

通俗易懂： 1．从数列中取出一个数作为基准数（第一个数）

2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边 或者说，将大于等于这个数的放到它的右边，小于它的数全放到它的左边

3．再对左右区间重复第二步，直到各区间只有一个数或空为止

二、代码实例 1.Java

//java代码1：
public class Main{
	public static void sort(int array[], int left, int right) {
		if(left