C#數據結構與演算法系列(二十二):快速排序演算法(QuickSort)
- 2020 年 7 月 16 日
- 筆記
- C#數據結構和演算法
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.總結思想
簡而言之就是首先獲取數組的中間值 然後將中間值於兩邊的數據比較 如左邊的大於中間值或者右邊的小於中間值 那麼就替換
然後再進行左右兩邊遞歸