1.快速排序主要思想
快速排序是一种常用的排序算法，其主要思想是选择一个基准值，将数组分割成两部分，左边的部分都比基准值小，右边的部分都比基准值大，然后对左右两部分分别进行递归排序，最终实现整个数组的排序。
快速排序的主要步骤：
-
• 1.选择基准值
-
• 从数组中选择一个基准值，通常是数组中的第一个元素、最后一个元素或者中间的元素。
-
• 2.分割
-
• 将数组中小于基准值的元素放在左边，大于基准值的元素放在右边，基准值处于最终排序位置的中间。
-
• 3.递归排序
-
• 对基准值左右两部分的子数组分别递归进行快速排序。
-
• 4.合并
-
• 不需要合并步骤，因为在分割的过程中，子数组的顺序会得到维护。
2.C++示例
void SortTest::quickSort(int *p,const int start, const int end) {
if (start < end) {
int pivot = p[end];
int i = start - 1;
for (int j = start; j < end ; ++j) {
if (p[j] <= pivot) {
++i;
std::swap(p[i], p[j]);
}
}
std::swap(p[i + 1], p[end]);
int pivotIndex = i + 1;//分区并获取枢纽索引
quickSort(p, 0, pivotIndex - 1);//对枢纽左侧的子数组进行快速排序
quickSort(p, pivotIndex + 1, end);//对枢纽右侧的子数组进行快速排序
}
}调用如下
void SortTest::test() {
const int KLenOfArray = 11;
int p[KLenOfArray] = { 10, 6, 12, 5, 1, 8, 11, 32, 1, 21, 3 };
int q[KLenOfArray];
memset(q, 0, sizeof(int) * KLenOfArray);
memcpy(q, p, sizeof(int) * KLenOfArray);
std::cout<<"quickSort快速排序后为"<<endl;
quickSort(q, 0, KLenOfArray - 1);
showArray(q, KLenOfArray);
}
3.效果
quickSort快速排序后为
arraylist infommation:1,1,3,5,6,8,10,11,12,21,32,4.小结
此文看下C++文章的排版及风格，后面可能会添加C++方向的笔记，不喜勿喷。
原文始发于微信公众号（客户端全栈技术养成记）：C++关于快速排序示例
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/290169.html
