No.1.3 排序 - 快速排序

一、作为C++编程小白，有必要简单分析、记录下，快速排序算法的实现，以便后续复习：

#include

int a[101], n; //定义全局变量，并在子函数中使用

void quicksort(int left, int right)
{
　　int i, j, t, temp;

　　if (left >= right)
　　　　return;

　　temp = a[left]; //temp中存储基准数

　　i = left;
　　j = right;

　　while(i != j){ //其实应该是 i 　　　　//顺序很重要，要先从右往左找
　　　　while(a[j] >= temp && i 　　　　　　j--;
　　　　//再从左往右找
　　　　while(a[i] <= temp && i 　　　　　　i++;

　　　　// i,j 找到数组中对应数据时，交换位置
　　　　if (i 　　　　　　t = a[i]; a[i]=a[j]; a[j]=t;
　　　　}
　　}

　　//当i=j,即 i/j 相遇时，将基准数归位：left <-> i
　　a[left] = a[i];
　　a[i] = temp;

　　//递归
　　quicksort(left, i-1);
　　quicksort(i+1,right);
}

int main(){
　　int i,j,n;
　　scanf("%d",&n);
　　for (i=1; i<=n; i++){
　　　　scanf("%d",&a[i]);
　　}
　　quicksort(1,n);

　　for (i=1; i<=n; i++){
　　　　printf("%d ",a[i]);
　　}
　　return 0;
}

/* quicksort()

　　1.首先给定参数：列表的左右边缘索引，毕竟你用的列表中那些位置，只有你自己知道；

　　2.如果 left>right，纯属开个玩笑；

　　3.如果left < right，对应 while(i!=j)，这时候，a[left]为基准数，i,j还没相遇，于是可以直接调换 a[i], a[j]

　　4.如果left = right，有两种情况：都是为了让基准数归位

　　a.从right出发的 j 找到了比基准数小的值 a[j]，然后 i 还没找到比 temp 大的值就遇到了 j（i++ = j），不好意思了，把 a[i]==a[j]和基准数对调，使之归位

　　b. j 还没找到比基准数小的值 a[j]（此时a[j] > temp），就遇到了 第三步中交换之后的 a[i] (j-- = i)，那么不好意思了，还是把a[i]和基准数对调，使之归位（a[i]/a[j--] 比 temp 小）

　　5.基准数归位以后呢，位置是 a[i]，左边是比它小的 (left, i-1),右边是比它大的 (i+1, right)，没啥好说的，递归呗

*/

二、稍作修改，引入struct student，即可实现”对学生以分数进行的排名”，太懒了，不写了