-
冒泡排序、选择排序、递归排序跟快速排序
2018-01-04 16:41:21用这些排序时,都可以写自己的排序规则。 Java API对Arrays类的说明是:此类包含用来操作数组(比如排序和搜索)的各种方法。 上面两句话话是对其他博客上的引用,不清楚是那篇了,所以就不贴地址了,其实除了...排序算法,基本的高级语言都有一些提供。C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(不是Array)。用这些排序时,都可以写自己的排序规则。
Java API对Arrays类的说明是:此类包含用来操作数组(比如排序和搜索)的各种方法。
上面两句话话是对其他博客上的引用,不清楚是那篇了,所以就不贴地址了,其实除了数组,java对集合也有sort()的排序方法,这里详细写一下对数组的几种常用的排序方法。
快速排序是对选择排序和冒泡排序的优化
选择排序我觉得是最好理解的,冒泡排序推荐看下:https://www.cnblogs.com/shen-hua/p/5422676.html,写的很清楚
冒泡排序:
@Test public void test4() { int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51}; for(int i=0;i<a.length-1;i++) { for (int j = 0; j < a.length - 1-i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } System.out.println(Arrays.toString(a)); }
选择排序:
@Test public void test2() { int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51}; for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { if (a[i] > a[j]) { a[j] = a[i] + a[j]; a[i] = a[j] - a[i]; a[j] = a[j] - a[i]; } } }
递归排序:递归的本质---自身调用自身
# 求阶乘 public static void main(String[] args) { System.out.println(f(5)); System.out.println(5 * 4 * 3 * 2 * 1); } public static int f(int n) { if (1 == n || 2 == n) return n; else return n * f(n - 1); /* * 5*f4 * 5*4*f3 * 5*4*3*f2 * 5*4*3*2 * */ }
/* 斐波那契数列: 0、1、1、2、3、5、8 f0 = 0; f1 = 1; fn = f(n-1) + f(n - 2) (n >= 2) */ public static void main(String[] args) { System.out.println(f(5)); } public static int f(int n) { if (n == 1 || n == 2) { return 1; } else { return f(n - 1) + f(n - 2); } }
快速排序分治法就用到了递归思想,主要有挖坑法和下标交换法,分治也用到交换思想,
挖坑法
package study.test; import java.util.Arrays; public class Mysort { public static void quickSort(int[] arr, int startIndex, int endIndex) { // 递归结束条件:startIndex大等于endIndex的时候(即每部分数组拆分至一个元素) if (startIndex >= endIndex) { return; } // 得到基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 用分治法递归数列的两部分 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } private static int partition(int[] arr, int startIndex, int endIndex) { System.out.println("the begin : " + Arrays.toString(arr)); // 取第一个位置的元素作为基准元素 int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; // 坑的位置,初始等于pivot的位置 int index = startIndex; //大循环在左右指针重合或者交错时结束 while (right >= left) { //right指针从右向左进行比较 while (right >= left) { if (arr[right] < pivot) { arr[left] = arr[right]; index = right; left++; break; } right--; System.out.println("the in one: " + Arrays.toString(arr)); } //left指针从左向右进行比较 while (right >= left) { if (arr[left] > pivot) { arr[right] = arr[left]; index = left; right--; break; } left++; System.out.println("the in two: " + Arrays.toString(arr)); } } arr[index] = pivot; System.out.println("the end : " + Arrays.toString(arr)); return index; } public static void main(String[] args) { int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }
非交换思想,使用数组拆分
package study.test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class JustSort { public static int partition(int[] arr, int start, int end) { int mid = start + (end - start) / 2; //每次取中位数为基准元素 System.out.println("基准元素取中 mid :" + arr[mid]); List<Integer> left = new ArrayList(); List<Integer> rigth = new ArrayList(); for (int i = 0; i <= end; i++) { //遍历数组,使用集合分别存储大于基准数和小于基准数的元素 if (i != mid) { //遍历过错中先隔离基准数,待遍历完毕后存储基准数,保证基准数在数组中下标不变 if (arr[i] <= arr[mid]) { left.add(arr[i]); } if (arr[i] > arr[mid]) { rigth.add(arr[i]); } } } int index = left.size(); //获取数组分治后下一轮数组的长度作为下一次排序的范围 left.add(arr[mid]); //添加基准数 left.addAll(rigth); //此时left集合中存储当次排序后元素 for (int i = 0; i < left.size(); i++) { arr[i] = left.get(i); //将排序后元素从list更新到原数组 } System.out.println(Arrays.toString(arr)); return index; } public static void sort(int[] array, int start, int end) { if (start >= end) { //当拆分数组元素仅有1个时,出现截取数组终止下标比开始下标小1或者相等(第一个元素时相等),此时无需排序 return; } int mid = partition(array, start, end); sort(array, start, mid - 1); //根据基准数切割数组,选取基准数左边数组 sort(array, mid + 1, end); //选取基准数右边数组 } public static void main(String[] args) { int[] arr = {4, 7, 6, 5, 3, 2, 8, 1}; System.out.println("源数组: \n" + Arrays.toString(arr)); sort(arr, 0, arr.length - 1); System.out.println("排序结果: \n" + Arrays.toString(arr)); } }
-
java 快速排序_用Java实现快速排序算法
2020-12-02 08:47:54它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...前言
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
整个过程,我都写到注释里面了。如果不明白,可以打开冒泡排序的章节,用动画的形式来自己观看一下。
代码
package
总结
点击关注不迷路哦,后续有更新会推送给您的。
-
java实现冒泡排序和快速排序
2017-12-08 21:59:19用java实现了冒泡排序和快速排序,冒泡还是比较简单的,但快速排序采坑了,网上有很多代码是有问题的,最后通过分析和实践,终于弄明白了,分享出来以供大家一起学习~~快速排序写了2种实现方法,原理都是一样的,快...用java实现了冒泡排序和快速排序,冒泡还是比较简单的,但快速排序采坑了,网上有很多代码是有问题的,最后通过分析和实践,终于弄明白了,分享出来以供大家一起学习~~
快速排序写了2种实现方法,原理都是一样的,快排的平均时间复杂度是O(N*logN)
实现思路:(基于递归实现)
1.选一个值作为中轴(理想情况选中值最好,但一般使用数组的第一个值)。
2.基于中轴,将数组分为两部分,较小的分在左边,较大的分在右边。
3.对两个子数组分别重复上述过程进行排序。import java.util.ArrayList; import java.util.Arrays; /** * Created by admin on 2017/12/8. */ public class SortArray { public static void main(String[] args) { final int[] arr1 = {3, 12, 3, 15, 2, 89, 45}; final int[] arr2 = {3, 12, 3, 15, 2, 89, 45}; final int[] arr3 = {3, 12, 3, 15, 2, 89, 45}; //调用冒泡 int[] sortResult1 = sort1(arr1); //调用快速 int start = 0; int end = arr2.length-1; int[] sortResult2 = quickSort(arr2,start,end); int[] sortResult3 = quickSort2(arr3, start, end); System.out.println(Arrays.toString(sortResult1)); System.out.println(Arrays.toString(sortResult2)); System.out.println(Arrays.toString(sortResult3)); } //冒泡排序 从大到小 public static int[] sort1(int[] arr){ for (int i = arr.length-1; i > 0; i--){ for (int j=0; j<i; j++){ if (arr[j]<arr[j+1]){ int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } //快速排序方法一 private static int[] quickSort(int[] arr, int low, int high){ if (low < high){ int index = partitions(arr, low, high); quickSort(arr, low, index-1); //递归排序左子数组 quickSort(arr, index+1, high); //递归排序右子数组 } return arr; } public static int partitions(int[] arr, int low, int high){ //arr2 = {3, 12, 3, 15, 2, 89, 45} int index = arr[low]; //中轴 while (low < high){ while (low < high && arr[high] >= index) high--; //arr[high]一直大于index,那么就一直减小high arr[low] = arr[high]; //直到遇到比index小的值 交换到左端 while (low < high && arr[low] <= index) low++; //arr[low]一直小于index,那么就一直增大low arr[high] = arr[low]; //直到遇到比index大的值 交换到右端 } arr[low] = index; //返回的是中轴的位置 return low; } //快速排序方法二 public static int[] quickSort2(int[] arr,int l,int r){ if(l>=r) return arr; int i = l; int j = r; int key = arr[l];//选择第一个数为key while(i<j){ while(i<j && arr[j]>=key)//从右向左找第一个小于key的值 j--; if(i<j){ arr[i] = arr[j]; i++; } while(i<j && arr[i]<key)//从左向右找第一个大于key的值 i++; if(i<j){ arr[j] = arr[i]; j--; } } arr[i] = key; quickSort2(arr, l, i-1);//递归调用 quickSort2(arr, i+1, r);//递归调用 return arr; } }
-
快速排序的递归和非递归实现
2016-02-28 16:28:12写在前面对于经典的排序算法大家都很熟悉,这里提供一个未经过严格测试的快速排序算法代码,仅供学习之用。另外,说几点在写算法时的一般规律或者说快速记忆方法。当然,对于分治类型的算法,一般都存在递归解法和非...写在前面
对于经典的排序算法大家都很熟悉,这里提供一个未经过严格测试的快速排序算法代码,仅供学习之用。
另外,说几点在写算法时的一般规律或者说快速记忆方法。
当然,对于分治类型的算法,一般都存在递归解法和非递归解法两种,这里也给出两种实现。
代码实现
package com.nggirl.test.sort; import java.util.HashSet; import java.util.Set; public class QuickSort { public static void main(String[] args) { int[] sortArray = {1,3,2,6,4,5,9,7,8}; new QuickSort().sort(sortArray, 0, 8); for(int x : sortArray){ System.out.println(x); } System.out.println("============================="); new QuickSort().sortNonRecurse(sortArray, 0, 8); for(int x : sortArray){ System.out.println(x); } } private void sort(int[] sortArray, int start, int end){ if(sortArray == null || sortArray.length == 0){ return; } if(start > end || start > sortArray.length || end - start > sortArray.length){ return; } int pivot = pivot(sortArray, start, end); sort(sortArray, start, pivot-1); sort(sortArray, pivot+1, end); } private void sortNonRecurse(int[] sortArray, int start, int end){ if(sortArray == null || sortArray.length == 0){ return; } if(start > end || start > sortArray.length || end - start > sortArray.length){ return; } class PartValue{ private int start; private int end; public PartValue(int start, int end){ this.start = start; this.end = end; } public int getStart() { return start; } public int getEnd() { return end; } } Set<PartValue> parts = new HashSet<PartValue>(); parts.add(new PartValue(start, end)); while(parts.size() != 0){ Set<PartValue> nextParts = new HashSet<PartValue>(); for(PartValue part : parts){ int pivot = pivot(sortArray, part.getStart(), part.getEnd()); if(part.getStart() < pivot-1){ nextParts.add(new PartValue(part.getStart(), pivot-1)); } if(pivot+1 < part.getEnd()){ nextParts.add(new PartValue(pivot+1, part.getEnd())); } } parts = nextParts; } } private int pivot(int[] sortArray, int start, int end){ int cur = sortArray[start]; while(start < end){ //右侧小的往左移动 while(end > start && sortArray[end] > cur){ end--; } if(end > start){ sortArray[start++] = sortArray[end]; sortArray[end] = cur; } //左侧大的右移 while(start < end && sortArray[start] <= cur){ start++; } if(start < end){ sortArray[end--] = sortArray[start]; sortArray[start] = cur; } } return start; } }
关于递归实现
递归实现的思路很简单,关键是要把握两点。1.终止条件判断;2.递归调用方法。比如,上述代码中的sort方法:
private void sort(int[] sortArray, int start, int end){ if(sortArray == null || sortArray.length == 0){ return; } if(start > end || start > sortArray.length || end - start > sortArray.length){ return; } int pivot = pivot(sortArray, start, end); sort(sortArray, start, pivot-1); sort(sortArray, pivot+1, end); }
其中,第二个if中的start > end是递归的终止条件,其他的都是入参检查。
后续的,pivot方法和分开两次调用的sort,就是递归过程。
对于正式的代码,一般来说在递归主方法调用的前面会加上一个包装方法,用来处理条件检查或者主方法所需数据的准备。类似于:
packSort(int[] sortArray, int start, int end){ if(sortArray == null || sortArray.length == 0){ return; } if(start > end || start > sortArray.length || end - start > sortArray.length){ return; } sort(sortArray, start, end); } private void sort(int[] sortArray, int start, int end){ //终止条件 if(start > end){ return; } //递归过程---裂变 int pivot = pivot(sortArray, start, end); sort(sortArray, start, pivot-1); sort(sortArray, pivot+1, end); }
非递归实现
对于非递归实现,如果你熟悉二叉树的遍历过程那么大概应该知道:深度优先遍历要用堆栈去辅助,广度优先遍历要用队列去辅助。
对于分治类型的算法都可以类比于树的广度优先遍历,也就是用队列做辅助存储,把后续需要递归遍历的入参插入到队列尾部。
当然,存储的方式不一定必须使用队列,但原理都是一样的,就是存储后续遍历的入参,也就是条件。
这里使用的是不断更新的一个HashSet去存储下一个水平层的所有遍历条件。(可以把二分的过程,想象成一个树状结构,每一次递归,完成树状的一个水平层。)
递归的条件,这里放到了一个局部内部类里面(因为这个类的有效范围仅仅是sortNonRecurse里面,所以使用了局部的内部类):
class PartValue{ private int start; private int end; public PartValue(int start, int end){ this.start = start; this.end = end; } public int getStart() { return start; } public int getEnd() { return end; } }
当然,这里选择HashSet可以看做一个败笔,用一个ArrayList相对来说更能够节省一些不必要的空间。
pivot这个关键方法
这里简单说一下pivot这个方法的过程(这里没有给出详细的解说,仅是给出了一个记忆的线索):
首先,选择最左侧的值作为pivot-value;
然后,用3个while循环确定pivot的最终位置。内层的两个循环先把右侧第一个小于pivot-value的值移到左侧。再把左侧第一个大于pivot-value的值移动到右侧。由外边的循环不断的完成这个过程。直到start=end为止。
最后,返回start值,此时的start就是要找的划分为止,也就是pivot。对于第一个步骤还可以采用随机选取的方式,避免sortArray有序时带来的低效。
-
递归 java_递归就这么简单
2021-03-05 14:22:21递归介绍本来预算此章节是继续写快速排序的,然而编写快速排序往往是递归来写的,并且递归可能不是那么好理解,于是就有了这篇文章。在上面提到了递归这么一个词,递归在程序语言中简单的理解是:方法自己调用自己... -
Java中的快速排序算法
2020-03-19 17:15:10快速排序是一种比较常用的排序算法,它的原理是先在待排序的区间中,找一个基准值,再遍历整个待排序区间,将比基准值小(可以等于)的值放到基准值...用递归方法实现就是在其中主要的就是分组的过程,再完成递归即... -
最简单的java递归_递归就这么简单
2021-03-16 10:16:18递归介绍本来预算此章节是继续写快速排序的,然而编写快速排序往往是递归来写的,并且递归可能不是那么好理解,于是就有了这篇文章。在上面提到了递归这么一个词,递归在程序语言中简单的理解是:方法自己调用自己... -
java快速排序实现
2015-07-24 22:28:07我这里是实现快速排序,用中间的数字(n)作为对比的对象,从数组的前面(位置i)开始找到比这个n大的,再从后面(位置j)找到比n小的,两个进行对换,知道这个i和j相遇,就终止此轮的循环,然后再继续循环(递归法)... -
排序算法---(4)快速排序---Java实现
2018-03-17 19:07:25写在前面: 快速排序是冒泡排序的升级,他的排序思想为:对于给定的一组记录,选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准... -
java实现归并排序
2020-11-04 11:58:05用java写归并排序 主要思想:先分再合,使用分治的方法 1,第一步,先说如何分 假设有数组8个数字,先分为4,在分为2,再分为1 这边使用递归,详情见图片 这样的话就将所有的数据递归,即将所有的数据给分开,再来... -
JAVA上百实例源码以及开源项目
2016-01-03 17:37:40Java访问权限控制,为Java操作文件、写入文件分配合适的权限,定义写到文件的信息、定义文件,输出到c:/hello.txt、写信息到文件、关闭输出流。 Java绘制图片火焰效果 1个目标文件 摘要:Java源码,图形操作,火焰... -
java 面试题 总结
2009-09-16 08:45:34Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap... -
最新Java面试宝典pdf版
2011-08-31 11:29:22用JAVA实现一个快速排序。 79 11、有数组a[n],用java代码将数组元素顺序颠倒 80 12.金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。 81 三. html&JavaScript&ajax... -
Java面试宝典2010版
2011-06-27 09:48:27用JAVA实现一个快速排序。 11、有数组a[n],用java代码将数组元素顺序颠倒 80 12.金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。 三. html&JavaScript&ajax部分 1... -
JAVA上百实例源码以及开源项目源代码
2018-12-11 17:07:42在有状态SessionBean中,用累加器,以对话状态存储起来,创建EJB对象,并将当前的计数器初始化,调用每一个EJB对象的count()方法,保证Bean正常被激活和钝化,EJB对象是用完毕,从内存中清除…… Java Socket 聊天... -
java面试宝典2011整理有答案
2011-11-09 13:36:06用JAVA实现一个快速排序。 79 11、有数组a[n],用java代码将数组元素顺序颠倒 80 12.金额转换,阿拉伯数字的金额转换成中国传统的形式如:(¥1011)->(一千零一拾一元整)输出。 81 三. html&JavaScript&ajax... -
java范例开发大全
2013-03-08 20:06:54实例78 快速排序法 106 第6章 字符串(教学视频:138分钟) 108 6.1 字符串类String 108 实例79 创建字符串类 108 实例80 如何使用charAt()方法计算重复字符 109 实例81 按字母顺序比较大小 110 实例82 首尾相连 111... -
Java 面试宝典
2013-02-01 10:02:088、用最有效率的方法算出 2 乘以 8 等於几? ............................................................. 10 9、请设计一个一百亿的计算器 .................................................................... -
超级有影响力霸气的Java面试题大全文档
2012-07-18 09:47:04Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、... -
java范例开发大全源代码
2011-10-30 23:31:51实例78 快速排序法 106 第6章 字符串(教学视频:138分钟) 108 6.1 字符串类String 108 实例79 创建字符串类 108 实例80 如何使用charAt()方法计算重复字符 109 实例81 按字母顺序比较大小 ... -
Java范例开发大全 (源程序)
2011-04-27 07:47:22实例78 快速排序法 106 第6章 字符串(教学视频:138分钟) 108 6.1 字符串类String 108 实例79 创建字符串类 108 实例80 如何使用charAt()方法计算重复字符 109 实例81 按字母顺序比较大小 110 ... -
Java范例开发大全(全书源程序)
2013-04-05 11:50:26实例78 快速排序法 106 第6章 字符串(教学视频:138分钟) 108 6.1 字符串类String 108 实例79 创建字符串类 108 实例80 如何使用charAt()方法计算重复字符 109 实例81 按字母顺序比较大小 110 实例82 ... -
快速排序就这么简单 归并排序就这么简单 二叉树就这么简单 堆排序就这么简单 希尔排序就这么简单 基数排序就这么简单 八大基础排序总结 Java实现单向链表 栈和队列就是这么简单 十道简单算法题 十道算法题【二】 :...
-
在Java中,我们一般通过集成Thread类和实现Runnnable接口,调用线程的start()方法实现线程的启动。但如果并发的数量很多,而且每个线程都是执行很短的时间便结束了,那样频繁的创建线程和销毁进程会大大的降低系统...
-
做了一个小时的面试题(没有过 希望大家帮忙答下 虽然很幼稚 毕竟每个人都是这么过来的吗 感激了!...
2010-04-16 11:10:58递归地使用快速排序方法对right 进行排序 所得结果为l e f t + m i d d l e + r i g h t 37、关于模块间的设计原则? 规范要一样 38、项目过程一般是怎样的?你参加过几个项目开发?参加过的项目流程是怎样的... -
但是要记住学习算法最关键的还是解题思路和方法,用什么语言实现是其次的,如果你时间比较多我是建议你用 Java 语言再实现一遍。 《labuladong的算法小抄》 非常推荐!这是一本很新的书,写书前作者在 Github 开源...
-
-
-
recursiveSort : 递归快速排序 fastStackSort : 栈快速排序 upsideDown : 将数组颠倒 integersToInts : Inteher数组转换成int数组 toString : 将给定的数组转换成字符串 Assets目录数据库相关 -> ...