十大经典排序之快速排序(C++实现)
2024-10-21 13:29:22
快速排序
通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
思路:
(1)选择基准:从数列中挑出一个元素,称为 "基准"(pivot)。挑选方法(首尾法,随机取值法,三数取中法)
(2)重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
(3)递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
代码实现:
#include <iostream>
#include <random>
using namespace std;
template <typename T> //整數或浮點數皆可使用
int Paritition1(T* A, int low, int high) {
T pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
template <typename T>
void QuickSort(T* A, int low, int high) //快排母函数
{
if (low < high) {
int pivot = Paritition1(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
int main()
{
int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
int len = (int) sizeof(arr) / sizeof(*arr);
QuickSort(arr,0, len-1);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
double arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
len = (int) sizeof(arrf) / sizeof(*arrf);
QuickSort(arrf,0, len-1);
for (int i = 0; i < len; i++)
cout << arrf[i] << ' ' << endl;
return 0;
}
几种优化思路
当待排序序列的长度分割到一定大小(16)后,使用插入排序或者调用层次过深的时候调用堆排序(STL中Sort采用的优化方法)
相同元素聚集(特定优化方式,针对数列中重复数很多的情况)
传统递归改尾递归(一言以蔽之,传统递归越深,距离目标越近;尾递归越深,距离起点越远。)
void quickSort(SqList * list , int low ,int high)
{int pivot; while(low<high)
{ pivot=Partition(list,low,high); quickSort(list, low,pivot - 1); //quickSort(list,low,pivot-1); 原递归调用 //quickSort(list,pivot+1,high); low = pivot+1; /*尾递归*/ }
}
最新文章
- Sql常用语句(3)
- redis数据类型之—Hash
- Android Studio快捷键每日一练(1)
- 树莓派安装LAMP作为服务器
- 数据结构之链表、栈和队列 java代码实现
- windows下查看所有进程以及pid
- UML中的六大关系
- get mac 20150202
- MSSQL版本
- systemtap 列出所有linux 内核模块与相关函数2
- Oracle_Flashback_技术_总结
- BROCADE 300和MD3200扩展柜FC SAN,截图
- 应对黑客攻击SQL SERVER数据库中的一个案例
- txt 开关 csv 可通用 工具
- linux自动化构建工具-scons指南
- Markdown语法讲解及MWeb使用教程
- NOIP2017Day1题解
- pandas的Panel类型dtype
- C# 6 元组应用 Part 2:C# 也玩模式匹配
- pyCharm最新2017激活码