­

C#數據結構與演算法系列(二十二):快速排序演算法(QuickSort)

1 Introduction

Quicksort (QuickSort) is an improvement to bubble sorting. The basic idea is: split the data to be sorted into two independent parts by one sorting,

All of the data in one part is smaller than all the data in the other part, and then the two parts of the data are quickly sorted according to this method, and the entire sorting process can be recursive

In this way, the entire data becomes an ordered sequence

2. Schematic diagram

 

 

 

 3. Examples

Requirement: Sort [-9,78,0,23,-567,70] from largest to smallest

 

    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);
            }

        }
    }

Renderings

 4.總結思想

簡而言之就是首先獲取數組的中間值 然後將中間值於兩邊的數據比較 如左邊的大於中間值或者右邊的小於中間值 那麼就替換 

然後再進行左右兩邊遞歸