快速排序

1、思路不对，编出的代码肯定不对，因此编码之前，一定要现在草稿纸上，根据思路写出伪码。

2、快速排序的思路：选一个目标，把数组分成两块，左边一块都比目标小，右边一块都比目标大。对每一块，递归做同样的事情，递归的出口时，左起点大于等于右起点。

3、递归的形参表为：数组和排序的区间，排序区间也就是左起点和右起点，QuickSort(int a[], int lhs,int rhs)，

递归出口：if(lhs>=rhs) return;

4、方法1：思路是对排序的区间做一个拷贝，取第一个为目标，从第二个开始，遍历排序区间，比目标小，从前往后。以此放在原数组区间的左边，比目标大，从后向前，一次放在原数组区间的右边，最后中间有个空格，把目标放在空格里，并且很容易知道空格的位置，对空格的前后两块递归。

5、方法一很简单直观，但是要多分配一块内存，存储区间的内容。有没有更好的办法呢？

　　方法2：思路是取第一个为目标，挖一个坑，从第二个开始遍历，比目标小，依次往前移，比目标大，应该放在后面，跟最后一个交换（下一次和倒数第二个交换，后面交换的位置前移一位），继续和目标比较，比目标小，往前移，比目标大，把倒数第二个换上来，以此类推。最后把目标填到空格里。

6、方法二有个问题，那就是从尾部换上来的元素，比目标大，还要把这个元素换回去，注意：这里换回去的位置，是尾部的前一个元素。有没有更好的办发呢？

　　方法二在第一个位置挖了个坑，比目标小的往前移，比目标大的，和最后面的元素交换，如果比目标小了，前移，如果还是比目标大，和次后面的元素交换。这就导致了换上来，有可能还要换回去。更好的办法是：既然前面已经有一个坑了，我从后面找到小元素，放到前面的坑里，这样后面就有了一个坑，再从前面找到一个大元素，放到后面的坑里，这样前面就挖了一个坑，最后剩下的坑放目标。

　　方法3：在前面挖个坑，从后面找到一个小元素，挖出来，放到前面的坑里，后面就有了一个坑，再从前面找一个大元素，挖出来，放到后面的坑了。循环继续的条件是：前后没有走到一起。注意，这个时候，不适合在使用for循环了，当然也可以使用for。使用while表达循序继续的条件：往后走的位置小于往前走的位置，在循环的内部，首先从后面找到小元素，挖坑，使用while找到小元素，添数挖坑，然后使用while从前面找到大元素，添数挖坑。也就是说，用到三个while，外部的while判断是否走到了一起。内部第一个while，从后面挖坑，内部第二个while从前面挖坑。

1 template <typename T>
 2 void QuickSort(T* arr,int left,int right)
 3 {
 4  if(left < right)
 5  {
 6   int mid = Adjust(arr,left,right);
 7   QuickSort(arr,left,mid-1);
 8   QuickSort(arr,mid+1,right);
 9  }
10 }
11 
12 
13 template <typename T>
14 int Adjust(T* arr, int i,int j)
15 {
16  T target = arr[i];
17  while(i<j)
18  {
19   while(i<j && arr[j]>target)
20   {
21    --j;
22   }
23   if(i<j)
24   {
25    arr[i++] = arr[j];
26   }
27 
28   while(i<j && arr[i]<target)
29   {
30    ++i;
31   }
32   if(i<j)
33   {
34    arr[j--] = arr[i];
35   }
36  }
37 
38  arr[i] = target;
39  return i;
40 }      

1 template <typename T>
 2 void QuickSort(T* arr,int left,int right)
 3 {
 4  // 只有一个元素，不需要排序。因此对于左闭合区间，比较left+1 与 right。
 5  // 注意：千万不能写成：++left<right。
 6  if(left+1 < right) 
 7  {
 8   int mid = Adjust(arr,left,right);
 9   QuickSort(arr,left,mid); //递归调用左闭合区间
10   QuickSort(arr,mid+1,right);
11  }
12 }
13 
14 
15 template <typename T>
16 int Adjust(T* arr, int i,int j)
17 {
18  T target = arr[i];
19  --j; // 首先移到有效元素
20  while(i<j)
21  {
22   while(i<j && arr[j]>target)
23   {
24    --j;
25   }
26   if(i<j)
27   {
28    arr[i++] = arr[j];
29   }
30 
31   while(i<j && arr[i]<target)
32   {
33    ++i;
34   }
35   if(i<j)
36   {
37    arr[j--] = arr[i];
38   }
39  }
40 
41  arr[i] = target;
42  return i;
43 }