C++快排 ~ 三种实现方法
C++快排 ~ 三种实现方法
- 1、前言
- 2、代码
- 2.1 hoare 版本
- 2.1.1 代码
- 2.1.2 运行结果
- 2.2 挖坑法
- 2.2.1 代码
- 2.2.2 运行结果
- 2.3 前后指针
- 2.3.1 代码
- 2.3.2 运行结果
1、前言
快排的理论部分，有兴趣者可点击博客 温故而知新 -＞ 数据结构 -＞排序 或通过其他方式进行理解！
博主其实之前实现过快排，具体可见博客 温故而知新 -＞ 数据结构 -＞排序 -＞程序实现2_利用C++ 中的内容，但因为当时实现是函数之间的层层调用，虽然理解不难，但代码量会比较多，也有点麻烦，所以在本篇博客中将对其进行精简！
快排中，将区间按照基准值划分为左右两半部分的常见方式有：
- hoare版本
- 挖坑法
- 前后指针版本
所以下面的程序实现将按这三种方法进行说明！
2、代码
2.1 hoare 版本
2.1.1 代码
#include <iostream>
#include <vector>
using namespace std;
void display(vector<int>& arr)
{
for (auto& n : arr)
cout << n << " ";
cout << endl;
}
// 将数组以升序进行排列！
void quickSort(vector<int>& arr, int left, int right) // hoare 升序
{
if (left >= right)
return;
int key = arr[left];
int begin = left;
int end = right;
int start = left;
while (begin < end)
{
while (begin < end && arr[end] >= key)
--end;
while (begin < end && arr[begin] <= key)
++begin;
if (begin != end)//此句是用于减少不必要的操作，可加可不加
swap(arr[begin], arr[end]);
}
swap(arr[start], arr[begin]);
quickSort(arr, left, begin - 1);//此处begin与end可任选其一
quickSort(arr, begin + 1, right);
}
// 将数组以降序进行排列！
void quickSort_2(vector<int>& arr, int left, int right) // hoare 降序
{
if (left >= right)
return;
int key = arr[left];
int begin = left;
int end = right;
int start = left;
while (begin < end)
{
while (begin < end && arr[end] <= key)
--end;
while (begin < end && arr[begin] >= key)
++begin;
if (begin != end)//此句可加可不加
swap(arr[begin], arr[end]);
}
swap(arr[start], arr[begin]);
quickSort_2(arr, left, begin - 1);//此处begin与end可任选其一，因为上面的循环结束后，begin会与end相等
quickSort_2(arr, begin + 1, right);
}
void test()
{
vector<int> arr = { 6, 3, 1, 8, 7, 2, 4 };
cout << "原数组："; display(arr);
quickSort(arr, 0, arr.size() - 1);
cout << "升序排列："; display(arr);
quickSort_2(arr, 0, arr.size() - 1);
cout << "降序排列："; display(arr);
}
int main()
{
test();
return 0;
}
注意：上述升序与降序的主要区别就是程序中的大小判断条件相反！
2.1.2 运行结果
2.2 挖坑法
2.2.1 代码
#include <iostream>
#include <vector>
using namespace std;
void display(vector<int>& arr)
{
for (auto& n : arr)
cout << n << " ";
cout << endl;
}
// 将数组以升序进行排列！
void quickSort2(vector<int>& arr, int left, int right)
{
if (left >= right)
return;
int key = arr[left];
int begin = left;
int end = right;
while (begin < end)
{
while (begin < end && arr[end] >= key)
--end;
arr[begin] = arr[end];//此处其实也可通过判断begin与end是否相等来减少多余操作
while (begin < end && arr[begin] <= key)
++begin;
arr[end] = arr[begin];//此处其实也可通过判断begin与end是否相等来减少多余操作
}
arr[begin] = key;
quickSort2(arr, left, end - 1);
quickSort2(arr, end + 1, right);
}
// 将数组以降序进行排列！
void quickSort2_2(vector<int>& arr, int left, int right)
{
if (left >= right)
return;
int key = arr[left];
int begin = left;
int end = right;
while (begin < end)
{
while (begin < end && arr[end] <= key)
--end;
arr[begin] = arr[end];//此处其实也可通过判断begin与end是否相等来减少多余操作
while (begin < end && arr[begin] >= key)
++begin;
arr[end] = arr[begin];//此处其实也可通过判断begin与end是否相等来减少多余操作
}
arr[begin] = key;
quickSort2_2(arr, left, begin - 1);
quickSort2_2(arr, begin + 1, right);
}
void test()
{
vector<int> arr = { 6, 3, 1, 8, 7, 2, 4 };
cout << "原数组："; display(arr);
quickSort2(arr, 0, arr.size() - 1);
cout << "升序排列："; display(arr);
quickSort2_2(arr, 0, arr.size() - 1);
cout << "降序排列："; display(arr);
}
int main()
{
test();
return 0;
}
2.2.2 运行结果
2.3 前后指针
2.3.1 代码
#include <iostream>
#include <vector>
using namespace std;
void display(vector<int>& arr)
{
for (auto& n : arr)
cout << n << " ";
cout << endl;
}
// 将数组以升序进行排列！
void quickSort3(vector<int>& arr, int left, int right)
{
if (left >= right)
return;
int prev = left;
int cur = left + 1;
int key = arr[left];
while (cur <= right)
{
if (arr[cur] < key && ++prev != cur)//小于基准值且不连续时进行交换
swap(arr[prev], arr[cur]);
++cur;
}
swap(arr[left], arr[prev]);
quickSort3(arr, left, prev - 1);
quickSort3(arr, prev + 1, right);
}
// 将数组以降序进行排列！
void quickSort3_2(vector<int>& arr, int left, int right)
{
if (left >= right)
return;
int prev = left;
int cur = left + 1;
int key = arr[left];
while (cur <= right)
{
if (arr[cur] > key && ++prev != cur)//小于基准值且不连续时进行交换
swap(arr[prev], arr[cur]);
++cur;
}
swap(arr[left], arr[prev]);
quickSort3_2(arr, left, prev - 1);
quickSort3_2(arr, prev + 1, right);
}
void test()
{
vector<int> arr = { 6, 3, 1, 8, 7, 2, 4 };
cout << "原数组："; display(arr);
quickSort3(arr, 0, arr.size() - 1);
cout << "升序排列："; display(arr);
quickSort3_2(arr, 0, arr.size() - 1);
cout << "降序排列："; display(arr);
}
int main()
{
test();
return 0;
}
2.3.2 运行结果
上述三种方法，个人推荐用第二种~