快速排序

 1         /// <summary>
 2         /// 快速排序
 3         /// 原理：将数组分成两组，前面一组比后面一组小，然后前后两组依次再次划分，直到全部有序 [ref List<int> nums]
 4         /// </summary>
 5         /// <param name="nums">待排序数组</param>
 6         /// <param name="left">数组第一个数下标</param>
 7         /// <param name="right">数组总个数</param>
 8         public static int[] QuickSort(int[] nums, int left, int right)
 9         {
10             if (left < right)
11             {
12                 int i = left;
13                 int j = right - 1;
14                 int middle = nums[(left + right) / 2];  //找到数字中间值
15                 //[9 8 6 7 5 3 2 4 1 7]
16                 while (true)
17                 {
18                     while (i < right && nums[i] < middle) { i++; };  //左边的数小于中间的数，下标向右移
19                     while (j > 0 && nums[j] > middle) { j--; };      //左边的数大于右边的数，下标向左移
20                     if (i == j) break;
21                     nums[i] = nums[i] + nums[j];  //nums[i]、nums[j]交换
22                     nums[j] = nums[i] - nums[j];
23                     nums[i] = nums[i] - nums[j];
24                     if (nums[i] == nums[j]) j--;
25                 }
26                 QuickSort(nums, left, i);
27                 QuickSort(nums, i + 1, right);
28             }
29             return nums;
30         }
工欲善其事，必先利其器。