首页 > 编程知识 正文

快速排序的三种方法是,快速排序

时间:2023-05-05 07:22:50 阅读:284502 作者:4319

快速排序算法主要用到的基本算法思想是分治算法:排序数组时,将数组分为两个小部分,然后对它们进行递归排序。

在本篇文章中,将采用三种方法实现快速排序。现在有数组a定义为{ 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 }。

第一种

我们给定一个t值,然后重新组织数组a[m...n],并计算下标p,使得所有小于t的元素在p的一端,所有大于t的元素在p的另一端。我们通过一个从左到右扫描数组的简单for循环完成这一任务。排序过程如下图所示:

                               

                                 

                                 

代码实现如下所示:

#include <iostream>using namespace std;template <typename T>void swap(T a[], int m, int n){T temp = a[m];a[m] = a[n];a[n] = temp;}template <typename T1>void sort_one(T1 a[], int m, int n){int p=m;T1 t = a[m];if (m > n)return;for (int i = m+1; i <= n; i++){if (a[i] < t){swap<T1>(a, ++p, i);}}swap<T1>(a, m, p);sort_one(a,m,p-1);sort_one(a, p + 1, n);}int main(){double a[]= { 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 };sort_one<double>(a, 0, 7);for (int i=0; i < 8; i++)cout << a[i]<<",";return 0;}

该快速排序方法能快速完成对随机整数数组的排序。在具有n个相同的数组元素时,采用插入排序时每个元素需要移动的距离都为0,总的运行时间为O(n);但该方法需要的n-1次划分中都需要O(n)时间来去掉一个元素,所以总的运行时间为O(n)。

第二种

对于上述中出现的问题,我们引入第二种方法,使用双向划分避免上述中的问题。如下图所示:

                            

下标p和q初始化为待划分数组的两端。主循环中有两个内循环,第一个内循环将p向右移过小元素,遇到大元素时停止;第二个内循环将q向左移过大元素,遇到小元素时停止。然后主循环测试这两个下标是否交叉并交换他们的值。

实现代码如下所示:

#include <iostream>using namespace std;template <typename T>void swap(T a[], int m, int n){T temp = a[m];a[m] = a[n];a[n] = temp;}template <typename T2>void sort_two(T2 a[], int m, int n){if (m > n)return;T2 t = a[m];int p = m,q=n+1;while (1){for (p++; p <= n&&a[p] < t; p++);for (q--; a[q]>t; q--);if (p > q)break;swap<T2>(a, p, q);}swap<T2>(a, m, q);sort_two(a, m, q - 1);sort_two(a, q + 1, n);}int main(){double a[]= { 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 };sort_two<double>(a, 0, 7);for (int i=0; i < 8; i++)cout << a[i]<<",";return 0;}

如果数组已经按升序排好了,那么它就会围绕最小的元素进行划分,然后是第2小的元素,依此类推,总共需要O(n^2)的时间。

第三种

为了解决上述问题,引入随机选择划分元素可以得到好的多的性能,我们通过把a[m]与a[m...n]中的一个随机项交换实现这一点。

代码实现如下所示

#include <iostream>using namespace std;template <typename T>void swap(T a[], int m, int n){T temp = a[m];a[m] = a[n];a[n] = temp;}template <typename T3>void sort_three(T3 a[], int m, int n){if (m > n)return;swap<T3>(a, a[m], a[rand() % (n - m + 1) + m]);T3 t = a[m];int p = m, q = n + 1;while (1){for (p++; p <= n&&a[p] < t; p++);for (q--; a[q]>t; q--);if (p > q)break;swap<T3>(a, p, q);}swap<T3>(a, m, q);sort_two(a, m, q - 1);sort_two(a, q + 1, n);}int main(){double a[]= { 55.3, 55.2, 59.5, 26, 53, 58, 97, 93 };sort_three<double>(a, 0, 7);for (int i=0; i < 8; i++)cout << a[i]<<",";return 0;}

本篇中源代码工程文件下载地址:https://github.com/XiaoYaoNet/QuickSort

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。