快速排序（Quick Sort）
首先我们思考一个问题：
给定一个整型数的无序序列，假设我取位置0处的值作为基准值，想要把这个无序序列变换为：在这个基准值左边的都比基准值小，在这个基准值右边的都比基准值大。
注：基准值左边的序列不一定是有序的，基准值右边的序列不一定是有序的。
如何做？
可以这么做：
遍历这个序列，将每个值都与基准值比较，比基准值大的都放在一个新的数组中保存，比基准值小的（或等于）都放在另外一个新的数组中保存。
在遍历完之后，再将对应的数据回置回去，即可。
上面的做法很好实现，但是效率很低。
下面看一个简单高效率的实现：
#include <stdio.h>
#include <stdlib.h>
/************************************************
* 函数名称：print_array
* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址
* 2.int n：一个int类型变量，指明数组大小
* 函数描述：输出数组中每个元素
* 返回值 ：void
* Author ：test1280
* History ：2017/04/14
* *********************************************/
void print_array(int *parray, int n)
{
int i;
for (i=0; i<n; i++)
{
printf("%d ", parray[i]);
}
printf("\n");
}
/************************************************
* 函数名称：onceSort
* 参数列表：1.int *array:一个int类型指针，指向一个数组首地址
* 2.int arrayLeft:左下标
* 3.int arrayRight:右下标
* 函数描述：对一个序列进行变换，以left作为基准值，基准值左边的都比基准值小，基准值右边的都比基准值大
* 返回值 ：一个int类型数据，代表left(实际此时left与right值相等)
* Author ：test1280
* History : 2017/04/14
* *********************************************/
int onceSort(int *array, int arrayLeft, int arrayRight)
{
int left=arrayLeft, right=arrayRight;
int basePos = left;
int tmp;
while (left<right)
{
while (left<right && array[right]>=array[basePos])
right--;
printf("-------------------------------------\n");
printf("before swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
tmp = array[right];
array[right] = array[basePos];
array[basePos] = tmp;
basePos = right;
printf("after swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
while (left<right && array[left]<=array[basePos])
left++;
printf("-------------------------------------\n");
printf("before swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
tmp = array[left];
array[left] = array[basePos];
array[basePos] = tmp;
basePos = left;
printf("after swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
return left;
}
int main()
{
int array[8] = {49, 38, 65, 97, 76, 13, 27, 49};
print_array(array, 8);
onceSort(array, 0, 7);
print_array(array, 8);
return 0;
}
额，思路只要看看还是简单的。
输出如下：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before swap...left=0;right=6;basePos=0
49 38 65 97 76 13 27 49
after swap...left=0;right=6;basePos=6
27 38 65 97 76 13 49 49
-------------------------------------
-------------------------------------
before swap...left=2;right=6;basePos=6
27 38 65 97 76 13 49 49
after swap...left=2;right=6;basePos=2
27 38 49 97 76 13 65 49
-------------------------------------
-------------------------------------
before swap...left=2;right=5;basePos=2
27 38 49 97 76 13 65 49
after swap...left=2;right=5;basePos=5
27 38 13 97 76 49 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=5;basePos=5
27 38 13 97 76 49 65 49
after swap...left=3;right=5;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
after swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
after swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
27 38 13 49 76 97 65 49
[test1280@localhost sort]$
可以看到，我选择的是left的位置的值作为基准值，那么例子中就是49，输出结果中可以看到位置3处的值是49，位置3之前的序列都不比49大，位置3之后的序列都不比49小。
思路是这样子：
首先要有一个基准值，就以最左边的值（left）作为基准值吧。
然后从右边进行查找，查找一个值比基准值小的，就把它与基准值进行交换。
然后从左边进行查找，查找一个值比基准值大的，就把它与基准值进行交换。
依次类推，直到left与right相等。
这个时候再来看这个序列，就符合我们最开始的需求了。
所谓快速排序，其实就是 分治算法 + 我们之前的需求 所组合起来的。
经过我们上面的程序的变换，其中的基准值一定可以在
当前序列范围内找到一个确定的位置，这个位置也就是最后排好序的位置。
我们可以将左边的和右边的再进行递归处理，这不就是分治吗？只要左边和右边都是有序的，那么整个当前序列范围都是有序的。
请看下面的代码：
#include <stdio.h>
#include <stdlib.h>
/************************************************
* 函数名称：print_array
* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址
* 2.int n：一个int类型变量，指明数组大小
* 函数描述：输出数组中每个元素
* 返回值 ：void
* Author ：test1280
* History ：2017/04/14
* *********************************************/
void print_array(int *parray, int n)
{
int i;
for (i=0; i<n; i++)
{
printf("%d ", parray[i]);
}
printf("\n");
}
/************************************************
* 函数名称：onceSort
* 参数列表：1.int *array:一个int类型指针，指向一个数组首地址
* 2.int arrayLeft:左下标
* 3.int arrayRight:右下标
* 函数描述：对一个序列进行变换，以left作为基准值，基准值左边的都比基准值小，基准值右边的都比基准值大
* 返回值 ：一个int类型数据，代表left(实际此时left与right值相等)
* Author ：test1280
* History : 2017/04/14
* *********************************************/
int onceSort(int *array, int arrayLeft, int arrayRight)
{
int left=arrayLeft, right=arrayRight;
int basePos = left;
int tmp;
while (left<right)
{
while (left<right && array[right]>=array[basePos])
right--;
printf("-------------------------------------\n");
printf("before swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
tmp = array[right];
array[right] = array[basePos];
array[basePos] = tmp;
basePos = right;
printf("after swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
while (left<right && array[left]<=array[basePos])
left++;
printf("-------------------------------------\n");
printf("before swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
tmp = array[left];
array[left] = array[basePos];
array[basePos] = tmp;
basePos = left;
printf("after swap...left=%d;right=%d;basePos=%d\n", left, right, basePos);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
return left;
}
/**********************************************************
* 函数名称：QuickSort
* 参数列表：1.int *array：指向数组首地址的指针；
* 2.int arrayLeft：左下标；
* 3.int arrayRight：右下标；
* 函数描述：快速排序
* 返回值 ：void
* Author : test1280
* History : 2017/04/14
* ********************************************************/
void QuickSort(int *array, int arrayLeft, int arrayRight)
{
if (arrayLeft<arrayRight)
{
int pos = onceSort(array, arrayLeft, arrayRight);
QuickSort(array, arrayLeft, pos-1);
QuickSort(array, pos+1, arrayRight);
}
}
int main()
{
int array[8] = {49, 38, 65, 97, 76, 13, 27, 49};
print_array(array, 8);
QuickSort(array, 0, 7);
print_array(array, 8);
return 0;
}
输出：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before swap...left=0;right=6;basePos=0
49 38 65 97 76 13 27 49
after swap...left=0;right=6;basePos=6
27 38 65 97 76 13 49 49
-------------------------------------
-------------------------------------
before swap...left=2;right=6;basePos=6
27 38 65 97 76 13 49 49
after swap...left=2;right=6;basePos=2
27 38 49 97 76 13 65 49
-------------------------------------
-------------------------------------
before swap...left=2;right=5;basePos=2
27 38 49 97 76 13 65 49
after swap...left=2;right=5;basePos=5
27 38 13 97 76 49 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=5;basePos=5
27 38 13 97 76 49 65 49
after swap...left=3;right=5;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
after swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
-------------------------------------
before swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
after swap...left=3;right=3;basePos=3
27 38 13 49 76 97 65 49
-------------------------------------
-------------------------------------
before swap...left=0;right=2;basePos=0
27 38 13
after swap...left=0;right=2;basePos=2
13 38 27
-------------------------------------
-------------------------------------
before swap...left=1;right=2;basePos=2
13 38 27
after swap...left=1;right=2;basePos=1
13 27 38
-------------------------------------
-------------------------------------
before swap...left=1;right=1;basePos=1
13 27 38
after swap...left=1;right=1;basePos=1
13 27 38
-------------------------------------
-------------------------------------
before swap...left=1;right=1;basePos=1
13 27 38
after swap...left=1;right=1;basePos=1
13 27 38
-------------------------------------
-------------------------------------
before swap...left=4;right=7;basePos=4
76 97 65 49
after swap...left=4;right=7;basePos=7
49 97 65 76
-------------------------------------
-------------------------------------
before swap...left=5;right=7;basePos=7
49 97 65 76
after swap...left=5;right=7;basePos=5
49 76 65 97
-------------------------------------
-------------------------------------
before swap...left=5;right=6;basePos=5
49 76 65 97
after swap...left=5;right=6;basePos=6
49 65 76 97
-------------------------------------
-------------------------------------
before swap...left=6;right=6;basePos=6
49 65 76 97
after swap...left=6;right=6;basePos=6
49 65 76 97
-------------------------------------
-------------------------------------
before swap...left=4;right=4;basePos=4
49 65
after swap...left=4;right=4;basePos=4
49 65
-------------------------------------
-------------------------------------
before swap...left=4;right=4;basePos=4
49 65
after swap...left=4;right=4;basePos=4
49 65
-------------------------------------
13 27 38 49 49 65 76 97
在QuickSort中，首先onceSort下，确定了一个基准值的最后位置，然后只需要两侧再进行QuickSort排好序，那不就是最后我们想要的从小到大的结果了？
其实这里还是可以小小地优化一下，其实onceSort每次并不总是需要移动一下，只是在最后才能确定基准值最后的位置，不必要每次移动来移动去的。
看如下代码：
#include <stdio.h>
#include <stdlib.h>
/************************************************
* 函数名称：print_array
* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址
* 2.int n：一个int类型变量，指明数组大小
* 函数描述：输出数组中每个元素
* 返回值 ：void
* Author ：test1280
* History ：2017/04/14
* *********************************************/
void print_array(int *parray, int n)
{
int i;
for (i=0; i<n; i++)
{
printf("%d ", parray[i]);
}
printf("\n");
}
/************************************************
* 函数名称：onceSort
* 参数列表：1.int *array:一个int类型指针，指向一个数组首地址
* 2.int arrayLeft:左下标
* 3.int arrayRight:右下标
* 函数描述：对一个序列进行变换，以left作为基准值，基准值左边的都比基准值小，基准值右边的都比基准值大
* 返回值 ：一个int类型数据，代表left(实际此时left与right值相等)
* Author ：test1280
* History : 2017/04/14
* *********************************************/
int onceSort(int *array, int arrayLeft, int arrayRight)
{
int left=arrayLeft, right=arrayRight;
int baseVal = array[left];
while (left<right)
{
//每次循环时，left总是一个坑，可以被填入值
while (left<right && array[right]>=baseVal)
right--;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[left] = array[right];
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
//到此时，right总是一个坑，可以被填入值
while (left<right && array[left]<=baseVal)
left++;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[right] = array[left];
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
array[left] = baseVal;
return left;
}
/**********************************************************
* 函数名称：QuickSort
* 参数列表：1.int *array：指向数组首地址的指针；
* 2.int arrayLeft：左下标；
* 3.int arrayRight：右下标；
* 函数描述：快速排序
* 返回值 ：void
* Author : test1280
* History : 2017/04/14
* ********************************************************/
void QuickSort(int *array, int arrayLeft, int arrayRight)
{
if (arrayLeft<arrayRight)
{
int pos = onceSort(array, arrayLeft, arrayRight);
QuickSort(array, arrayLeft, pos-1);
QuickSort(array, pos+1, arrayRight);
}
}
int main()
{
int array[8] = {49, 38, 65, 97, 76, 13, 27, 49};
print_array(array, 8);
QuickSort(array, 0, 7);
print_array(array, 8);
return 0;
}
输出：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before move...left=0;right=6;
49 38 65 97 76 13 27 49
after move...left=0;right=6;
27 38 65 97 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=2;right=6;
27 38 65 97 76 13 27 49
after move...left=2;right=6;
27 38 65 97 76 13 65 49
-------------------------------------
-------------------------------------
before move...left=2;right=5;
27 38 65 97 76 13 65 49
after move...left=2;right=5;
27 38 13 97 76 13 65 49
-------------------------------------
-------------------------------------
before move...left=3;right=5;
27 38 13 97 76 13 65 49
after move...left=3;right=5;
27 38 13 97 76 97 65 49
-------------------------------------
-------------------------------------
before move...left=3;right=3;
27 38 13 97 76 97 65 49
after move...left=3;right=3;
27 38 13 97 76 97 65 49
-------------------------------------
-------------------------------------
before move...left=3;right=3;
27 38 13 97 76 97 65 49
after move...left=3;right=3;
27 38 13 97 76 97 65 49
-------------------------------------
-------------------------------------
before move...left=0;right=2;
27 38 13
after move...left=0;right=2;
13 38 13
-------------------------------------
-------------------------------------
before move...left=1;right=2;
13 38 13
after move...left=1;right=2;
13 38 38
-------------------------------------
-------------------------------------
before move...left=1;right=1;
13 38 38
after move...left=1;right=1;
13 38 38
-------------------------------------
-------------------------------------
before move...left=1;right=1;
13 38 38
after move...left=1;right=1;
13 38 38
-------------------------------------
-------------------------------------
before move...left=4;right=7;
76 97 65 49
after move...left=4;right=7;
49 97 65 49
-------------------------------------
-------------------------------------
before move...left=5;right=7;
49 97 65 49
after move...left=5;right=7;
49 97 65 97
-------------------------------------
-------------------------------------
before move...left=5;right=6;
49 97 65 97
after move...left=5;right=6;
49 65 65 97
-------------------------------------
-------------------------------------
before move...left=6;right=6;
49 65 65 97
after move...left=6;right=6;
49 65 65 97
-------------------------------------
-------------------------------------
before move...left=4;right=4;
49 65
after move...left=4;right=4;
49 65
-------------------------------------
-------------------------------------
before move...left=4;right=4;
49 65
after move...left=4;right=4;
49 65
-------------------------------------
13 27 38 49 49 65 76 97
[test1280@localhost sort]$
相比之前的实现，只是在最开始保存了基准值，然后在进入循环之前基准值的位置就是一个坑，可以被填入右侧的比基准值小的数据，然后右侧的那个数据所在的位置就是一个坑，可以被填入左边的比基准值大的数据……直到left=right，遍历完全部元素。此时，left=right，这个位置填入基准值即可。
如果从大到小排序，只需要修改下条件：
//每次循环时，left总是一个坑，可以被填入值
while (left<right && array[right]<=baseVal)
right--;
……
//到此时，right总是一个坑，可以被填入值
while (left<right && array[left]>=baseVal)
left++;
……
97 76 65 49 49 38 27 13
[test1280@localhost sort]$
那个基准值如果通用一些，不选用left处的值，可以吗？
请看：
#include <stdio.h>
#include <stdlib.h>
/************************************************
* 函数名称：print_array
* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址
* 2.int n：一个int类型变量，指明数组大小
* 函数描述：输出数组中每个元素
* 返回值 ：void
* Author ：test1280
* History ：2017/04/14
* *********************************************/
void print_array(int *parray, int n)
{
int i;
for (i=0; i<n; i++)
{
printf("%d ", parray[i]);
}
printf("\n");
}
/************************************************
* 函数名称：onceSort
* 参数列表：1.int *array:一个int类型指针，指向一个数组首地址
* 2.int arrayLeft:左下标
* 3.int arrayRight:右下标
* 函数描述：对一个序列进行变换，以left作为基准值，基准值左边的都比基准值小，基准值右边的都比基准值大
* 返回值 ：一个int类型数据，代表left(实际此时left与right值相等)
* Author ：test1280
* History : 2017/04/14
* *********************************************/
int onceSort(int *array, int arrayLeft, int arrayRight)
{
int left=arrayLeft, right=arrayRight;
int holePos = (left + right)/2;
int baseVal = array[holePos];
while (left<right)
{
while (left<right && array[right]>=baseVal)
right--;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[holePos] = array[right];
holePos = right;
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
while (left<right && array[left]<=baseVal)
left++;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[holePos] = array[left];
holePos = left;
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
array[left] = baseVal;
return left;
}
/**********************************************************
* 函数名称：QuickSort
* 参数列表：1.int *array：指向数组首地址的指针；
* 2.int arrayLeft：左下标；
* 3.int arrayRight：右下标；
* 函数描述：快速排序
* 返回值 ：void
* Author : test1280
* History : 2017/04/14
* ********************************************************/
void QuickSort(int *array, int arrayLeft, int arrayRight)
{
if (arrayLeft<arrayRight)
{
int pos = onceSort(array, arrayLeft, arrayRight);
QuickSort(array, arrayLeft, pos-1);
QuickSort(array, pos+1, arrayRight);
}
}
int main()
{
int array[8] = {49, 38, 65, 97, 76, 13, 27, 49};
print_array(array, 8);
QuickSort(array, 0, 7);
print_array(array, 8);
return 0;
}
这里的基准值选择的是left与right中间的那个值，输出如下：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before move...left=0;right=7;
49 38 65 97 76 13 27 49
after move...left=0;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=7;right=7;
49 38 65 49 76 13 27 49
after move...left=7;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=0;right=6;
49 38 65 49 76 13 27
after move...left=0;right=6;
49 38 65 27 76 13 27
-------------------------------------
-------------------------------------
before move...left=2;right=6;
49 38 65 27 76 13 27
after move...left=2;right=6;
49 38 65 27 76 13 65
-------------------------------------
-------------------------------------
before move...left=2;right=5;
49 38 65 27 76 13 65
after move...left=2;right=5;
49 38 13 27 76 13 65
-------------------------------------
-------------------------------------
before move...left=4;right=5;
49 38 13 27 76 13 65
after move...left=4;right=5;
49 38 13 27 76 76 65
-------------------------------------
-------------------------------------
before move...left=4;right=4;
49 38 13 27 76 76 65
after move...left=4;right=4;
49 38 13 27 76 76 65
-------------------------------------
-------------------------------------
before move...left=4;right=4;
49 38 13 27 76 76 65
after move...left=4;right=4;
49 38 13 27 76 76 65
-------------------------------------
-------------------------------------
before move...left=0;right=3;
49 38 13 27
after move...left=0;right=3;
49 27 13 27
-------------------------------------
-------------------------------------
before move...left=0;right=3;
49 27 13 27
after move...left=0;right=3;
49 27 13 49
-------------------------------------
-------------------------------------
before move...left=0;right=2;
49 27 13 49
after move...left=0;right=2;
13 27 13 49
-------------------------------------
-------------------------------------
before move...left=2;right=2;
13 27 13 49
after move...left=2;right=2;
13 27 13 49
-------------------------------------
-------------------------------------
before move...left=0;right=0;
13 27
after move...left=0;right=0;
13 27
-------------------------------------
-------------------------------------
before move...left=0;right=0;
13 27
after move...left=0;right=0;
13 27
-------------------------------------
-------------------------------------
before move...left=5;right=6;
76 65
after move...left=5;right=6;
65 65
-------------------------------------
-------------------------------------
before move...left=6;right=6;
65 65
after move...left=6;right=6;
65 65
-------------------------------------
13 27 38 49 49 65 76 97
[test1280@localhost sort]$
当然，你可以选取其他的值（一定要是合理的~），但都不会影响最后的排序结果。
这么来看太复杂了，可以将main中的QuickSort修改为onceSort，输出如下：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before move...left=0;right=7;
49 38 65 97 76 13 27 49
after move...left=0;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=7;right=7;
49 38 65 49 76 13 27 49
after move...left=7;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
49 38 65 49 76 13 27 97
第一次 一次排序，（0+7）/2 = 3，3处的值是基准值，即97,；
一开始把末尾的49填写到了97所在的位置；然后发现左下标移动直接到了倒数第二个的位置；
最后把97填写到最后的位置（left与right指向的位置）。
问：能不能不从右边开始查找呢？从左边开始查找？
#include <stdio.h>
#include <stdlib.h>
/************************************************
* 函数名称：print_array
* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址
* 2.int n：一个int类型变量，指明数组大小
* 函数描述：输出数组中每个元素
* 返回值 ：void
* Author ：test1280
* History ：2017/04/14
* *********************************************/
void print_array(int *parray, int n)
{
int i;
for (i=0; i<n; i++)
{
printf("%d ", parray[i]);
}
printf("\n");
}
/************************************************
* 函数名称：onceSort
* 参数列表：1.int *array:一个int类型指针，指向一个数组首地址
* 2.int arrayLeft:左下标
* 3.int arrayRight:右下标
* 函数描述：对一个序列进行变换，以left作为基准值，基准值左边的都比基准值小，基准值右边的都比基准值大
* 返回值 ：一个int类型数据，代表left(实际此时left与right值相等)
* Author ：test1280
* History : 2017/04/14
* *********************************************/
int onceSort(int *array, int arrayLeft, int arrayRight)
{
int left=arrayLeft, right=arrayRight;
int holePos = (left + right)/2;
int baseVal = array[holePos];
while (left<right)
{
while (left<right && array[left]<=baseVal)
left++;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[holePos] = array[left];
holePos = left;
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
while (left<right && array[right]>=baseVal)
right--;
printf("-------------------------------------\n");
printf("before move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
array[holePos] = array[right];
holePos = right;
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
array[left] = baseVal;
return left;
}
/**********************************************************
* 函数名称：QuickSort
printf("after move...left=%d;right=%d;\n", left, right);
print_array(array+arrayLeft, arrayRight-arrayLeft+1);
printf("-------------------------------------\n\n");
}
array[left] = baseVal;
return left;
}
/**********************************************************
* 函数名称：QuickSort
* 参数列表：1.int *array：指向数组首地址的指针；
* 2.int arrayLeft：左下标；
* 3.int arrayRight：右下标；
* 函数描述：快速排序
* 返回值 ：void
* Author : test1280
* History : 2017/04/14
* ********************************************************/
void QuickSort(int *array, int arrayLeft, int arrayRight)
{
if (arrayLeft<arrayRight)
{
int pos = onceSort(array, arrayLeft, arrayRight);
QuickSort(array, arrayLeft, pos-1);
QuickSort(array, pos+1, arrayRight);
}
}
int main()
{
int array[8] = {49, 38, 65, 97, 76, 13, 27, 49};
print_array(array, 8);
QuickSort(array, 0, 7);
print_array(array, 8);
return 0;
}
结果输出为：
[test1280@localhost sort]$ ./main
49 38 65 97 76 13 27 49
-------------------------------------
before move...left=7;right=7;
49 38 65 97 76 13 27 49
after move...left=7;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=7;right=7;
49 38 65 49 76 13 27 49
after move...left=7;right=7;
49 38 65 49 76 13 27 49
-------------------------------------
-------------------------------------
before move...left=2;right=6;
49 38 65 49 76 13 27
after move...left=2;right=6;
49 38 65 65 76 13 27
-------------------------------------
-------------------------------------
before move...left=2;right=6;
49 38 65 65 76 13 27
after move...left=2;right=6;
49 38 27 65 76 13 27
-------------------------------------
-------------------------------------
before move...left=3;right=6;
49 38 27 65 76 13 27
after move...left=3;right=6;
49 38 27 65 76 13 65
-------------------------------------
-------------------------------------
before move...left=3;right=5;
49 38 27 65 76 13 65
after move...left=3;right=5;
49 38 27 13 76 13 65
-------------------------------------
-------------------------------------
before move...left=4;right=5;
49 38 27 13 76 13 65
after move...left=4;right=5;
49 38 27 13 76 76 65
-------------------------------------
-------------------------------------
before move...left=4;right=4;
49 38 27 13 76 76 65
after move...left=4;right=4;
49 38 27 13 76 76 65
-------------------------------------
-------------------------------------
before move...left=0;right=3;
49 38 27 13
after move...left=0;right=3;
49 49 27 13
-------------------------------------
-------------------------------------
before move...left=0;right=3;
49 49 27 13
after move...left=0;right=3;
13 49 27 13
-------------------------------------
-------------------------------------
before move...left=1;right=3;
13 49 27 13
after move...left=1;right=3;
13 49 27 49
-------------------------------------
-------------------------------------
before move...left=1;right=2;
13 49 27 49
after move...left=1;right=2;
13 27 27 49
-------------------------------------
-------------------------------------
before move...left=2;right=2;
13 27 27 49
after move...left=2;right=2;
13 27 27 49
-------------------------------------
-------------------------------------
before move...left=2;right=2;
13 27 27 49
after move...left=2;right=2;
13 27 27 49
-------------------------------------
-------------------------------------
before move...left=1;right=1;
13 27
after move...left=1;right=1;
27 27
-------------------------------------
-------------------------------------
before move...left=1;right=1;
27 27
after move...left=1;right=1;
27 27
-------------------------------------
-------------------------------------
before move...left=6;right=6;
76 65
after move...left=6;right=6;
65 65
-------------------------------------
-------------------------------------
before move...left=6;right=6;
65 65
after move...left=6;right=6;
65 65
-------------------------------------
27 13 38 49 49 65 76 97
[test1280@localhost sort]$
很明显有问题~
哪里错了呢？仔细思考下，后续补充。
（PS：第一次交换时，发现97时基准值，直到最后left就变成了7，然后直接将位置7处的值放置在holePos处，合适吗？当然不合适。。比较都不比较直接交换当然不合适。）
总结思考：
1.基本的快速排序原理；
2.基准值的选取（PS：(right+left)/2会不会对边界值造成某些影响？可以这么选取吗？思考ing）；
3.从左边开始搜索；
