A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

目前,我们常用的排序无法就是针对数组或者是集合的元素进行的操作,下面是我个人总结的常用的需要掌握的排序方法,时间有限,这一次先总结数组的排序。
      可能对于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就可以了....



  

能坚持看到最后
都是真爱啊
特别感谢
也祝你
在编程的世界里
越久越爱

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马