說明
之前說過軸的選擇是快速排序法的效率關鍵之一,在這邊的快速排序法的軸選擇方式更加快了快速排序法的效率,它是來自演算法名書 Introduction to Algorithms 之中。
解法
先說明這個快速排序法的概念,它以最右邊(或最左邊)的值s作比較的標準,將整個數列分為三個部份,一個是小於s的部份,一個是大於s的部份,一個是未處理的部份,如下所示 :
在排序的過程中,i 與 j 都會不斷的往右進行比較與交換,最後數列會變為以下的狀態:
然後將s的值置於中間,接下來就以相同的步驟會左右兩邊的數列進行排序的動作,如下所示:
整個演算的過程,直接摘錄書中的虛擬碼來作說明:
QUICKSORT(A, p, r)
if p < r
then q <- PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
end QUICKSORT
PARTITION(A, p, r)
x <- A[r]
i <- p-1
for j <- p to r-1
do if A[j] <= x
then i <- i+1
exchange A[i]<->A[j]
exchange A[i+1]<->A[r]
return i+1
end PARTITION
一個實際例子的演算如下所示:
public class Sort {
public static void quick(int[] number) {
sort(number, 0, number.length-1);
}
private static void sort(int[] number, int left, int right) {
if(left < right) {
int q = partition(number, left, right);
sort(number, left, q-1);
sort(number, q+1, right);
}
}
private static int partition(int number[], int left, int right) {
int i = left - 1;
for(int j = left; j < right; j++) {
if(number[j] <= number[right]) {
i++;
swap(number, i, j);
}
}
swap(number, i+1, right);
return i+1;
}
private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
分享到:
相关推荐
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
冒泡法排序c语言程序 冒泡法排序c语言程序 基础排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序
printf("\t3: 快速排序\n"); printf("\t4: 直接选择排序\n"); printf("\t5: 堆排序\n"); printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); printf("\t***************************\n"); scanf("%d",&i...
输入同样一组数据,比较直接插入排序、冒泡排序、快速排序这三种排序算法的关键字的比较次数和数据移动次数。
用C++写了以上三种排序算法,对初学数据结构的同学一个参考
C语言中三种排序法的用处与优点(冒泡排序、插入排序和快速排序) 冒泡法排序c语言程序
详细描述快速排序规律,并附上源码,具体请看我的博客快速排序分区,含单向分区法,双向分区,以及三指针分区
快速排序是一种采用分治法策略的高效排序算法,其基本思想是选取一个基准元素,将数组分为两部分,使得一部分的元素都小于基准元素,另一部分的元素都大于基准元素。 快速排序过程 快速排序的过程包括选取基准、分区...
选择排序、快速排序、冒泡排序三种基本排序方法的程序,vc6.0实现,思路清晰简单,注释详细易懂,通过对比可加深理解排序方法和原理。
* 快速排序的实现基于分治法,具体分为三个步骤。假设待排序的序列为L[m..n]。 * 分解:序列L[m .. n]被划分成两个可能为空的子序列L[m .. pivot-1]和L[pivot+1 .. n], * 使L[m .. pivot-1]的每个元素均小于或...
快速排序法(三) 合并排序法 基数排序法 � 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 � 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数...
各种经典算法(总有一款你喜欢),河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 騎士走棋盤 八個皇后 八枚銀幣 ...快速排序法(三) 合併排序法 基數排序法 。。。
快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表) 插補搜尋法 費氏搜尋法 矩陣 稀疏矩陣 多維矩陣轉一維矩陣 上三角、下三角、對稱矩陣 奇數魔方...
快速排序法(三) 合并排序法 基数排序法 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 堆叠 - 使用阵列实作 堆叠 - 使用链结实作(C 语言动态记忆体宣告) 堆叠 - 使用 ...
虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明:挖坑填数+分治法: 先来看实例吧,定义下面再给出(最好能用自己的话来总结定义,这样对实现...
主要介绍了Java编程基于快速排序的三个算法题实例代码,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
这三个程序本人已经上机调试过,没错误,是C++编写的,经过老师审核过的,值得一下
经典常用算法解析与实现,通过Java C语言分别实现各种算法,图文并茂,描述很详细! 主要包括如下算法,很全面! 河内塔 费式数列 巴斯卡三角形 三色棋 ...快速排序法(三) 合并排序法 基数排序等
老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 ...快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜
C语言经典几十个经典案例,都有详尽 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 ...快速排序法(三) 合并排序法 基数排序法 循序搜寻法(使用卫兵)