程序员必会的经典排序算法（一）冒泡排序

时间：2022-03-22 00:28:37

排序算法

 尊重劳动成果，请访问CSDN著者原文链接 http://blog.csdn.net/zixiao217/article/details/51960532
 排序，一定程度上就是比较，比较是过程（貌似是唯一手段），再决定是否交换，结果就是排序。
 在东陆学院，假定小一18岁（age_yiyi），小尤17岁（age_yoyo），对于我们自然人来说，我们知道小一是比小尤大一岁的，因为18减去17比0要大。
 而对于计算机来说（程序），给出两个数，要比较它们的大小，同样采用上述方案。
 计算机很傻（AlphaGo表示不服），所以程序员首先要告诉它怎么认定两个数的大小关系（a - b > 0, 则表示a > b），然后将大的放到后面(b, a)，得到排好序的序列（b, a）。

制定大小规则

/**
*  @param age_yiyi
*  @param age_yoyo
* <pre>如果age_yiyi大于age_yoyo就返回正数1，否则返回负数-1</pre>
*/
int compare(int age_yiyi, age_yoyo){
return age_yiyi > age_yoyo ? 1 : -1;
}

 或者为了更好理解，加入第一个数大于第二个数我们返回真true，否则返回false

/**
*  @param age_yiyi
*  @param age_yoyo
* <pre>如果age_yiyi大于age_yoyo就返回真true，否则返回false</pre>
*/
boolean greaterThan(int age_yiyi, int age_yoyo){
return age_yiyi > age_yoyo ? true : false;
}

决定是否交换

 我们要排序，想将大的数放到后面，那么首先比较两个数的大小，如果第一个数大，则交换两个数（把大的换到后面去），否则不交换。

/**
*  @param age_yiyi
*  @param age_yoyo
* <pre>交换方法：如果 age_yiyi 大于 age_yoyo，就交换两个的位置，将大的换到后面去，排成从小到大序列 
* </pre>
*/
void swap( int age_yiyi, int age_yoyo ){
int temp = 0;
/*
 step1.交换两个数，借助辅助变量temp，
 step2.交换的时候，先将第一个数赋值给temp，
 step3.再将第二个数赋值给第一个数，这时候第一个数变成了较小的那个数（第二个数）了
 step4.最后将temp（第一步保存的大数的值）赋值给第二个数，这样第二个数就是较大的数了
 */
if(greaterThan(age_yiyi, age_yoyo )){
        temp = age_yiyi;
        age_yiyi = age_yoyo;
        age_yoyo = temp;
    }
}

冒泡排序

冒泡排序的思路

 给定一组数据N个数：
 从第一个数开始起，依次和它之后的那个数比较，如果前面的数大于后面的数，就交换它们在序列中的位置，直到最后一个数，这样就得到最大的数放到这组数的末尾，这样叫做一趟。
 然后从第二个数开始，依次记性第一步一样的操作，这样得到第二大的数放到倒数第二的位置，这是第二趟。
 ……
 第N-1个数开始，与它后面的数比较，确定最小数的位置。
 这样经过N-1趟，这N个数据就排成了从小到大的有序升序序列了。

 场景：东路学院，现在宿舍又住进一位室友小莹19岁（age_ynyn），现在她们三个按年龄排位确立大姐的身份。

int[] studentArr = {18, 17, 19};
for(int i = 0; i < studentArr.length; i++){
for(int j = i + 1; j < studentArr.length; j++){
        swap(studentArr[i], studentArr[j]);
    }
}

 完整代码如下:

package org.byron4j.basic.sort;

public class BubbleSortUtil {
public static void main(String[] args){
int[] studentArr = {18, 17, 19};
for(int a : studentArr){
            System.out.print(a + "\t");
        }
        System.out.println("\n--------冒泡排序后--------");
        bubbleSort(studentArr);
    }

/**
 * 冒泡排序
 */
public static void bubbleSort(int[] studentArr) {
for (int i = 0; i < studentArr.length; i++) {
for (int j = i; j < studentArr.length -1; j++) {
if( greaterThan(studentArr[j], studentArr[j + 1]) ){
int temp = 0;
                    temp = studentArr[j];
                    studentArr[j] = studentArr[j + 1];
                    studentArr[j + 1] = temp;
                }
            }
            System.out.print("冒泡第 - " + (i + 1) + "趟后： ");
for(int a : studentArr){
                System.out.print(a + "\t");
            }
            System.out.println("");
        }
    }

/**
 * 交换函数，如果第一个数大于第二个数，就交换它们的位置，将大数换到后面去
 */
public static void swap(int age_yiyi, int age_yoyo) {
int temp = 0;
if (greaterThan(age_yiyi, age_yoyo)) {
            temp = age_yiyi;
            age_yiyi = age_yoyo;
            age_yoyo = temp;
        }
    }

/**
 * 判断大小的方法，第一个数大于第二个数返回true，否则返回false
 */
public static boolean greaterThan(int age_yiyi, int age_yoyo) {
return age_yiyi > age_yoyo ? true : false;
    }
}

 运行结果

18  17  19  
--------冒泡排序后--------
冒泡第 - 1趟后： 17   18  19  
冒泡第 - 2趟后： 17   18  19  
冒泡第 - 3趟后： 17   18  19

 注意* 在完整代码示例中不要在bubbleSort方法中调用swap方法去进行交换，因为变成了值传递，不会交换数组元素的位置。

public static void bubbleSort(int[] studentArr) {
for (int i = 0; i < studentArr.length; i++) {
for (int j = i; j < studentArr.length -1; j++) {
//基本类型进入swap后是值传递，只会在swap方法中交换两个值，
//出了swap方法， studentArr的元素并不会交换
                swap(studentArr[j], studentArr[j + 1]);
            }
        }
    }
标签：

相关文章