說明
快速排序法(quick sort)是目前所公認最快的排序方法之一(視解題的對象而定),雖然快速排序法在最差狀況下可以達O(n2),但是在多數的情況下,快速排序法的效率表現是相當不錯的。
快速排序法的基本精神是在數列中找出適當的軸心,然後將數列一分為二,分別對左邊與右邊數列進行排序,而影響快速排序法效率的正是軸心的選擇。
這邊所介紹的第一個快速排序法版本,是在多數的教科書上所提及的版本,因為它最容易理解,也最符合軸心分割與左右進行排序的概念,適合對初學者進行講解。
解法
這邊所介紹的快速演算如下:
1. 將最左邊的數設定為軸,並記錄其值為 s
廻圈處理:
1. 令索引 i 從數列左方往右方找,直到找到大於 s 的數
2. 令索引 j 從數列右方往左方找,直到找到小於 s 的數
3. 如果 i >= j,則離開迴圈
4. 如果 i < j,則交換索引i與j兩處的值
5. 將左側的軸與 j 進行交換
6. 對軸左邊進行遞迴
7. 對軸右邊進行遞迴
透過以下演算法,則軸左邊的值都會小於s,軸右邊的值都會大於s,如此再對軸左右兩邊進行遞迴,就可以對完成排序的目的,例如下面的實例,*表示要交換的數,[]表示軸:
* [41] 24 76* 11 45 64 21 69 19 36*
* [41] 24 36 11 45* 64 21 69 19* 76
* [41] 24 36 11 19 64* 21* 69 45 76
* [41] 24 36 11 19 21 64 69 45 76
* 21 24 36 11 19 [41] 64 69 45 76
在上面的例子中,41左邊的值都比它小,而右邊的值都比它大,如此左右再進行遞迴至排序完成。
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 i = left;
int j = right + 1;
while(true) {
// 向右找
while(i + 1 < number.length && number[++i] < number[left]) ;
// 向左找
while(j -1 > -1 && number[--j] > number[left]) ;
if(i >= j)
break;
swap(number, i, j);
}
swap(number, left, j);
sort(number, left, j-1); // 對左邊進行遞迴
sort(number, j+1, right); // 對右邊進行遞迴
}
}
private static void swap(int[] number, int i, int j) {
int t = number[i];
number[i] = number[j];
number[j] = t;
}
}
分享到:
相关推荐
快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中...
使用快速排序法对一维数组进行排序,程序完全可以运行,方便大家学习
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
void qsort(int arr[],int left,int right) //qsort()函数实现快速排序,并且是递归调用,而且,递归调用qsort()函数本身两次,因为要对中值两边的 { //部分分别进行排序。arr是待排序的数组名,left是排序的左边界,...
一个快速排序法的例子 构建1亿的随机数,完整排序花时26秒左右
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为“基准”(pivot), 重新排序数列,所有比基准值小的元素摆放在基准前面...
java 快速排序 折半查找的界面实现 (递归与分治法)
一种快速的排序法—插入合并排序法一种快速的排序法—插入合并排序法
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
使用快速排序算法实现对n个元素进行排序。 由文件input.txt提供输入数据,输出到文件output.txt中。
在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left),递归左半边 if(left) QuickSort (pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) QuickSort (pData,i,right);...
分治法的应用,快速排序是其中一种。注释便于读者明白。
这是一个利用MFC界面做的快速排序法的实现
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...
Problem Description 使用插入排序算法对输入的n个整数,按照从小到大的...输出排序后的整数,每个整数之间以一个空格分隔。注意:最后一个整数后面没有空格。 Sample Input 6 5 2 4 6 1 3 Sample Output 1 2 3 4 5 6
递归求解(Conquer):通过递归对p..aq和aq+1..ar进行排序。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在ap..aq和aq+1..ar都排好序后不需要执行...因此,快速排序法是分治法的经典应用实例之一。
在某些情况下,快速排序法法是最快的一种排序算法,并且它有很大的推广潜力