快速排序

1. 先找一个基准数base，通常选择最左边（）或者最右边（）

2. 找到这个基准数在数组中的位置(从小到大排序)

a. 两个flag，一个从最左端开始（flag_low = left）,一个从最右端开始(flag_high = right)，一个向右，一个向左，直到两个flag相遇
b. 如果nums[low] <= base ，则代表nums[low]的位置合理--> low++，继续向右寻找;
c. 如果nums[high] >= base，则代表nums[high]的位置合理--> high--，继续向左寻找;
：如果基准数是nums[left]， 则从high-- 开始，如果基准数是nums[right]，则从left++开始
d. 当两个flag都到达不符合的位置，则交换low high指向的值
e. 当两个flag相遇时，就到了基准数应该在的位置，nums[flag_high] = base;

3. 调用递归，分别对基准数左边[ left, flag-1 ]和基准数右边[ flag+1, right ]的数组进行排序

以数组最左边为基准数：nums[left]

 void quickSort (int left, int right, vector<int>& nums) {
     if (left >= right)  return;
     // find base num
     int base = nums[left];
     // two flags. flag_low & flag_high
     int flag_low = left;
     int flag_high = right;
     while (flag_low < flag_high) {
         while (nums[flag_high] >= base && flag_low < flag_high) {
             flag_high--;
         }
         while (nums[flag_low] <= base && flag_low < flag_high) {
             flag_low++;
         }
         if (flag_low < flag_high) {
             int tmp = nums[flag_low];
             nums[flag_low] =  nums[flag_high];
             nums[flag_high] = tmp;
        }
     }
     nums[left] = nums[flag_low];
     int flag = flag_high;
     nums[flag] = base;  //flag_high = flag_low;

     //递归
     quickSort(left, flag-1, nums);
     quickSort(flag+1, right, nums);
}

以数组最右边为基准数：nums[right]

 void quickSort (int left, int right, vector<int>& nums) {
     if (left >= right)  return;
     // find base num
     int base = nums[right];
     // two flags. flag_low & flag_high
     int flag_low = left;
     int flag_high = right;
     while (flag_low < flag_high) {
         while (nums[flag_low] <= base && flag_low < flag_high) {
             flag_low++;
         }
         while (nums[flag_high] >= base && flag_low < flag_high) {
             flag_high--;
         }
         if (flag_low < flag_high) {
             int tmp = nums[flag_low];
             nums[flag_low] =  nums[flag_high];
             nums[flag_high] = tmp;
        }
     }
     int flag = flag_high;
     nums[right] = nums[flag];
     nums[flag] = base;  //flag_high = flag_low;

     //递归
     quickSort(left, flag-1, nums);
     quickSort(flag+1, right, nums);
}

以左边为基准，返回从大到小排序结果

void quickSort (int left, int right, vector<int>& nums) {
     if (left >= right)  return;
     // find base num
     int base = nums[left];
     // two flags. flag_low & flag_high
     int flag_low = left;
     int flag_high = right;
     while (flag_low < flag_high) {
         while (nums[flag_high] <= base && flag_low < flag_high) {
             flag_high--;
         }
         while (nums[flag_low] >= base && flag_low < flag_high) {
             flag_low++;
         }
         if (flag_low < flag_high) {
             int tmp = nums[flag_low];
             nums[flag_low] =  nums[flag_high];
             nums[flag_high] = tmp;
        }
     }
     int flag = flag_high;
     nums[left] = nums[flag];
     nums[flag] = base;  //flag_high = flag_low;

     //递归
     quickSort(left, flag-1, nums);
     quickSort(flag+1, right, nums);
}

1. 排序算法是稳定的吗？
   不稳定
   排序算法的稳定性是说，如果在数组中，存在a[i] = a[j]，那在排序的过程中，如果a[i]和a[j]的前后顺序不会发生改变，则代表它是稳定的；如果顺序会发生改变，则不稳定。
2. 排序算法的时间复杂度
   最坏：O（N^2），平均复杂度是O（N*log(N)）
   完成一次遍历的复杂度是N，需要遍历的次数，最多是N，最少是log(N)