C语言训练-排序问题<1> （C语言代码）快速排序

解题思路:

解题思路在代码的注释里。

注意事项:

参考代码:

#include <stdio.h>

#include <string.h>

void quickSort(int a[], int p, int r);

int partition(int a[], int p, int r);

int main()

{

int a[4];

//输入数组

for (int i = 0; i < 4; i++)

{

scanf("%d", &a[i]);

}

//快速排序

quickSort(a, 0, 3);

//输出排序后的结果：

for (int i = 0; i < 4; i++)

{

if (i == 0)

{

printf("%d", a[i]);

}

else {

printf(" %d", a[i]);

}

}

printf("\n");

system("pause");

return 0;

}

void quickSort(int a[], int p, int r)  //p是待操作的那段数组最左元素下标，

{                                      //r是待操作的那段数组最右元素下标。

if (p < r)

{

int q = partition(a, p, r);   //找标杆

quickSort(a, p, q - 1);       //标杆左边

quickSort(a, q + 1, r);       //标杆右边

}

}

int partition(int a[], int p, int r)

{

int i = p, j = r + 1;              //1、初始化i和j。i指向数组第一个元素，j指向数组最后一个元素的后一位。

int x = a[p];                      //2、第一个元素是标杆，暂存在x

while (1)                        //3、i往右走找到比标杆小的元素，j往左走找到比标杆大的元素。

{

while (a[++i] < x&&i < r);  //3.1、i先走，++i即从除标杆外的第一个元素，即待操作那段数组的第二个元素开始。一直往右走，直到找到比标杆x大的元素。

while (a[--j] > x);         //3.2、j再走，--j即从待操作那段数组的最后一个元素开始。一直往左走，直到找比标杆x小的元素。

if (i >= j)                 //如果i和j位置重合，或者j走到了i前面，则跳出循环

{

break;

}

//4、如果i<j，则交换a[i]和a[j]两个元素的位置。然后重复3.1和3.2。

a[i] ^= a[j];

a[j] ^= a[i];

a[i] ^= a[j];

}

//5、如果i>=j,则跳出while循环，即i和j停止查找。a[p]和a[j]交换，即把比标杆小的数放在刚刚操作的那段数组的第一位置，将标杆x放到刚刚操作的那段数组的中间位置，并返回标杆下标。

a[p] = a[j];      

a[j] = x;        

return j;

}