算法导论第7章快速排序答案

﹏ヽ暗。殇╰゛Y 2022-05-14 00:45 253阅读 0赞

# 一、概念 #

快速排序是基于分治模式的，选择一个数作为主元，经过一遍扫描，所有小于主元的数放在主元的左边，大于主元的数放在主元的右边，这样就划分成了两组数据。然后对两组数分别进行快排。

快排的运行时间与划分是否对称有关，关键是如何选择主元。

最坏情况下，时间复杂度是O(n^2)，最好情况下，时间是O(nlgn)

# 二、程序 #

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  \#include <iostream>   
2.  using namespace std;  
3.    
4.  //输出过程   
5.  void Print(int \*A, int len)  
6.  \{  
7.      for(int i = 0; i < len; i++)  
8.      \{  
9.          if(i)cout<<' ';  
10.         else cout<<"==> A = \{";  
11.         cout<<A\[i\];  
12.     \}  
13.     cout<<'\}'<<endl;  
14. \}  
15.   
16. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*7.1普通快排\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
17. //划分   
18. int Partition(int \*A, int p, int r)  
19. \{  
20.     //选择A\[r\]作为主元   
21.     int x = A\[r\];  
22.     int i = p - 1, j;  
23.     for(j = p; j < r; j++)  
24.     \{  
25.         //小于主元的放在左边   
26.         if(A\[j\] <= x)  
27.         \{  
28.             i++;  
29.             //把大于主元的交换到右边    
30.             swap(A\[i\],A\[j\]);  
31.         \}  
32.     \}  
33.     swap(A\[i+1\], A\[r\]);  
34.     //返回最终主元的位置   
35.     return i+1;  
36. \}  
37.   
38. void QuickSort(int \*A, int p, int r)  
39. \{  
40.     if(p < r)  
41.     \{  
42.         //以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大   
43.         int q = Partition(A, p, r);  
44.         //分别对左边和右边排序   
45.         QuickSort(A, p, q-1);  
46.         QuickSort(A, q+1, r);  
47.     \}  
48. \}  
49.   
50. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*7.3随机快排\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
51. //划分   
52. int Randomized\_Partition(int \*A, int p , int r)  
53. \{  
54.     //随机选择一个数作为主元   
55.     int i = rand() % (r-p+1) + p;  
56.     swap(A\[r\], A\[i\]);  
57.     return Partition(A, p, r);  
58. \}  
59. //排序，原理与普通快排相同，只是调用的划分方法不同    
60. void Randomized\_QuickSort(int \*A, int p, int r)  
61. \{  
62.     if(p < r)  
63.     \{  
64.         int q = Randomized\_Partition(A, p, r);  
65.         Randomized\_QuickSort(A, p, q-1);  
66.         Randomized\_QuickSort(A, q+1, r);  
67.     \}  
68. \}

#include <iostream>
    using namespace std;
    
    //输出过程
    void Print(int *A, int len)
    {
    	for(int i = 0; i < len; i++)
    	{
    		if(i)cout<<' ';
    		else cout<<"==> A = {";
    		cout<<A[i];
    	}
    	cout<<'}'<<endl;
    }
    
    /************************7.1普通快排************************************************/
    //划分
    int Partition(int *A, int p, int r)
    {
    	//选择A[r]作为主元
    	int x = A[r];
    	int i = p - 1, j;
    	for(j = p; j < r; j++)
    	{
    		//小于主元的放在左边
    		if(A[j] <= x)
    		{
    			i++;
    			//把大于主元的交换到右边
    			swap(A[i],A[j]);
    		}
    	}
    	swap(A[i+1], A[r]);
    	//返回最终主元的位置
    	return i+1;
    }
    
    void QuickSort(int *A, int p, int r)
    {
    	if(p < r)
    	{
    		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
    		int q = Partition(A, p, r);
    		//分别对左边和右边排序
    		QuickSort(A, p, q-1);
    		QuickSort(A, q+1, r);
    	}
    }
    
    /********************7.3随机快排******************************************************/
    //划分
    int Randomized_Partition(int *A, int p , int r)
    {
    	//随机选择一个数作为主元
    	int i = rand() % (r-p+1) + p;
    	swap(A[r], A[i]);
    	return Partition(A, p, r);
    }
    //排序，原理与普通快排相同，只是调用的划分方法不同
    void Randomized_QuickSort(int *A, int p, int r)
    {
    	if(p < r)
    	{
    		int q = Randomized_Partition(A, p, r);
    		Randomized_QuickSort(A, p, q-1);
    		Randomized_QuickSort(A, q+1, r);
    	}
    }

# 三、练习 #

## 7.1 快速排序的描述 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  7.1-1  
2.      A = \{13 19 9 5 12 8 7 4 21 2 6 11\}  
3.  ==> A = \{9 5 8 7 4 2 6 11 21 13 19 12\}  
4.  ==> A = \{5 4 2 6 9 8 7 11 21 13 19 12\}  
5.  ==> A = \{2 4 5 6 9 8 7 11 21 13 19 12\}  
6.  ==> A = \{2 4 5 6 9 8 7 11 21 13 19 12\}  
7.  ==> A = \{2 4 5 6 7 8 9 11 21 13 19 12\}  
8.  ==> A = \{2 4 5 6 7 8 9 11 21 13 19 12\}  
9.  ==> A = \{2 4 5 6 7 8 9 11 12 13 19 21\}  
10. ==> A = \{2 4 5 6 7 8 9 11 12 13 19 21\}  
11. ==> A = \{2 4 5 6 7 8 9 11 12 13 19 21\}  
12. 7.1-2  
13. 返回r  
14. 7.1-2  
15. 修改PARTITION(A, p, r)，增加对A\[i\]==x时的处理。对于A\[i\]==x的数据，一半放在x左边，一半放在x右边  
16. //划分   
17. int Partition(int \*A, int p, int r)  
18. \{  
19.     //选择A\[r\]作为主元   
20.     int x = A\[r\];  
21.     int i = p - 1, j;  
22.     bool flag = 0;  
23.     for(j = p; j < r; j++)  
24.     \{  
25.         //小于主元的放在左边   
26.         if(A\[j\] < x || (A\[j\] == x && flag))  
27.         \{  
28.             i++;  
29.             //把大于主元的交换到右边    
30.             swap(A\[i\],A\[j\]);  
31.             if(A\[j\] == x)flag = !flag;  
32.         \}  
33.     \}  
34.     swap(A\[i+1\], A\[r\]);  
35.     //返回最终主元的位置   
36.     return i+1;  
37. \}  
38. 7.1-4  
39. 修改PARTITION(A, p, r)，把L4改为do if A\[j\] >= x

7.1-1
        A = {13 19 9 5 12 8 7 4 21 2 6 11}
    ==> A = {9 5 8 7 4 2 6 11 21 13 19 12}
    ==> A = {5 4 2 6 9 8 7 11 21 13 19 12}
    ==> A = {2 4 5 6 9 8 7 11 21 13 19 12}
    ==> A = {2 4 5 6 9 8 7 11 21 13 19 12}
    ==> A = {2 4 5 6 7 8 9 11 21 13 19 12}
    ==> A = {2 4 5 6 7 8 9 11 21 13 19 12}
    ==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
    ==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
    ==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
    7.1-2
    返回r
    7.1-2
    修改PARTITION(A, p, r)，增加对A[i]==x时的处理。对于A[i]==x的数据，一半放在x左边，一半放在x右边
    //划分
    int Partition(int *A, int p, int r)
    {
    	//选择A[r]作为主元
    	int x = A[r];
    	int i = p - 1, j;
    	bool flag = 0;
    	for(j = p; j < r; j++)
    	{
    		//小于主元的放在左边
    		if(A[j] < x || (A[j] == x && flag))
    		{
    			i++;
    			//把大于主元的交换到右边
    			swap(A[i],A[j]);
    			if(A[j] == x)flag = !flag;
    		}
    	}
    	swap(A[i+1], A[r]);
    	//返回最终主元的位置
    	return i+1;
    }
    7.1-4
    修改PARTITION(A, p, r)，把L4改为do if A[j] >= x

## 7.2 快速排序的性能 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  7.2-2  
2.  O(n^2)  
3.  7.2-4  
4.  基本有序的数列用快排效率较低

7.2-2
    O(n^2)
    7.2-4
    基本有序的数列用快排效率较低

## 7.3 快速排序的随机化版本 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  7.3-1  
2.  随机化不是为了提高最坏情况的性能，而是使最坏情况尽量少出现  
3.  7.3-2  
4.  最坏情况下，n个元素每次都划分成n-1和1个，1个不用再划分，所以O(n)次  
5.  最好情况下，每次从中间划分，递推式N(n)=1+2\*N(n/2)=O(n)

7.3-1
    随机化不是为了提高最坏情况的性能，而是使最坏情况尽量少出现
    7.3-2
    最坏情况下，n个元素每次都划分成n-1和1个，1个不用再划分，所以O(n)次
    最好情况下，每次从中间划分，递推式N(n)=1+2*N(n/2)=O(n)

## 7.4 快速排序的分析 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  7.4-5  
2.  //7.4-5利用插入排序改善快排   
3.  int k = 4;  
4.  //划分   
5.  int Partition(int \*A, int p, int r)  
6.  \{  
7.      //选择A\[r\]作为主元   
8.      int x = A\[r\];  
9.      int i = p - 1, j;  
10.     bool flag = 0;  
11.     for(j = p; j < r; j++)  
12.     \{  
13.         //小于主元的放在左边   
14.         if(A\[j\] < x || (A\[j\] == x && flag))  
15.         \{  
16.             i++;  
17.             //把大于主元的交换到右边    
18.             swap(A\[i\],A\[j\]);  
19.             if(A\[j\] == x)flag = !flag;  
20.         \}  
21.     \}  
22.     swap(A\[i+1\], A\[r\]);  
23.     //返回最终主元的位置   
24.     return i+1;  
25. \}  
26. //快速排序   
27. void QuickSort(int \*A, int p, int r)  
28. \{  
29.     //长度小于k的子数组不排序   
30.     if(r - p >= k)  
31.     \{  
32.         //以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大   
33.         int q = Partition(A, p, r);  
34.         //分别对左边和右边排序   
35.         QuickSort(A, p, q-1);  
36.         QuickSort(A, q+1, r);  
37.     \}  
38. \}  
39. //插入排序   
40. void InsertSort(int \*A, int p, int r)  
41. \{  
42.     int i, j;  
43.     for(i = p + 1; i <= r; i++)  
44.     \{  
45.         int temp = A\[i\];  
46.         j = i;  
47.         while(A\[j-1\] > temp)  
48.         \{  
49.             A\[j\] = A\[j-1\];  
50.             j--;  
51.         \}  
52.         A\[j\] = temp;  
53.     \}  
54. \}  
55. void Sort(int \*A, int p, int r)  
56. \{  
57.     //先进行粗粒度的快排   
58.     QuickSort(A, p, r);  
59.     //逐个进行插入排序   
60.     InsertSort(A, p, r);  
61. \}

7.4-5
    //7.4-5利用插入排序改善快排
    int k = 4;
    //划分
    int Partition(int *A, int p, int r)
    {
    	//选择A[r]作为主元
    	int x = A[r];
    	int i = p - 1, j;
    	bool flag = 0;
    	for(j = p; j < r; j++)
    	{
    		//小于主元的放在左边
    		if(A[j] < x || (A[j] == x && flag))
    		{
    			i++;
    			//把大于主元的交换到右边
    			swap(A[i],A[j]);
    			if(A[j] == x)flag = !flag;
    		}
    	}
    	swap(A[i+1], A[r]);
    	//返回最终主元的位置
    	return i+1;
    }
    //快速排序
    void QuickSort(int *A, int p, int r)
    {
    	//长度小于k的子数组不排序
    	if(r - p >= k)
    	{
    		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
    		int q = Partition(A, p, r);
    		//分别对左边和右边排序
    		QuickSort(A, p, q-1);
    		QuickSort(A, q+1, r);
    	}
    }
    //插入排序
    void InsertSort(int *A, int p, int r)
    {
    	int i, j;
    	for(i = p + 1; i <= r; i++)
    	{
    		int temp = A[i];
    		j = i;
    		while(A[j-1] > temp)
    		{
    			A[j] = A[j-1];
    			j--;
    		}
    		A[j] = temp;
    	}
    }
    void Sort(int *A, int p, int r)
    {
    	//先进行粗粒度的快排
    	QuickSort(A, p, r);
    	//逐个进行插入排序
    	InsertSort(A, p, r);
    }

# 四、思考题 #

## 7-1 Hoare划分的正确性 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a）  
2.      A = \{13 19 9 5 12 8 7 4 11 2 6 21\}    
3.  ==> A = \{6 19 9 5 12 8 7 4 11 2 13 21\}    
4.  ==> A = \{6 2 9 5 12 8 7 4 11 19 13 21\}    
5.  ==> A = \{4 2 9 5 12 8 7 6 11 19 13 21\}    
6.  ==> A = \{4 2 5 9 12 8 7 6 11 19 13 21\}    
7.  ==> A = \{2 4 5 9 12 8 7 6 11 19 13 21\}    
8.  ==> A = \{2 4 5 6 12 8 7 9 11 19 13 21\}    
9.  ==> A = \{2 4 5 6 7 8 12 9 11 19 13 21\}    
10. ==> A = \{2 4 5 6 7 8 9 12 11 19 13 21\}    
11. ==> A = \{2 4 5 6 7 8 9 12 11 13 19 21\}  
12. b）  
13. int Hoare\_Partition(int \*A, int p, int r)    
14. \{    
15.     int x = A\[p\], i = p - 1, j = r + 1;    
16.     while(true)    
17.     \{    
18.         do\{j--;\}    
19.         while(A\[j\] > x);    
20.         do\{i++;\}    
21.         while(A\[i\] < x);    
22.         if(i < j)    
23.             swap(A\[i\], A\[j\]);    
24.         else return j;    
25.         Print(A, 12);    
26.     \}    
27. \}    
28. void Hoare\_QuickSort(int  \*A, int p, int r)    
29. \{    
30.     if(p < r)    
31.     \{    
32.         int q = Hoare\_Partition(A, p, r);    
33.         Hoare\_QuickSort(A, p, q-1);    
34.         Hoare\_QuickSort(A, q+1, r);    
35.     \}    
36. \}

a）
        A = {13 19 9 5 12 8 7 4 11 2 6 21}  
    ==> A = {6 19 9 5 12 8 7 4 11 2 13 21}  
    ==> A = {6 2 9 5 12 8 7 4 11 19 13 21}  
    ==> A = {4 2 9 5 12 8 7 6 11 19 13 21}  
    ==> A = {4 2 5 9 12 8 7 6 11 19 13 21}  
    ==> A = {2 4 5 9 12 8 7 6 11 19 13 21}  
    ==> A = {2 4 5 6 12 8 7 9 11 19 13 21}  
    ==> A = {2 4 5 6 7 8 12 9 11 19 13 21}  
    ==> A = {2 4 5 6 7 8 9 12 11 19 13 21}  
    ==> A = {2 4 5 6 7 8 9 12 11 13 19 21}
    b）
    int Hoare_Partition(int *A, int p, int r)  
    {  
        int x = A[p], i = p - 1, j = r + 1;  
        while(true)  
        {  
            do{j--;}  
            while(A[j] > x);  
            do{i++;}  
            while(A[i] < x);  
            if(i < j)  
                swap(A[i], A[j]);  
            else return j;  
            Print(A, 12);  
        }  
    }  
    void Hoare_QuickSort(int  *A, int p, int r)  
    {  
        if(p < r)  
        {  
            int q = Hoare_Partition(A, p, r);  
            Hoare_QuickSort(A, p, q-1);  
            Hoare_QuickSort(A, q+1, r);  
        }  
    }

## 7-3 Stooge排序 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  void Stooge\_Sort(int \*A, int i, int j)    
2.  \{    
3.      if(A\[i\] > A\[j\])    
4.          swap(A\[i\], A\[j\]);    
5.      if(i + 1 >= j)    
6.          return;    
7.      k = (j - i + 1) / 3;    
8.      Stooge\_Sort(A, i, j-k);    
9.      Stooge\_Sort(A, i+k, j);    
10.     Stooge\_Sort(A, i, j-k);    
11. \}  
12. 以下内容转http://blog.csdn.net/zhanglei8893    
13. a）对于数组A\[i...j\]，STOOGE-SORT算法将这个数组划分成均等的3份，分别用A, B, C表示。  
14.      第6-8步类似于冒泡排序的思想。它进行了两趟：  
15.      第一趟的第6-7步将最大的1/3部分交换到C  
16.      第二趟的第8步将除C外的最大的1/3部分交换到B  
17.      剩余的1/3位于A，这样的话整个数组A\[i...j\]就有序了。  
18. b）比较容易写出STOOGE-SORT最坏情况下的运行时间的递归式  
19.            T(n) = 2T(2n/3)+Θ(1)  
20.      由主定律可以求得T(n)=n^2.71  
21. c）各种排序算法在最坏情况下的运行时间分别为：  
22.     插入排序、快速排序：Θ(n^2)  
23.     堆排序、合并排序：Θ(nlgn)  
24.     相比于经典的排序算法，STOOGE-SORT算法具有非常差的性能，这几位终生教授只能说是浪得虚名了^\_^

void Stooge_Sort(int *A, int i, int j)  
    {  
        if(A[i] > A[j])  
            swap(A[i], A[j]);  
        if(i + 1 >= j)  
            return;  
        k = (j - i + 1) / 3;  
        Stooge_Sort(A, i, j-k);  
        Stooge_Sort(A, i+k, j);  
        Stooge_Sort(A, i, j-k);  
    }
    以下内容转http://blog.csdn.net/zhanglei8893
    a）对于数组A[i...j]，STOOGE-SORT算法将这个数组划分成均等的3份，分别用A, B, C表示。
         第6-8步类似于冒泡排序的思想。它进行了两趟：
         第一趟的第6-7步将最大的1/3部分交换到C
         第二趟的第8步将除C外的最大的1/3部分交换到B
         剩余的1/3位于A，这样的话整个数组A[i...j]就有序了。
    b）比较容易写出STOOGE-SORT最坏情况下的运行时间的递归式
               T(n) = 2T(2n/3)+Θ(1)
         由主定律可以求得T(n)=n^2.71
    c）各种排序算法在最坏情况下的运行时间分别为：
        插入排序、快速排序：Θ(n^2)
        堆排序、合并排序：Θ(nlgn)
        相比于经典的排序算法，STOOGE-SORT算法具有非常差的性能，这几位终生教授只能说是浪得虚名了^_^

## 7-4 快速排序中的堆栈深度 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a)  
2.  void QuickSort2(int \*A, int p, int r)  
3.  \{  
4.      while(p < r)  
5.      \{  
6.          int q = Partition(A, int p, r);  
7.          QuickSort2(A, p, q-1);  
8.          p = q + 1;  
9.      \}  
10. \}  
11.   
12. b)  
13. A = \{1, 2, 3, 4, 5, 6\}  
14. c)  
15. void QuickSort3(int \*A, int p, int r)  
16. \{  
17.     while(p < r)  
18.     \{  
19.         int q = Partition(A, int p, r);  
20.         if(r-q > q-p)  
21.         \{  
22.             QuickSort3(A, p, q-1);  
23.             p = q + 1;  
24.         \}  
25.         else  
26.         \{  
27.             QuickSort3(A, q+1, r);  
28.             r = q - 1;  
29.         \}  
30.     \}  
31. \}

a)
    void QuickSort2(int *A, int p, int r)
    {
    	while(p < r)
    	{
    		int q = Partition(A, int p, r);
    		QuickSort2(A, p, q-1);
    		p = q + 1;
    	}
    }
    
    b)
    A = {1, 2, 3, 4, 5, 6}
    c)
    void QuickSort3(int *A, int p, int r)
    {
    	while(p < r)
    	{
    		int q = Partition(A, int p, r);
    		if(r-q > q-p)
    		{
    			QuickSort3(A, p, q-1);
    			p = q + 1;
    		}
    		else
    		{
    			QuickSort3(A, q+1, r);
    			r = q - 1;
    		}
    	}
    }

## 7-5 “三数取中”划分 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  //三数取中   
2.  int GetMid(int \*A, int p, int r)  
3.  \{  
4.      int a = -1, b = -1, c = -1;  
5.      while(a < p)a = rand() % (r+1);  
6.      while(b < p)b = rand() % (r+1);  
7.      while(c < p)c = rand() % (r+1);  
8.      if((A\[a\]-A\[b\])\*(A\[a\]-A\[c\])<=0)return a;  
9.      if((A\[b\]-A\[a\])\*(A\[b\]-A\[c\])<=0)return b;  
10.     if((A\[c\]-A\[a\])\*(A\[c\]-A\[b\])<=0)return c;  
11. \}  
12. //划分   
13. int Partition(int \*A, int p, int r)  
14. \{  
15.     //选择A\[r\]作为主元   
16.     int m = GetMid(A, p , r);  
17.     swap(A\[m\], A\[r\]);  
18.     int x = A\[r\];  
19.     int i = p - 1, j;  
20.     bool flag = 0;  
21.     for(j = p; j < r; j++)  
22.     \{  
23.         //小于主元的放在左边   
24.         if(A\[j\] < x || (A\[j\] == x && flag))  
25.         \{  
26.             i++;  
27.             //把大于主元的交换到右边    
28.             swap(A\[i\],A\[j\]);  
29.             if(A\[j\] == x)flag = !flag;  
30.         \}  
31.     \}  
32.     swap(A\[i+1\], A\[r\]);  
33.     //返回最终主元的位置   
34.     return i+1;  
35. \}  
36. //快速排序   
37. void QuickSort(int \*A, int p, int r)  
38. \{  
39.     //长度小于k的子数组不排序   
40.     if(r > p)  
41.     \{  
42.         //以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大   
43.         int q = Partition(A, p, r);  
44.         //分别对左边和右边排序   
45.         QuickSort(A, p, q-1);  
46.         QuickSort(A, q+1, r);  
47.     \}  
48. \}

//三数取中
    int GetMid(int *A, int p, int r)
    {
    	int a = -1, b = -1, c = -1;
    	while(a < p)a = rand() % (r+1);
    	while(b < p)b = rand() % (r+1);
    	while(c < p)c = rand() % (r+1);
    	if((A[a]-A[b])*(A[a]-A[c])<=0)return a;
    	if((A[b]-A[a])*(A[b]-A[c])<=0)return b;
    	if((A[c]-A[a])*(A[c]-A[b])<=0)return c;
    }
    //划分
    int Partition(int *A, int p, int r)
    {
    	//选择A[r]作为主元
    	int m = GetMid(A, p , r);
    	swap(A[m], A[r]);
    	int x = A[r];
    	int i = p - 1, j;
    	bool flag = 0;
    	for(j = p; j < r; j++)
    	{
    		//小于主元的放在左边
    		if(A[j] < x || (A[j] == x && flag))
    		{
    			i++;
    			//把大于主元的交换到右边
    			swap(A[i],A[j]);
    			if(A[j] == x)flag = !flag;
    		}
    	}
    	swap(A[i+1], A[r]);
    	//返回最终主元的位置
    	return i+1;
    }
    //快速排序
    void QuickSort(int *A, int p, int r)
    {
    	//长度小于k的子数组不排序
    	if(r > p)
    	{
    		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
    		int q = Partition(A, p, r);
    		//分别对左边和右边排序
    		QuickSort(A, p, q-1);
    		QuickSort(A, q+1, r);
    	}
    }

## 7-6 对区间的模糊排序 ##

见[算法导论7-6对区间的模糊排序][7-6]

转载自：[http://blog.csdn.net/mishifangxiangdefeng/article/details/7675718][http_blog.csdn.net_mishifangxiangdefeng_article_details_7675718]

[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7675718#
[7-6]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7681109
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7675718]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7675718