`
- 浏览:
34771 次
- 性别:
- 来自:
广州
-
QuickSort
一 Introduction
快速排序的最坏运行时间是Θ(n²);但在实践上它常常是最好的算法,因为它在平均情况下的期望运行时间是Θ(n lg n),而且隐藏在Θ(n lg n)里面的常量因子是很小的。同时,它是一种原地排序算法,在虚拟内存上也工作良好。
另外,通过随机函数可以极大降低最坏情况的出现概率。
二 算法描述
快速排序算法和归并排序一样,是一种基于分治思想(divide-and-conquer)的排序算法。以下是对数组A[p...r]中的元素进行快速排序的过程。
Divide: Partition (rearrange) the array A[p ‥ r] into two (possibly empty) subarrays A[p ‥ q - 1] and A[q + 1 ‥ r] such that each element of A[p ‥ q - 1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q + 1 ‥ r]. Compute the index q as part of this partitioning procedure.
Conquer: Sort the two subarrays A[p ‥ q -1] and A[q +1 ‥ r] by recursive calls to quicksort.
Combine: Since the subarrays are sorted in place, no work is needed to combine them: the entire array A[p ‥ r] is now sorted.
下面是快速排序算法的伪代码:
QUICKSORT(A, p, r)
1 if p < r
2 pivot = RANDOM(p,r)
3 then q ← PARTITION(A, p, r,pivot)
4 QUICKSORT(A, p, q - 1)
5 QUICKSORT(A, q + 1, r)
在这个算法中,PARTITION()是关键的一个方法,它把A[pivot]放在数组中的正确位置上,并将数组划分成两个子数组。左边的子数组中的任一个元素都小于A[pivot],右边的子数组中的任一个元素都不小于A[pivot]。以下是PARTITION()方法的伪代码:
PARTITION(A, p, r,pivot)
1 swap(A, r, pivot)
2 x ← A[r]
3 i ← p - 1
4 for j ← p to r - 1
5 do if A[j] ≤ x
6 then i ← i + 1
7 exchange A[i] ↔ A[j]
8 swap(A, i + 1, r)
9 return i + 1
三 分析
略。
四 代码清单
#include <time.h>
#include <cstdlib>
#include <iostream>
using namespace std;
//函数声明,以便在main函数里调用。
void quickSort(int [],int,int);
int main()
{
cout << "main() run." << endl;
srand(time(0));
int aryTest[10000];
int iNumberCounts = 10;
while (iNumberCounts)
{
cout << "The numbers to be sorted are: (" << iNumberCounts << ")" << endl;
for (int i = 0; i < iNumberCounts; i++)
{//生成随机数
aryTest[i] = rand() % 65535;
cout << aryTest[i] << " ";
}
cout << endl;
//对生成的随机数组调用快速排序算法。
quickSort(aryTest,0,iNumberCounts - 1);
bool bCorrect = true;
cout << "The sorted numbers are:" << endl;
for(int i = 0; i < iNumberCounts; i++)
{//输出并检查排序結果。
cout << aryTest[i] << " ";
if (i < iNumberCounts - 2)
{
if(aryTest[i] > aryTest[i + 1])
{
bCorrect = false;
break;
}
}
}
if (bCorrect)
{
cout << endl << "OK!The result is correct! "<< endl << endl;
}
else
{
cout << endl << "The result is wrong! "<< endl << endl;
}
cout << "Input count of numbers:" << endl;
cin >> iNumberCounts;
}
return 0;
}
void swap(int intArray[], int left, int right)
{
if (left == right)
{
return;
}
intArray[left] = intArray[left] + intArray[right];
intArray[right] = intArray[left] - intArray[right];
intArray[left] = intArray[left] - intArray[right];
}
int partition(int intArray[], int begin, int end, int pivot)
{
swap(intArray, end, pivot);
int i = begin - 1;
int iPivot = intArray[end];
for (int j = begin; j < end ; j++)
{
if (intArray[j] < iPivot)
{
i++;
swap(intArray ,i ,j);
}
}
swap(intArray, i + 1, end);
return (i + 1);
}
void quickSort(int intArray[], int begin, int end)
{
if (begin < end)
{
srand(time(0));
int pivot = begin + rand() % (end - begin + 1);
int p = partition(intArray, begin, end, pivot);
quickSort(intArray, begin, p - 1);
quickSort(intArray, p + 1, end);
}
}
五 结语
略。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
快速排序QuickSort.java
然后定义了quickSort函数来实现快速排序算法。在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解...
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
快速排序是20世纪十大算法之一,可见其精妙之处,相较于其他复杂度为O(n^2),可以提高到n*logn.一般我们研究快速排序基本采用内置类型,如int型数据,本类为了更通用,采用了模板类,具体数据对象类型可根据用户自己...
下面小编就为大家带来一篇Java快速排序QuickSort(实例)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
本文实例讲述了PHP快速排序quicksort。分享给大家供大家参考,具体如下: quicksort 在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。(即一分为二的...
很好aospiupdoaspdasdasdsadasd
资源名:quicksort_matlab_快速排序 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的...
快速排序(Quicksort)的Javascript实现
快速排序源代码,采用C++编写,经测试未发现BUG,供大家参考
void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } /****************************************************/
分治法的应用,快速排序是其中一种。注释便于读者明白。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
PHP_基于php实现的快速排序算法_QuickSort
用分治的思想模拟快速排序的迭代过程,快速排序平均运行时间可以和Heapsort媲美
QuickSort快速排序的实现 [Qsort类] 使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:...
C# 快速排序源码, 包含调用方式和注释,QuickSort.cs ///调用方式 /// /// int[] arr = new int[] { 5,3,9,6,4,7,8,1,2}; /// QuickSort.quickSort(arr, 0, arr.Length - 1); /// ///
快速排序 快速排序(Quicksort)是一种常见的、高效的排序算法,它基于分治(Divide and Conquer)的思想