排序（2）
我们在排序（1）中说到选择排序的代码：
void SelectSort(int* a,int n)
{
int begin=0,end=n-1;
int mini=begin,max=begin;
for(int i=begin+1;i<=end;i++)
{
if(a[i]>a[max])
{
maxi=i;
}
if(a[i]<a[mini])
{
mini=i;
}
++begin;
--end;
}
Swap(&a[beign],&a[mini]);
Swap(&a[end],&a[maxi]);
}那么当我们解决下面这个问题的时候：当开始时，begin=0，end=7，mini=begin=0，maxi=begin=0。i=1，1小于0，所以mini=1。a[mini]=1，++begin，begin=1，--end，end=6。此时最大值是9（begin），最小值是1（i）。
i=2，begin=1,end=6。
当begin和max重合，就会出现
4 3 5 6
正确的代码应该是这样的：
void SelectSort(int* a,int n)
{
int begin=0,end=n-1;
int mini=begin,maxi=begin;
for(int i=begin+1;i<=end;i++)
{
if(a[i]>a[max])
{
maxi=i;
}
if(a[i]<a[mini])
{
mini=i;
}
}
Swap(&a[begin],&a[mini]);
if(maxi==begin)
{
maxi=mini;
}
Swap(&a[end],&a[maxi]);
++begin;
--end;
}快速排序
把小的换到左边，把大的换到右边。
动图链接地址如下：
void QuickSort(int* a,int left,int right)
{
int key=a[left];
int begin=left,end=right;
while(begin<end)
{
//右边找小
while(begin<end&&a[end]>=key)//加等号，相等的值放左边或者右边都无所谓
{
--end;
}
//左边找大
while(begin<end&&a[begin]>key)
{
++begin;
}
Swap(&a[begin],&a[end]);
}
Swap(key,&a[begin]);
}这段代码有一些问题，让我们逐个解决吧！
首先，记录值只是复制了一个值，比如 int a = 10; int b = a; 修改b的值对a的值没有影响 记录索引，修改的就是索引对应的值
什么情况下不需要对数组进行分割了呢？一种是这个区间只有一个值，另一只种是这个区间不存在。（结束条件）
void QuickSort(int* a,int left,int right)
{
int keyi=left;
int begin=left,end=right;
if(left>right)
return;
while(begin<end)
{
//右边找小
while(begin<end&&a[end]>=key)//加等号，相等的值放左边或者右边都无所谓
{
--end;
}
//左边找大
while(begin<end&&a[begin]>key)
{
++begin;
}
Swap(&a[begin],&a[end]);
}
Swap(&a[keyi],&a[begin]);
keyi=begin;
//[left,keyi-1] keyi [keyi+1,right]'
QuickSort(a,left,keyi-1);
QuickSort(a,keyi+1,right);
}选key如果每一次都在最前面，那么就不合理，我们期望选择的key每次都是最中间的值。
1随机数选key
2三数取中（把选中的数挪到最左边）
int GetMid(int* a,int left,int right)
{
int mid=(left+right)/2;
if(a[left]<a[mid])
{
if(a[mid]<a[right])
{
return mid;
}
else if(a[left]<a[right])
{
return right;
}
else
return left;
}
else
{
if(a[mid]>a[right])
{
return mid;
}
else if(a[left]<a[right])
{
return left;
}
else
return right;
}
}但是当需要排序的数字只有几个时，需要进行的趟数就多了，而且很浪费。所以，在进行判断时，我们需要加上一个条件。那么在这样一个数字较少的情况下，我们应该选择哪种排序呢？希尔排序的优势就是让大的数更快跳到后面，小的数更快跳到前面。
int GetMid(int* a,int left,int right)
{
if(right-left+1<10)//小区间优化,不再递归分割排序，减少递归次数
{
InsertSort(a+left,right-left+1);
}
else
{
int mid=(left+right)/2;
if(a[left]<a[mid])
{
if(a[mid]<a[right])
{
return mid;
}
else if(a[left]<a[right])
{
return right;
}
else
return left;
}
else
{
if(a[mid]>a[right])
{
return mid;
}
else if(a[left]<a[right])
{
return left;
}
else
return right;
}
}
}结论：左边做key，右边先走，可以保证相遇位置的值比key要小。 相遇的场景分析: L遇R:R先走，停下来，R停下条件是遇到比key小的值，R停的位置一定比key小，L没有找大的，遇到R停下了 R遇L:R先走，找小，没有找到比key小的，直接跟L相遇了。L停留的位置是上一轮交换的位置，上一轮交换，把比key小的值，换到L的位置了
相反，让右边做key，左边先走，可以保证相遇位置的值比key要大。
腾讯云开发者
