据大家所知的,快速排序是目前的一种非常快的排序方法,它是由C. A. R. Hoare在1962年提出。它的基本思想是:选择一个中间key值,作为分蘖点。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比key小,另外一部分的所有数据都要比key大,然后再递归调用按此方法对这两部分数据分别进行快速排序,以此达到整个数据变成有序序列。
我们先来看一下具体的思路,再根据思路成型代码。
下面是我的程序运行结果截图:
我选择key的方法是(0 + array.length)/2。
因此,第一次选择“93”作为key所对应的值,第一次排序开始。比93小的四个数到了93的左边,比93大的两个数排到93的右边。
现在整个数组被分成了三块:比93小、93,比93大。容易想到下面进行递归调用,分别对93前后两大块进行快速排序。此时的93已经到了自己正确的次序位子。这里会有两个递归调用,先左还是先右完全由读者自己定。这里我选择了先左后右。
于是,第二次排序开始,到了93的左边四个数。选择68作为key对应的值。63,58相应的到了68左边,92到了68的右边。
第三次排序时到了68的左边,选择第一个元素58作为key对应的值,显然不需要交换任何值。
第四次排序时转到68的右边,因为只有92一个元素,不再需要排序。因此再继续向右走,来到93的右边。选择这一块中的第一个元素98作为key对应的值,将比98小的95移动到98的左边。
到这里我们的快速排序结束。
下面就到了代码部分。快速排序的代码有些技巧,需要我们格外的注意其中变量之间的关系和调用函数时的值传递问题。在上传的代码里我也会尽量多的添加注释,读者想要了解、理解、掌握快速排序,就还需要细细体会了。
package hhf.Sort_1012;
import java.util.Random;
/**
* 快速排序
* @author Administrator
* 2012年11月25日
*/
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
//生成一个随机的数组,它有5~20随机的长度,随机的0~99的值
Random random = new Random();
int num = 5 + random.nextInt(16);
int[] array = new int[num];
for(int i = 0 ; i < num ; i++)
array[i] = random.nextInt(100);
System.out.println("一共有元素 " + num + " 个");
//打印原来未排序数组
System.out.println("未排序前");
print(array);
//开始排序
System.out.println("排序中======>>>========>>>>>========>>>");
quicksort(array,0,array.length - 1);
//排序后再打印
System.out.println("已排序后");
print(array);
}
/**
* 快速排序的代码实现
* @param j 数组的末尾
* @param i 数组的起始
* @param array数组名
*/
private static void quicksort(int[] array, int i, int j) {
//System.out.println("quicksort中i = " + i);
//System.out.println("quicksort中j = " + j);
//这是一个递归函数 首先判断是否递归调用截止(当当前块只有一个元素的时候就不需要再排序了)
if(j <= i)
return;
//得到一个关键码key
int key = (j + i) / 2;
//System.out.println("quicksort中key = " + key);
//将关键码key与最后一个数array[length - 1]交换,可以使排序变得方便
swap(array,key,j);
//将前length-1个数进行分类 ——小于key的在前,大于key的在后,并返回大于key的那一块的第一个元素的地址k
int k = sort(array,i-1,j,j);
//System.out.println("quicksort中k = " + k);
//交换k和key是key到达自己应该到的位置
swap(array,k,j);
//递归调用自己 现在已经将原数组分为了两块[0~ key-1]和[key+1 ~ length]因而就要调用两次
print(array);//打印出来,看一下
quicksort(array,i,k-1);
quicksort(array,k+1,j);
}
/**
* 实现分类的函数,其结果是使得比key小的数放在前面 大于key的数放在后面
* @param array数组名
* @param i 数组起始的前一个位置
* @param j 数组结尾
* @param key 关键码
* @return大于key的数的第一个元素下标
*/
private static int sort(int[] array, int i, int j, int key) {
//System.out.println("sort中i0 = " + i);
//System.out.println("sort中j = " + j);
do{
//取到应该交换的i j值
while(array[++i] < array[key]);
while(j>0 && array[--j] >= array[key]);
//交换array[i]和array[j]
swap(array,i,j);
}while(j>i);
//因为最后会有一次多余的i,j交换,所以我们要再人为的交换回来
swap(array,i,j);
//System.out.println("sort中i1 = " + i);
//返回大于key0的第一个元素下标
return i;
}
/**
* 交换array里面的array[i]和array[j]
* @param array
* @param i
* @param j
*/
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 打印数组
* @param array数组名
*/
private static void print(int[] array) {
for(int i = 0 ;i < array.length ; i++)
System.out.print(array[i]+"\t");
System.out.println();
}
}
//double d = 5 + r.nextInt(5) + r.nextDouble();
//可以得到最小为5,最大为10的浮点数。
//解释:public int nextInt(int n)返回一个伪随机数,它是从此随机数生成器的序列中取出的、
//在 0(包括)和指定值(不包括)之间均匀分布的 int值。
//public double nextDouble()返回下一个伪随机数,
//它是从此随机数生成器的序列中取出的、在0.0d(包括)到 1.0d(包括)范围内均匀选择(大致)的 double 值。
代码不是很长,就只是有点复杂(⊙o⊙),理解就好,理解就好。 在结尾的时候我外加了一点关于随机函数的使用技巧。
最后呢,希望读者自己将代码写一遍,为了更好的掌握与体会。
分享到:
相关推荐
VB.NET二维数组快速排序(更新) 'OldArrays(),为排序二维数组;NewArrays(),为存放结果数组,SortColumnsOrOrders(),传递排序参数数组,偶数个为排序列号,奇数为升降序,0为升序,1为降序;FieldRow,是否有字段行...
按所推荐的程序在IE下跑了下,的确,排序耗时很小。 代码如下: [removed] /* * 洗牌 */ function ... /* * 快速排序,按某个属性,或按“获取排序依据的函数”,来排序. * @method soryBy * @static * @
易语言数组排序算法集合源码,数组排序算法集合,排序程序,冒泡排序,改冒泡法,双向泡排序,双响泡排序,直接插入排序,地精排序,地精排序2,地精排序3,二分排序,选择排序,梳子排序,希尔排序,快速排序
使用快速排序法对一维数组进行排序,程序完全可以运行,方便大家学习
用c语言数组实现的快速排序算法,用c语言数组实现的快速排序算法
易语言数组快速排序源码,数组快速排序,快速排序_asm,asm快速排序
二维数组的排序,其中包含冒泡排序、选择排序、插入排序和快速选择排序。
易语言文本数组排序集成源码,文本数组排序集成,显示,快速排序
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
利用易语言数据库对多维数组文本项目进行快速排序的模块
Java数组排序:冒泡排序、选择排序 、插入排序 、快速排序、希尔排序、堆排序和归并排序 三种Java数组复制方法 Java数组最大最小值 四种合并Java数组方法 Java数组升降序排序 Java数组查找:二分查找、顺序查找、...
易语言数组排序模块源码,数组排序模块,冒泡,选择_asm,交换_asm,选择_,交换,冒泡_E自带例子_改良后,插入,快速排序,快速排序_asm,asm快速排序,快速排序2,快速排序2_asm,asm快速排序2
VB.NET二维数组快速排序: OldArrays(),为排序二维数组;NewArrays(),为存放结果数组;Header,是否有标题行;SortColumnsOrOrders(),传递排序参数数组,奇数个为排序列号,偶数为升降序,0为升序,1为降序
随机产生一个数组,然后对数组排序,均值 方差 标准差等分析。
c#实现数组排序,包括冒泡排序法、插入排序法、选择排序法、希尔排序法、快速排序法
1.插入排序(直接插入排序、折半插入排序、希尔排序); 2.交换排序(冒泡泡排序、快速排序); 3.选择排序(直接选择排序、堆排序); 4.归并排序;5.基数排序。
选择不同类型的数据类型,完成数组数据的排序操作,排序分别为单向冒泡排序,双向冒泡排序和快速排序。
这个程序的头文件中包含四种排序方法:泡沫排序法(bubble),插入排序法(insertion),快速排序法(quick)和选择排序法(selection)。头文件中还使用了模板技术,以便可以同时实现几种类型的排序算法。 ...
挂号法-自定义数据数组排序。' 挂号法原理:。' 举例:自定义数据类型A,成员1:文本型 成员2:整数型 成员3:字节集型 成员4:文本型 等等...' 变量B:A类型 零维数组 拥有n个成员。' 假设要按成员2来排序。'...