C/C++实现快速排序的方法
快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边。(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边。只是这次运气好,扔完一次刚好排整齐。)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果。——取自百度百科(链接)
C/C++实现:
voidquick_sort(int*a,intlow,inthigh){if(low>=high){ return; }intfirst=low;intlast=high;intkey=a[first];while(first<last){ while(first<last&&a[last]>=key){ --last; } a[first]=a[last]; while(first<last&&a[first]<=key){ ++first; } a[last]=a[first]; } a[first]=key; quick_sort(a,low,first-1); quick_sort(a,first+1,high); }