文章目录
- 一、创始人托尼·霍尔的快速排序
- 二、挖坑法
- 三、前后指针法
所属专栏:C++初阶
引言:这里所说的快速排序有三种,第一种是霍尔大佬自创的,还有一种叫做挖坑法,另外一种叫前后指针法
一、创始人托尼·霍尔的快速排序
1.这里我们先把中间值定位数组中的首元素的值,设为key变量,大于key的放右边,小于key的放左边
2.定义left为从数组0下标开始找大于key的数,如果小于key,left就向前走一步,定义right从数组下标为n-1的位置,从右向左找小于key的数,从最右边的数开始,如果大于key,right就向后走一步
3.这里我们还要判断谁先和谁相遇(也就是谁走到相等的位置,而那个人是停止的)
如果left先走,那么left与right相遇的地方就是left走遇到right(相遇的地方的值是大于key的)
如果right先走,那么left与right相遇的地方就是right走遇到left(相遇的地方的值是小于key的)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* p1,int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int QuickSort(int left,int right,int* a)
{
int keyi = left;
int end = right;
//判断谁先走的问题,我们把大于a[keyi]的放左边
//小于a[keyi]的放右边,等于的话就不管
//这里要判断谁先走的问题
//如果left先走,那么left与right相遇的地方就是left走遇到right
//如果right先走,那么left与right相遇的地方就是right走遇到left
while (left < right)
{
//右边找小
while(left < right && a[right] >= a[keyi])
right--;
//左边找大
while(left < right && a[left] <= a[keyi])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}
void TestSort(int* a, int begin,int end)
{
if (begin >= end)//当只有一个数时,不用排序,直接返回
return;
//霍尔大佬的排序
int keyi = QuickSort(begin, end ,a);
TestSort(a, begin,keyi-1);
TestSort(a, keyi+1,end);
}
int main()
{
int a[] = {6,1,2,7,9,3,4,5,10,8};
TestSort(a, 0, sizeof(a) / sizeof(int) - 1);
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
printf("%d ", a[i]);
return 0;
}
这里的排序就像是二叉树的遍历,大家可以参考前面的代码
排序区间【begin,keyi-1】keyi 【keyi+1,end】(keyi为中间值,已经排好序了)
二、挖坑法
步骤如下:
1.这里的挖坑(从a[left]开始是第一个坑,然后right寻找小于key(a[left])的值,找到了这个坑就跑到a[right]去了,同时要交换一下下标hole=right)
2.然后就从left开始找大于key的值,找到了那么就是第二个坑,hole就跳到了left的位置,hole=left
3.以此类推,直到left=right的时候,此时的坑就在left=right的地方,然后a[hole]=key(此时的key就是中间值不需要排了)
int QuickSort(int left,int right,int* a)
{
int key = a[left];
int end = right;
int hole = left;
while (left < right)
{
//右边找小
while(left < right && a[right] >= key)
right--;
a[hole] = a[right];
hole = right;
//左边找大
while(left < right && a[left] <key)
left++;
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return left;
}
三、前后指针法
步骤如下:
1.首先定义一个前指针prev,和一个后指针cur
2.然后cur先向前走,如果大于key,那么继续向前走,prev,不向前走,如果小于key,那么prev和cur同时向前走(总的来说cur一直是向前走的,prev只在cur位置小于key才向前走的)
3.以此类推,直到cur>end就不走了
int QuickSort3(int left, int right, int* a)
{
int key = a[left];
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] <= key && ++prev != cur)
Swap(&a[prev],&a[cur]);
cur++;
}
//最后这里的a[prev]一定是一个小于key的值,
//所以需要和key这个中间值换一下,以达到key已经排好序
Swap(&a[prev], &a[left]);
return prev;
}