//本文所写快排的结果都是从小到大排序
思路
快排就是把数组的第一个值记为key,然后定义两个指针,一个叫begin,一个叫end.
begin指针从数组的头部出发,寻找比key大的值;end指针从数组的尾部出发,寻找比key小的值;
然后交换begin和end的值
......最后,begin和end相遇就停下,此时交换begin和key的值(也可以看做交换end和key的值),
就可以得到这样的结果:key左边的值都比key小,key右边的值都比key大.
然后key的左边和右边分别进行上面的排序过程,直到数组彻底有序为止.
待会还有一些细节的东西会在下面提到.
图解
比较简略,大家将就着看叭...
图中的left和right指针就是上面提到的begin和end指针...
霍尔版本写法（递归）
代码有两个函数,一个是QuickSort,构建了递归的框架;另一个是_QuickSort,里面写了快排的排序实现.
int _QuickSort(int* a, int left,int right)
{
int key = left;
int begin = left;
int end = right;
while (begin < end)
{
//end先走,end找比key小的值
while (begin < end && a[end] >= a[key])//防止越界,加上begin < end
{
--end;
}
//begin找比key大的值
while (begin < end && a[begin] <= a[key])
{
++begin;
}
swap(a[begin], a[end]);
}
swap(a[key], a[begin]);
//注意:我们交换的是数组的a[key]和 a[begin],但是key等于left,key应该更新成begin
key = begin;
return key;
}
void QuickSort(int* p, int left, int right)
{
if (left >= right)
{
return;
}
else
{
int key = _QuickSort(p, left, right);
QuickSort(p, left, key - 1);
QuickSort(p, key + 1, right);
}
}
注意事项
1.关于end先走
end先走可以保证最终停留的位置比key小。（不考虑这种情况：在数组有序的情况下，第一次循环end直接走到begin的位置，此时key位置的值就会等于end/begin位置的值）
让我们分析循环终止的情况：
要么就是end--走到了begin的位置,begin位置的值比key小,因为begin还在上次交换的位置，begin存的是比key小的值。
要么是end找到了比key小的值，就停在了那里，begin走到了end的位置，begin存的值也会比key小。
2.end先走的作用
交换key和begin的值，要保证key的左边值都比key小，右边值都比key大，所以begin停留的位置（换而言之end停留的位置）要比key小，才能做到。
优化
1.key值的选取
万一key值是最小的或者最大的,走快排就很浪费时间,所以我们选的key最好是一个中间值.
所以我们将会写一段代码来选取合适的key值.
2.数据比较少的时候使用插入排序
当数据个数比较少的时候,走插入排序比快排快,所以假设有百万数据时,我们可以让数据小于10个的时候走插入排序,数据大于10个走插入排序
3.优化后的代码
//此代码的swap函数是库里的
//为key选取合适的中间值
int GetMidi(int* a, int left, int right)
{
int midi = left + (right - left) / 2;
if (a[left] >= a[midi])
{
if (a[right] >= a[left]) {
return left;
}
else if (a[midi] >= a[right])
{
return midi;
}
else
{
return right;
}
}
else
{
if (a[left] >= a[right])
{
return left;
}
else if (a[midi] <= a[right])
{
return midi;
}
else
{
return right;
}
}
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int temp = a[end + 1];
while (end >= 0)
{
if (a[end] > temp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = temp;
}
}
int _QuickSort(int* a, int left,int right)
{
int midi = GetMidi(a, left, right);
if (midi!=left)
{
swap(&a[midi], &a[left]);
}
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
//end先走,end找比key小的值
while (begin < end && a[end] >= a[key])//防止越界,加上begin < end
{
--end;
}
//begin找比key大的值
while (begin < end && a[begin] <= a[key])
{
++begin;
}
swap(a[begin], a[end]);
}
swap(a[key], a[begin]);
key = begin;
return key;
}挖坑法(递归)
挖坑法在效率上和霍尔法一样，但是会少很多注意事项.
思路
大体上和霍尔排序的思路一样,也有两个指针left和right从头和尾出发,一个找比key大,一个找比key小.
区别在于选取了key值之后,原数组key的地方会空出来,等待比key 小的值right放进去,然后数组里就会空出right的位置,等待比key大的值left放进right的位置,然后left的位置会空出来.......重复此过程,直到left和right相遇.
图解
代码
//此代码的swap是自己写的
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int temp = arr[end + 1];
while (end >= 0)
{
if (temp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = temp;
}
}
int GetMid(int* arr, int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] <= arr[mid])
{
if (arr[left]>=arr[right])
{
return left;
}
else if (arr[mid]<=arr[right])
{
return mid;
}
else
{
return right;
}
}
else
{
if (arr[mid]>arr[right])
{
return mid;
}
else if (arr[left]<arr[right])
{
return left;
}
else
{
return right;
}
}
}
void swap(int* p1, int* p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void QuickSort(int* arr, int left,int right)
{
if (left >= right) {
return;
}
if ((right - left + 1)<=10)
{
InsertSort(arr + left, right - left + 1);
return;
}
else
{
int mid = GetMid(arr, left, right);
if (mid != left)
{
swap(&arr[mid], &arr[left]);
}
int key = arr[left];
//int flag = 0;
int lefti = left, righti = right;
//首次记录hole的值
int hole = left;
while (lefti < righti)
{
while (lefti < righti && arr[righti] >= key)
{
--righti;
}
//比key小的值填入hole
arr[hole] = arr[righti];
//更新hole的位置
hole = righti;
while (lefti < righti && arr[lefti] <= key)
{
++lefti;
}
//比key大的值填入hole
arr[hole] = arr[lefti];
//更新hole的位置
hole = lefti;
}
arr[hole] = key;
QuickSort(arr, left, hole - 1);
QuickSort(arr, hole + 1, right);
}
}
双指针法
思路
有两个指针,一个叫pre,一个叫cur,
cur初始时在pre前面的一个位置,
每循环一次,cur都会往前走一步,
如果cur的值比key小,且pre的下一个值不等于cur,
(实际上,如果cur的值比key大,pre指针就不会走)
那就交换cur和pre的值.
图解
代码
//GetMidi函数本文前面出现过,我就不放了
int partSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right);
if (midi != left)
{
swap(&a[midi], &a[left]);
}
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
while (a[cur] < a[keyi] && ++prev != cur)
{
swap(&a[cur], &a[prev]);
}
++cur;
}
swap(&a[keyi], &a[prev]);
return prev;
}
//QuickSort函数也要调用哦,本文前面出现过我就不放了非递归(使用栈)
思路
和递归的部分思路是相似的,
同样需要key值,
key把数组分为左右两部分,
右边数组先入栈,
左边数组后入栈,
每次取栈顶的区间排序.
代码
void QuickSortNonR(int* a, int left, int right)
{
stack<int> st;
st.push(left);
st.push(right);
while (!st.empty())
{
int end = st.top();
st.pop();
int begin = st.top();
st.pop();
//这是双指针法排序,在本文章的上一部分提及了
int key = partSort2(a, begin, end);
if (key + 1 < end) {
st.push(key + 1);
st.push(end);
}
if (begin < key - 1)
{
st.push(begin);
st.push(key - 1);
}
}
}
![[免费]SpringBoot+Vue景区订票(购票)系统【论文+源码+SQL脚本】](https://i-blog.csdnimg.cn/direct/6e930f3dde3c4f2bb9cf4501c8642e1c.jpeg)
