假设一个数
66
8 5 44 9 77 2 33 41 15 42 69
现在随机挑选一个键值,假设我们选到的是41
,把41
作为key
值存在。设左部序列标为i,
右部序列标为j,
将这个数列升序排序。
从左边开始,66
比41
来得大,两者交换,现在key
值41
在第一位,i
指向第一位,
得到的序列为:41
(I) 8 5 44 9 77 2 33 66 15 42 69(J)
轮到右部,找到第一个比41
小的数为45
者交换,现在i
指向第一位,j
指向右第三位,key
值在第8
位,即跟j
重合。
得到的序列为: 15(I)
8 5 44 9 77 2 33 66 41(J) 42 69
继续比i
,44
比41
来得大,两者交换,现在i
指向第四位,j
指向右数第三位,i
跟key
重合,
得到的序列为:15
8 5 41
(i
) 9
77 2 33 66 44 (j) 42 69;
j
继续往下移,33
比41
来得小,两者交换,现在i
指向第四位,j
指向右数第六位,key
与是重合,
得到的序列为: 15
8 5 33
(i
)
9 77 2 41(j) 66 44
42 69
i
往下,77
比41
来得大,
交换
得到的序列为:15
8 5 33 9 41
(i
)
2 77(j) 66 44 42 69
j
往下,2
比41
小
得到的序列为: 15
8 5 33 9 2
(i
)
41(j) 77 66 44 42 69
i
往下,i
与j
重合
第一轮排序结束,得到序列
15 8 5 33 9 2 41 77 66 44
42 69
现在把序列为分两部分,左部为
15 8 5 33 9 2
右部为 41
77 66 44 42 69
同样排序
得最后排序结果: 2
5 8 9 15 33 41 42 44 66 69 77
java实现如下:
Sort接口:
package com.javaeye.rsrt;
public interface Sort {
/**
* 供程序使用的快速排序的接口
* @param num 要进行排序的数序
* @return 排好序的数列
*/
public int[] BeginSort(int[] num);
}
QuickSort类:
package com.javaeye.rsrt;
/**
*
* @author nishiting
*
* 原理:要求将传进来的数列进行排序,快速排序是冒泡法的一个改进版,先通过第一轮排序把数列分为
* 两部分,一部分比关键值小,一部分比关键值大,然后将分开的两部分再进行排序,直到排序结束为止。
*
*/
public class QuickSort implements Sort {
@Override
public int[] BeginSort(int[] num){
Sort(num,0,num.length-1);
System.out.print("num:");
for(int i = 0;i<num.length;i++){
System.out.print(num[i]+" ");
}
System.out.println();
return num;
}
/**
* 将排序方法进行递归,从而得到最终结果
* @param num 要进行排序的数列
* @param start 排序那段的起始位置
* @param end 要排序那段的结束位置
*
*/
private void Sort(int[] num, int start, int end){
/**
* 如果开始的位置超出了结束位置,则程序可以结束,如果两者相等,则代表只排序一个元素,可以不必排序,直接返回
*/
// if(start >= end){
//
// return;
//
// }
/**
*key得到第一轮排序好的关键值的位置,
*将数列分为两部分进行递归,第一部分为key左边的部分,值都比key来的小,
*第二部分为key右边的部分,值都比key来的大。
*
*
*/
if(start<end){
int key = Partition(num,start,end);
Sort(num,start,key-1);
Sort(num,key+1,end);
}
}
/**
* 将数列分为两部分,左部为比关键值小的,右部为比关键值大的,这边取比关键值大的
* @param num 要进行排序的数列
* @param start 排序那段的起始位置
* @param end 要排序那段的结束位置
* @return 关键值的位置
*/
private int Partition(int[] num,int start,int end){
int i = start;
int j = end;
int temp;
/**
* 如果开始的位置小于结束的位置,则代表至少还有两个元素,要将其进入循环排序
*/
while(i < j){
/**
* 从结束位置开始查找,找到第一个比关键值小的元素
*
*/
while (i<j && num[i]<=num[j]) j--;
/**
* 如果这时左边向标小于右边向标的话,则将右部比关键值小的数与关键值进行交换,将i加1,进行左部查找
*/
if(i < j){
temp = num[i];
num[i] = num[j];
num[j] = temp;
i++;
}
/**
* 从开始位置开始查找,找到第一个比关键值大的元素
*
*/
while (i<j && num[i]<=num[j]) i++;
/**
* 如果这时左边向标小于右边向标的话,则将左部比关键值大的数与关键值进行交换,将j减1,进行右部查找
*
*/
if(i < j){
temp = num[i];
num[i] = num[j];
num[j] = temp;
j--;
}
/**
* 返回这时关键值的位置
*/
return i;
}
}
测试用例:
QuickSortTest类:
package com.javaeye.rsrt;
import junit.framework.TestCase;
public class QuickSortTest extends TestCase {
public void testSort(){
QuickSort sort = new QuickSort();
/**
* 测试输入值为空的情况
*/
int[] num = {};
int[] values = {};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试输入值为一个的情况
*
*/
num = new int[] {1};
values = new int[] {1};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试输入为两个升序的情况
*
*/
num = new int[] {1,2};
values =new int[] {1,2};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试输入两个降序的情况
*
*/
num = new int[]{2,1};
values = new int[] {1,2};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试输入多个的情况
*
*/
num = new int[] {1,66,4,7,3,42,11,44,2,87};
values = new int[] {1,2,3,4,7,11,42,44,66,87};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试包含不规则数字情况
*/
num = new int[] {01};
values = new int[] {01};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试多个包含不规则数字情况
*/
num = new int[] {01,1,4,04,6,07,03,2};
values = new int[] {1,01,2,03,4,04,6,07};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试包含有一个负数的情况
*/
num = new int[] {-1};
values = new int[] {-1};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
/**
* 测试包含有多个负数的情况
*
*/
num = new int[] {-1,8,3,-2,77,-44,11};
values =new int[] {-44,-2,-1,3,8,11,77};
sort.BeginSort(num);
for(int i =0;i<num.length;i++){
assertEquals(num[i], values[i]);
}
}
}
分享到:
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序,比较高效的排序算法之一。这是一个例子,一个关于快速排序的例子。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
用函数实现快速排序,并输出每次分区后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input ...
C语言实现多种链表快速排序
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟 扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次 扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只 减少1。快速...
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1)实现快速排序算法。 2)要求输入待排序元素个数,利用随机函数生成指定数目的元素,元素值的 取值范围为[10, 1000000]。 3)运行快速排序程序对所生成元素进行排序,要求将元素的初始输入序列和 排序后的结果序列...
快速排序算法,C语言 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
按所推荐的程序在IE下跑了下,的确,排序耗时很小。 代码如下: [removed] /* * 洗牌 */ function ... /* * 快速排序,按某个属性,或按“获取排序依据的函数”,来排序. * @method soryBy * @static * @
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...