快速排序法

操作

1.用Partition()函数取得划分数，严的教材该数选的是数组第一个数。

2.将小于划分树的左侧放小于它的数，在右边放比它大的数。此时划分数的位置不需移动，就为它的排序完成后的位置。

3.将划分数的左侧数组和右侧数组分别迭代，直到左右数组为空或者为1。

代码

划分算法

//划分区域返回划分点的最终位置
        public int Partition(int[] s,int low, int high)
        {
            //选数组的第一个点为划分点
            int pos=s[low];
            while(low<high)
            {
                //划分大于划分点区域
                while(s[high]>=pos&&low<high) --high;
                s[low]=s[high];
                //此时high可被覆盖，因为已被赋值到low中
                while(s[low]<=pos&&low<high) ++low;
                s[high]=s[low];
            }
            s[low]=pos;
            return low;
        }

返回值：low(为最终划分数的位置)

迭代排序

//递归方式
        public void RecursiveQSott(int[] s,int low,int high)
        {
            if(low<high)
            {
                int pivotpos=Partition(s,low,high);
                //对小于部分区域排序
                RecursiveQSott(s,low,pivotpos-1);
                 //对大于部分区域排序
                RecursiveQSott(s,pivotpos+1,high);
            }
        }