分治思想下的快速排序
分治思想
1.分治法的设计思想：把一个难以解决的大问题，分割成几个规模较小的相同问题，然后处理这些小问题，最终解决这个大问题。
2.分治策略:对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
3.如果原问题可以分割成k个子问题（1<k<=n），而且这些小问题都可解，并且可以根据这些小问题的解求出原问题的解，那么就可以使用分治法，由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
4.分治适用的情况：
1.该问题的规模缩小到一定的程度就可以容易地解决
2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3.利用该问题分解出的子问题的解可以合并为该问题的解
4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
快速排序
1.基本思想：
1.先从数组中选取一个基准数，通常是a[0]
2.对数组进行分区，比基准数大的放到右边，比基准数小的放到左边
3.对两个分区再次进行1.2步的操作，重复下去，知道数组排序完成
2.代码实现(java):
public static void main(String[] args) {
int[] arr = {32,12,53,25,64,62,41,33,7};
new demo2().quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private void quickSort(int[] arr, int start, int end) {
if(start>=end){
return;
}
int k=arr[start];
int i=start,j=end;
while (i!=j){
while(i<j&&arr[j]>=k) {
--j;
}
swap(arr,i,j);
while(i<j&&arr[i]<=k) {
++i;
}
swap(arr, i, j);
}
//分治思想
quickSort(arr,start,i-1);
quickSort(arr,i+1,end);
}
private void swap(int[] arr, int i, int j) {
int temp;
temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
