Java中对数组的排序方法总汇分析
1.冒泡排序
public void bubbleSort(int a[]) {
int n = a.length;
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1; j++)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
先拿出来数组中的第一个数,然后后面的数进行比较,规则是谁大取谁,也就 是说第一轮比较出来了一个最大的值
2. 选择排序
public void selectiveSort(int arr[]) {
for (int i = 0; i < arr.length; i++) {
// 这里实现的方法是将前一个数依次与后面的数据进行比较
for (int j = i + 1; j < arr.length; j++) {
// 如果前一位置的数据大于后一位置的数据,那么就将其他进行置换,也就是说将最小的数排列在了左面
if (arr[i] > arr[j]) {
int tep = arr[i];// 实现两个变量的值互换,由此可以排列出数组从小到大
arr[i] = arr[j];
arr[j] = tep;
}
}
}
}
3.快速排序
* 快速排序是对冒泡排序的一种改进。
* 它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
* 最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)
排序过程分析
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序;
*设要排序的数组是A[0]……A[N-1],
*首先任意选取一个数据(通常选用第一个元素)作为基准点,
*然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,
*然后采用分治策略,分别以同样的方式排序前面和后面的数据。
*值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
排序过程可分为:
1、设置两个变量X、Y,排序开始的时候 X:=1,Y:=N;
2、以第一个数组元素作为关键数据,赋值给number,即number:=A[1];
3、从Y开始向前搜索,即由后开始向前搜索(Y:=Y-1),找到第一个小于number的值,两者交换;
4、从X开始向后搜索,即由前开始向后搜索(X:=X+1),找到第一个大于number的值,两者交换;
4、重复第3、4步,直到XY=J;
例如:待排序的数组A的值分别是:(初始关键数据number:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
进行第一次交换后: 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找)
进行第二次交换后: 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )
进行第三次交换后: 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找)
进行第四次交换后: 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )
此时再执行第三步的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。
相关文章
- java.lang.ClassCastException: java.util.LinkedHashMap cannot be cast to com.gzl.cn.bean.Employee
- Java中的信号量Semaphore
- java Collections.sort()实现List排序自定义方法
- 【Java】java数据库连接池配置的几种方法
- 【Bug】idea 连接postgresql数据库超时 [08001] 尝试连线已失败。 java.net.SocketTimeoutException: connect timed out.
- 系统学习JAVA第十五天(Match类下的方法,日期相关类,处理异常)
- java 数组声明方法
- java 使用反射调用可变参数方法
- java.io.FileNotFoundException: E:workwork (拒绝访问。)
- Java 8新特性——default方法(defender方法)介绍
- java中遍历Map几种方法
- Java学习---JAVA的类设计
- 关于Java数组的12个最佳方法
- Java小白入门200例16之方法的定义和使用
- Java小白入门200例64之Java复制(拷贝)数组的几种方法
- Java hutool/java 常用方法
- 最简单的方法搞懂java自增(++)和自减(--)(学不会来打我)