C#数据结构与算法系列（二十二）：快速排序算法（QuickSort）

    public  class QuickSort
    {
        public  static  void Test()
        {
            int [] arr = { -9 , 78 , 0 , 23 , -567 , 70 };

            Sort(arr, 0 , arr. Length- 1 );

            System.Console.WriteLine( string .Join( " , " , arr));
        }

        public  static  void   Sort( int [] arr, int left, int right)
        {
            int l = left;

            int r = right;

            // Middle value 
            int middle = arr[(l + r) / 2 ];

            // temp temporary variable 
            int temp = 0 ;

            // The purpose of the while loop is to put the value smaller than the middle value on the left and the value larger than the middle on the right 
            while (l< r)
            {
                // Look for the left side of the middle, and find the value greater than or equal to middle before exiting 
                while (arr[l]< middle)
                {
                    l ++ ;
                }
                // Always search on the right side of middle, and find the value less than or equal to middle before exiting 
                while (arr[r]> middle)
                {
                    r -= 1 ;
                }

                // If l>=denote the values ??on the left side of the middle, all the values ??on the left are less than or equal to the middle, and the values ??on the right are greater than the value of the middle 
                if (l>= r)
                {
                    break ;
                }

                // Exchange 

                temp = arr[l];

                arr[l] = arr[r];

                arr[r] = temp;

                // If the value of arr[l]==middle is found after the exchange, - move forward 
                if (arr[l]== middle)
                {
                    r -= 1 ;
                }

                // If the value of arr[r]==middle is found after the exchange, ++ shift back 
                if (arr[r]== middle)
                {
                    l ++ ;
                }

            }

            // If l==r, you must l++,r--, otherwise there will be a stack overflow 
            if (l== r)
            {
                l += 1 ;

                r -= 1 ;
            }

            // Recursion to the left 
            if (left< r)
            {
                Sort(arr, left, r);
            }

            // Recursive to the right 
            if (right> l)
            {
                Sort(arr, l, right);
            }

        }
    }