快速排序法之分治法，挖坑填数法

解题思路:

注意事项:  法一 分治法注意事项   内循环的while(i<j&&nums[j]>=key)和while(i<j&&nums[i]<=key)  必须加等号

法二 挖坑填数法注意事项     最后是 nums[i]=key;
参考代码:

法一 分治法:

#include<iostream> 

#include<algorithm>

#include<vector>

using namespace std;

//利用基于范围的for循环可以快速打印容器元素

void print(vector<int> nums)

{

     for(auto i:nums)

     {

          cout<<i<<" ";

     }

}

void quickSort(vector<int>&nums,int left,int right)

{

if(left>=right) return;

int i=left;

int j=right,key=nums[left];

while(i!=j)

{

     while(i<j&&nums[j]>=key)

     {

             j--;

     }

     while(i<j&&nums[i]<=key)

     {

             i++;

     }

     swap(nums[i],nums[j]);

}

nums[left]=nums[i];

nums[i]=key; 

quickSort(nums,left,i-1);

quickSort(nums,i+1,right);

}

法二 挖坑填数法：

void quickSort2(vector<int>&nums,int left,int right)

{

if(left>=right) return;

int i=left,j=right,key=nums[left];

while(i<j)

{

     while(i<j&&nums[j]>=key)

     {

          j--;

     }

     if(i<j)

     {

         nums[i]=nums[j];

         i++;

     }

     while(i<j&&nums[i]<key)

     {

         i++;

     }

     if(i<j)

     {

         nums[j]=nums[i];

         j--;

     }

}

nums[i]=key;

quickSort2(nums,left,i-1);

quickSort2(nums,i+1,right);

}

int main()

{

     vector<int>nums;

     int n,x;

     cin>>n;

     while(n--)

     {

     cin>>x;

     nums.push_back(x);

}

quickSort(nums,0,nums.size()-1);

print(nums);

return 0;

}