黑马程序员技术交流社区
标题:
【广州校区】java常用的数组排序方式的详解
[打印本页]
作者:
Maymaymay
时间:
2017-12-14 14:23
标题:
【广州校区】java常用的数组排序方式的详解
目前，我们常用的排序无法就是针对数组或者是集合的元素进行的操作，下面是我个人总结的常用的需要掌握的排序方法，时间有限，这一次先总结数组的排序。
可能对于0基础或者刚刚学习编程的童鞋，像冒泡和直接排序的算法特别是两个for循环怎么写容易弄混了，通过面试交流感觉这部分童鞋主要是对这种算法的思想不是很理解，以下我的总结是比较详细和啰嗦的，有兴趣不嫌弃的伙伴可以看看，有补充的多多分享、有错误的多多纠正，小女子不胜感激
大方向分类
数组：
（1）冒泡排序
（2）选择/直接排序
（3）数组工具类
开始分点总结：
冒泡排序
public class Test {
/*
冒泡排序
（1）比较方式：相邻两个元素进行比较,如果满足条件就进行位置置换。
（2）原理：内循环结束一次，最值出现在尾角标位置。
*/
public static void main(String[] args) {
int arr[]={8,5,3,1,6};
bubbleSort(arr);
}
public static void bubbleSort(int[] arr)
{
for(int i=0; i<arr.length-1; i++)
{
for(int j=0; j<arr.length-i-1; j++)//-x:让每次参与比较的元减。
//-1:避免角标越界。
{
if(arr[j]>arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
//输出数组内容
for (int j = 0; j < arr.length; j++) {
System.out.println(arr[j]);
}
}
}
step1:先理解两个for循环
for(int i=0; i<arr.length-1; i++){
for(int j=0; j<arr.length-i-1; j++){
}
}
下面是我呕心沥血写出来的具体的交换过程！！！！(从小到大排序、升序排序)
第1次比较，当i=0,i<4,j<4
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
}
}
j=0的时候, 5 8 3 1 6
J=1的时候, 5 3 8 1 6
j=2的时候, 5 3 1 8 6
j=3的时候, 5 3 1 6 8
第1次比较之后最大的数8已经冒到最后了
第2次比较，当i=1,i<4,j<3
for(int i=1; i<4; i++){
for(int j=0; j<3; j++){
}
}
j=0的时候, 3 5 1 6 8
J=1的时候, 3 1 5 6 8
j=2的时候, 3 1 5 6 8（5和6的位置是符合排序的要求的，所以不需要交换）
第2次比较之后倒数第二大的数6已经冒到倒数第二个位置
第3次比较，当i=2,i<4,j<2
for(int i=2; i<4; i++){
for(int j=0; j<2; j++){
}
}
j=0的时候, 1 3 5 6 8
J=1的时候, 1 3 5 6 8（3和5的位置是符合排序的要求的，所以不需要交换）
第3次比较之后倒数第三大的数5已经冒到倒数第三个位置
第4次比较，当i=3,i<4,j<1
for(int i=3; i<4; i++){
for(int j=0; j<1; j++){
}
}
j=0的时候, 1 3 5 6 8（1和3的位置是符合排序的要求的，所以不需要交换）
第4次比较之后倒数第四大的数3已经冒到倒数第四个位置，最小的数在最前面位置，完成排序。
Step2：定义if语句实现交换两个值
if(arr[j]>arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
因为冒泡排序的比较方式是相邻两个元素进行比较的，所以第二个元素的角标肯定是第一个元素的角加1：if(arr[j]>arr[j+1])；
如果要求升序排序：用>(把最大的数冒到最后)if(arr[j]>arr[j+1])
如果要求降序排序：用<(把最小的数冒到最后)if(arr[j]<arr[j+1])
最后定义一个中间变量temp，主要是用于交换的。
第一次这样去总结这个算法，刚码完第一个算法我就我感觉整个人....都...不....好....了.....
对于算法我也是有爱有恨的
我自己第一次被面试到算法的时候，
明明我刚刚前一秒背的那个熟啊，默写都不止十遍了
面试官一问我那个胸有成竹啊
当我说完冒泡排序的时候很自信的时候，
面试官问我
你是在说冒泡排序还是直接排序
我就知道果然我还是背不住
当时就是那个for循环和if判断老是弄混了，
面试官一问然后加上紧张整个人都蒙逼
所以理解真的是蛮重要的
用的多也能够比较深刻记得
吃过亏也能促使我们逼自己去理解和应用
总得选一种适合自己的方式去掌握吧
选择排序
/*
选择排序
（1）比较方式：以一个角标的元素和其他元素进行比较。
（2）原理：在内循环第一次结束，最值出现的头角标位置上。
*/
public class selectSort {
public static void main(String[] args) {
int arr[]={8,5,3,1,6};
selectSort(arr);
}
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {//为什么y的初始化值是 i+1?因为每一次比较，都用i角标上的元素和下一个元素进行比较
if (arr>arr[j]) {
int temp=arr;
arr=arr[j];
arr[j]=temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr);
}
}
}
step1:先理解两个for循环
for(int i=0; i<arr.length-1; i++){
for(int j=i+1; j<arr.length; j++){
}
}
下面是我呕心沥血写出来的又一个具体的交换过程！！！！（从大到小排序、降序排序）
第1次比较，当i=0,i<4,j<5
for(int i=0; i<4; i++){
for(int j=1; j<5; j++){
}
}
j=1的时候, 8 5 3 1 6
j=2的时候, 8 5 3 1 6
j=3的时候, 8 5 3 1 6
j=4的时候, 8 5 3 1 6
第1次比较之后最大的数8排在最前面
第2次比较，当i=1,i<4,j<5
for(int i=1; i<4; i++){
for(int j=2; j<5; j++){
}
}
j=2的时候, 8 5 3 1 6
j=3的时候, 8 5 3 1 6
j=4的时候, 8 6 3 1 5
第2次比较之后第二大的数6排在第二位置
第3次比较，当i=2,i<4,j<5
for(int i=2; i<4; i++){
for(int j=3; j<5; j++){
}
}
j=3的时候, 8 6 3 1 5
j=4的时候, 8 6 5 1 3
第3次比较之后第三大的数5排在第三位置
第4次比较，当i=3,i<4,j<5
for(int i=3; i<4; i++){
for(int j=4; j<5; j++){
}
}
j=4的时候, 8 6 5 3 1
第4次比较之后第四大的数3排在第四位置，最小的数1在最后位置，完成排序
Step2：定义if语句实现交换两个值
if(arr>arr[j])
{
int temp = arr;
arr = arr[j];
arr[j] = temp;
}
直接排序的比较方式是以一个角标的元素和其他元素进行比较的，每比较一次，外循环的一个数就需要跟内循环的每一个数依次比较一次，所以判断条件为：if(arr>arr[j])；
如果要求升序排序：用>（实现升序）if(arr>arr[j])
如果要求降序排序：用<（实现降序）if(arr<arr[j])
最后定义一个中间变量temp，主要是用于交换的。
数组工具类-Arrays
使用数组工具类Arrays的sort()方法也可以对数组元素进行快速排序，API文档介绍得比较明白，我就直接截图了：
代码如下：
import java.util.Arrays;
/*
* 数组工具类-Arrays
* （1）直接使用sort()方法可以实现升序排序，然后遍历数组输出
* （2）如果使用sort()方法排序后，想要降序输出，只需要将for循环进行修改
*/
public class halfSeach {
public static void main(String[] args) {
int arr[]={8,5,3,1,6};
Arrays.sort(arr);
//输出(升序)
for (int i = 0; i < arr.length; i++) {
System.out.println(arr);
}
//降序输出
for (int i = arr.length-1; i >=0; i--) {
System.out.println(arr);
}
}
}
API文档中，可以查到Arrays的sort()方法使用如下，详细的就自己看API就可以了....
能坚持看到最后
都是真爱啊
特别感谢
也祝你
在编程的世界里
越久越爱
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2