快速排序:
设定一个枢纽的值,一般以首个元素的值为枢纽的值,把比枢纽小的元元素放在左边,比枢纽值大的元素放在右边,最后把枢纽的值放到合适的位置。根据返回枢纽的位置,对以上过程进行递归。
/**
* EnhancedQuickSort.java
*
* 快速排序
*
* @author Administrator
*/
public class QuickSort {
public static void quickSort(int[] a) {
qSort(a, 0, a.length - 1);
}
/**
* 对下标从s到t的元素进行快速排序。
*/
public static void qSort(int[] a, int s, int t) {
if (s < t) {
int pivot = partition(a, s, t);
qSort(a, s, pivot - 1);
qSort(a, pivot + 1, t);
}
}
/**
* 该方法返回枢纽的下标。
*/
public static int partition(int[] a, int p, int r) {
int i = p, j = r + 1;
int x = a[p];
/**
* 将 >= x的元素交换到右边区域,<= x的元素交换到左边区域。
*/
while (true) {
while (a[++i] < x) {
if (i >= r)
break;
}
while (a[--j] > x)
;
if (i >= j)
break;
Util.swap(a, i, j);
}
a[p] = a[j];
a[j] = x;
return j;
}
public static void main(String[] args) throws Exception {
if (args.length == 0) {
System.out.println("请输入数字以空格隔开");
System.exit(-1);
}
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
// int[] a = new int[100];
// for(int i = 0; i < a.length; i++)a[i] = 100-i;
quickSort(a);
// 输出排序后的数组元素。
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
}
改进型:随机枢纽快速排序RadomQuickSort.java
/**
* RadomQuickSort.java
*
* 随机枢纽快速排序.每次都随机选择无序序列中的一个数为枢纽的值.
*
* @author Administrator
*
*/
public class RadomQuickSort {
public static int radomPartition(int[] a, int p, int r) {
// 生成p到r之间的一个随机数j
int j = (int) Math.round(Math.random() * (r - p)) + p;
Util.swap(a, p, j);
return QuickSort.partition(a, p, r);
}
public static void rQSort(int[] a, int s, int t) {
if (s < t) {
int pivot = radomPartition(a, s, t);
rQSort(a, s, pivot - 1);
rQSort(a, pivot + 1, t);
}
}
public static void radomQuickSort(int[] a) {
rQSort(a, 0, a.length - 1);
}
public static void main(String[] args) throws Exception {
if (args.length == 0) {
System.out.println("请输入数字以空格隔开");
System.exit(-1);
}
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
radomQuickSort(a);
// 输出排序后的数组元素。
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
}
分享到:
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序...快速排序快速排序快速排序快速排序快速排序快速排序快速排序快速排序
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
用C++语言实现的几个常见算法,里面有注解,方便大家理解,简单易学,都可以正常编译运行。
c++ 选择排序 插入排序 快速排序 使用模板写的,感觉不错,哈哈,希望对大家有帮助
C# 常用经典算法,选择排序 冒泡排序 快速排序 插入排序 希尔排序
快速排序,希尔排序快速排序,希尔排序 快速排序,希尔排序
C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例...
快速排序 基础排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序.zip
基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 基于c语言10个数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 ...
呵呵,传上来供大家学习使用~8种排序算法 包括:选择排序 冒泡排序 快速排序 等~~
分治策略 合并排序 快速排序 代码 C语言 是自己写的程序,还请各位指教
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
插入排序 并归排序 桶排序 快速排序这些算法书上的经典算法,给出了算法过程,可供测试实际运行效率或者学习算法本身
C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
不错的练手C语言课程设计例子--10个数据结构课程设计实例、二叉树建立遍历冒泡排序快速排序等 不错的练手C语言课程设计例子--10个数据结构课程设计实例、二叉树建立遍历冒泡排序快速排序等 不错的练手C语言课程设计...
快速排序,比较高效的排序算法之一。这是一个例子,一个关于快速排序的例子。
冒泡法排序c语言程序 冒泡法排序c语言程序 基础排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序