快速排序是较好的排序算法,但是只有将它用好的逻辑代码实现才能看出它的威力,本人用几种思维逻辑实现了快速排序,但是运行结果发现,同样是快速排序,不同实现方法运行效率差别相当大,现在把运行效率最好的代码共享。
import java.util.Random;
public class Sort {
private static int count = 0;
/**
* 快速排序的简单实现:
* 1、如果实位置大于0或者结束位置大于总长度时出现数组越界异常,否则转向2
* 2、如果其实位置大于等于结束位置,则返回原数组,否则转向3
* 3、以最后位置为参考位置,并将start位置赋予i,end-1位置赋予j,并且当i<=j时执行循环执行4
* 4、从j开始向前查找到第一个大于等于基准点的数据,找到后从i开始找小于等于基准点的数据,找到后如果符合i<j,则i,j位置数据互换。
* 5、将i和基准点的数据交换。
* 6、递归快速排序(i+1)->end的数据
* 7、快速排序 start->(i-1)的数据
* 8、返回排序后的数组
*
* @param arr
* 要排序的数组
* @param start
* 参与排序的数组的其实位置
* @param end
* 参与排序的数组结束位置
* @return int[] 排序后的数组
*/
public static int[] quickSort(int[] arr, int start, int end) {
count++;// 压栈次数
if (start < 0 || end > arr.length) {
throw new java.lang.ArrayIndexOutOfBoundsException();
} else if (start >= end) {
return arr;
}
int media = arr[end];
int i = start, j = end - 1;
while (i <= j) {
while (j >= i && arr[j] >= media) {
j--;
}
while (i <= j && arr[i] <= media) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
swap(arr, i, end);
quickSort(arr, start, i - 1);// 较小数据快速排序
quickSort(arr, i + 1, end);// 较大数据快速排序
return arr;
}
/**
* 交换数组中的数据
*
* @param numbers
* 数组
* @param pos
* 要交换的数据在数组中的位置
* @param anotherPos
* 要交换的数据在数组中的位置
*/
private static void swap(int[] numbers, int pos, int anotherPos) {
int media = numbers[pos];
numbers[pos] = numbers[anotherPos];
numbers[anotherPos] = media;
}
public static void main(String args[]) {
int[] arr = new int[10000];
for (int i = 0; i < arr.length; i++) {// 生成5000个随机数
arr[i] = new Random().nextInt(50000);
}
long t = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);// 快速排序
System.out.println("排序时间:" + (System.currentTimeMillis() - t));
System.out.println("压栈次数:" + count);
System.out.println("排序后数据:");
for (int i = 0; i < arr.length; i++) {// 循环打印排序后的结果,每行10个
System.out.print(arr[i] + ",");
if ((i + 1) % 10 == 0) {
System.out.print("\n");
}
}
}
}
快速排序源代码说明:
1、递归快速排序算法是采用不断压栈,所以本方法监控了压栈次数。栈的操作非常快,但是栈空间是有限的,所以基本上是空间换时间的做法。
2、如果数据量过大,栈的空间不能满足,可以选择和其它算法结合,折中速度及栈空间的使用。
只需要将
if (start < 0 || end > arr.length) {
throw new java.lang.ArrayIndexOutOfBoundsException();
} else if (start >= end) {
return arr;
}
修改为:
if (start < 0 || end > arr.length) {
throw new java.lang.ArrayIndexOutOfBoundsException();
} else if (start >= end) {
return arr;
}else if (start >= 8) {
return bubbleSort(arr,start,end)
}
注意:swap方法要用private 或者实用final限定符,编译器将进行编译优化,提高运行效率。具体请参考 final、private限定符的使用规则。
分享到:
相关推荐
java 快速排序 折半查找的界面实现 (递归与分治法)
算法,我可以为您详细解释Java中快速排序算法的实现,并提供一个代码示例。快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个...
当然,我可以为您详细解释Java中快速排序算法的实现,并提供一个代码示例。快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个...
java基本排序算法实现,包括快速 选择 插入 希尔 堆 冒泡 交换
文档中涵盖了快速排序的基本概念,包括如何对数组进行排序以及如何在Java中实现快速排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现快速排序,包括详细的代码示例和实现细节。 文档还涵盖了高级主题,...
插入,选择排序的链表实现及快速,希尔,冒泡排序算法实现
八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序,归并排序,基数排序在内的八种排序算法,同时对各种算法的基本特征做出了详细分析: - 算法基本思想 - 算法的...
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
用java实现了10种基础排序,其内容包括: 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.桶排序 9.基数排序 10.计数排序 如有疑问请私信我
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
快速排序算法是基于分治策略的另一个排序算法。其基本思想是:对输入的子数组a[p:r],按以下三个步骤进行排序。 1) 分解(Divide)(2) 递归求解(Conquer)(3) 合并(Merge)
java实现一些基本的算法,如快速排序,BFS,N皇后,最小生成树等
1. 算法思想 选取一个基准值,将待排序数据分为左(小于基准值)右(大于基准值)两个区间,然后对两个分区的数据进行同样的循环操作,最后便可得到一组有序数据。...因此快速排序的平均时间复杂度为$O(n^
插入 选择 冒泡 Shell 归并 快速等各种基本排序算法的Java实现;FYI
快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序。使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好。就平均时间而言,是目前被认为最好的一种内部...
目录插入排序直接插入排序基本原理代码实现性能分析折半插入排序代码实现希尔排序基本原理代码...快速排序基本原理代码实现(递归和非递归)性能分析归并排序基本原理代码实现性能分析排序总结各种排序算法之间的比较...
里面有最基本的几种排序算法,包括选择,插入,冒泡,希尔,快速,合并,堆!用界面化的方式,由菜单开始选择,输入元素个数,随机生成元素,你也可以自己输入,只要改变一下生成函数即可
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
主要实现算法:冒泡排序、选择排序、插入排序、快速排序、合并排序、堆排序。