class Program
    {
        /// <summary>
        /// 对数组dataArray中索引从left到right之间的数做排序
        /// </summary>
        /// <param name="dataArray">要排序的数组</param>
        /// <param name="left">要排序数据的开始索引</param>
        /// <param name="right">要排序数据的结束索引</param>
        static void QuickSort(int[] dataArray, int left, int right) {
            if (left<right)
            {
                //基准数 把比他小或者等于他的 放在他的左边 ，然后把比他大的放在他的右边
                int x = dataArray[left];
                int i= left;
                int j = right;//用来做循环的标志位
                //当i==j的时候，说明我们找到了一个中间位置，这个中间位置就是基准数应该所在的位置
                while (true&&i<j)
                {
                    //从后往前比较（从右往左做比较）找一个比x小或者等于x的数字，放在我们的坑里（i的位置）
                    while (true && i < j)
                    {
                        if (dataArray[j] <= x)//如果小于或者等于基准数，把他放在x的左边
                        {
                            dataArray[i] = dataArray[j];
                            break;
                        }
                        else
                        {
                            j--;//向左移动到下一个数字，然后作比较
                        }
                    }
                    //从前往后（从左往右）找一个比x大的数字，放在我们的坑里（j的位置）
                    while (true && i < j)
                    {
                        if (dataArray[i] > x)
                        {
                            dataArray[j] = dataArray[i];
                            break;
                        }
                        else
                        {
                            i++;
                        }
                    }
                }
                //跳出循环，现在i==j i是中间位置
                dataArray[i] = x;//left-i-right
                QuickSort(dataArray,left,i-1);
                QuickSort(dataArray,i+1,right);
            }
        }


        static void Main(string[] args)
        {
            int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
            QuickSort(data,0,data.Length-1);
            foreach (var item in data)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }
    }
}