重温快速排序(r4笔记第73天)
说起排序，总是会想起大名鼎鼎的快速排序，等自己再次翻开快速排序时，感觉是很陌生的，从这个对比也能看出自己确实是已经忘记了曾经重要的日子。快速排序使用了分治思想，分而治之。为了达到它传说中较低的时间度，接受了来自大家多年的挑战还依然是名副其实的快速排序。一个简单的例子就是通过简单的实例来说明。我们假设一组数字如下：6,9,4,1,8,7,2,3,5我们假设以第一个数为参考，即temp为6，两边的数分别为i,j,从这组数的两边来比较这个中间变量，不断的移动下标，从右边开始寻找比temp小的数，从左边开始和寻找比temp大的数。在这个例子中就是以8为基本的参考，分别从这组数的右边，左边开始移动下标，寻找分别是小于6，大于6的节点。需要经过这么几轮的比较。第一轮，我们发现右边第一个节点5<6,就是它了，从左边开始，节点9>6,需要对这个两个节点进行对调。6,9,4,1,8,7,2,3,5变为6,5,4,1,8,7,2,3,96,5,4,1,8,7,2,3,96,5,4,1,3,7,2,8,96,5,4,1,3,7,2,8,96,5,4,1,3,2,7,8,96,5,4,1,3,2,7,8,92,5,4,1,3,6,7,8,95,4,1,31,4,5,31,2, 4,5,3 继续比较，拆分得到最后的结果。
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)
{
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找左边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最后分拆，得到两组数，对基准书进行重新初始化
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//处理左边的
quicksort(i+1,right);//处理右边的
}