說明
在 快速排序法(一) 中,每次將最左邊的元素設為軸,而之前曾經說過,快速排序法的加速在於軸的選擇,在這個例子中,只將軸設定為中間的元素,依這個元素作基準進行比較,這可以增加快速排序法的效率。
解法
在這個例子中,取中間的元素s作比較,同樣的先得右找比s大的索引 i,然後找比s小的索引 j,只要兩邊的索引還沒有交會,就交換 i 與 j 的元素值,這次不用再進行軸的交換了,因為在尋找交換的過程中,軸位置的元素也會參與交換的動作,例如:
41 24 76 11 45 64 21 69 19 36
首先left為0,right為9,(left+right)/2 = 4(取整數的商),所以軸為索引4的位置,比較的元素是45,您往右找比45大的,往左找比45小的進行交換:
* 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]
完成以上之後,再初別對左邊括號與右邊括號的部份進行遞迴,如此就可以完成排序的目的。
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 s = number[(left+right)/2];
int i = left - 1;
int j = right + 1;
while(true) {
// 向右找
while(number[++i] < s) ;
// 向左找
while(number[--j] > s) ;
if(i >= j)
break;
swap(number, i, j);
}
sort(number, left, i-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;
}
}
分享到:
相关推荐
void qsort(int arr[],int left,int right) //qsort()函数实现快速排序,并且是递归调用,而且,递归调用qsort()函数本身两次,因为要对中值两边的 { //部分分别进行排序。arr是待排序的数组名,left是排序的左边界,...
在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
算法的实验,背包问题,二分搜索_快速排序_背包问题,若有兴趣可以下载使用。
本资源包括一份分治法算法分析文档,4份Java源程序,包括二分查找、归并排序、快速排序、比赛日程安排。
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
Problem Description ...第二行输入n个整数。 Output Description 输出排序后的整数,每个整数之间以一个空格分隔。注意:最后一个整数后面没有空格。 Sample Input 6 5 2 4 6 1 3 Sample Output 1 2 3 4 5 6
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
快速排序时目前比较的好的排序方法,相比较的别排序法,例如冒泡法,选择法等等。
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
直接插入、折半插入、冒泡、快速、简单选择等排序方法 用c语言实现 代码运行正常 不会有任何的问题
排序 桶 快速 冒泡
快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 � 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 � 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角...
实现数据的折半插入排序、冒泡排序、快速排序和二路归并排序。 输入实例: 请输入待排序数据数目: 3 请输入待排序数据: 23,6,45 输出示例: 折半插入排序: 比较次数 移动元素次数 排序结果 6,23,45。
以从小到大排序为例,选择排序是从某一列数字当中选出最小的数字与第一个位置交换,在从第二个数字开始寻找第二小的数字与第二个位置交换,以此类推,直至最后一个数字交换完毕,排序完成
1)比较范围:直接插入排序、冒泡法排序、简单选择排序、快速排序1(自己实现)、快速排序2(调用STL)、归并排序。 2)比较指标:a)关键字操作次数(比较次数和移动次数之和),b)排序时间。每个指标采用多次重复...
分治法排序 归并排序与二分查找 算法课课件
这三个程序本人已经上机调试过,没错误,是C++编写的,经过老师审核过的,值得一下
不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的,第i趟子排序从第1个数至第n-i个数,若第i个数比后一个数大(则...
各种经典算法(总有一款你喜欢),河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 騎士走棋盤 ...快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 。。。
某个二维数组存放了一系列的字符串,试利用排序的一些算法(如插入、冒泡、快速排序等)例如:二维数组的字符串如下: char s[][20]={“while”,”if”,“else”,”do”,“for”,”switch”,“case”,};