Java常用的经典排序算法：冒泡排序与选择排序
一、冒泡排序
冒泡排序（bubble sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
进一步理解为（假设由小到大排序）：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录的最大记录将位于第n位；然后对（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。
以数组int[] arr = {3,9,5,7,1}为例，冒泡排序的具体步骤如下：
初始状态：[3,9,5,7,1]
第一趟排序过程如下：
第一次arr[0]=3与arr[1]=9比较交换后： [3,9,5,7,1]
第二次arr[1]=9与arr[2]=5比较交换后： [3,5,9,7,1]
第三次arr[2]=9与arr[3]=7比较交换后： [3,5,7,9,1]
第四次arr[3]=9与arr[4]=1比较交换后：[3,5,7,1,9]
第一趟排序最值9出现在最后一位。
第一趟排序后9出现在第n位：[3,5,7,1,9]
第二趟排序后7出现在n-1位：[3,5,1,7,9]
第三趟排序后5出现在n-2位：[3,1,5,7,9]
第四趟排序后3出现在n-3位，完成排序：[1,3,5,7,9]
程序示例如下（假设由小到大排序）：
package com.bhyj;
public class arraysort {
/**
* 冒泡排序
*/
public static void bubblesort(int[] arr) {
/**
* 外循环控制排序趟数
* 总共需要arr.length-1趟
*/
for (int i = 0; i < arr.length - 1; i++) {
/**
* 内循环控制每一趟的比较次数
* 第1趟比较次数为arr.length-1
* 第2趟比较次数为arr.length-1-1
* 第3趟比较次数为arr.length-1-2
* 第i趟比较次数为arr.length-1-(i-1)
* 由于i从0开始，所以第i趟比较次数为arr.length-1-i
*
*/
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(string[] args) {
int[] arr = { 3, 9, 5, 7, 1 };
// 排序前
system.out.print("排序前：");
printarray(arr);
// 排序
arraysort.bubblesort(arr);
system.out.println("");
// 排序后
system.out.print("排序后：");
printarray(arr);
}
/**
* 打印数组
*/
public static void printarray(int[] arr) {
system.out.print("[");
for (int i = 0; i < arr.length; i++) {
system.out.print(arr[i]);
if(i < arr.length-1){
system.out.print(",");
}
}
system.out.print("]");
}
}
输出结果为：
排序前：[3,9,5,7,1]
排序后：[1,3,5,7,9]
冒泡排序时间复杂度:o(n2)
二、选择排序
选择排序（selection sort）的基本思想为（假设由小到大排序）：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到的最小的记录与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。
以数组int[] arr = {3,9,5,7,1}为例，选择排序的具体步骤如下：
初始状态：[3,9,5,7,1]
第一趟排序过程如下：
第一次arr[0]=3与arr[1]=9比较交换后： [3,9,5,7,1]
第二次arr[0]=3与arr[2]=5比较交换后： [3,9,5,7,1]
第三次arr[0]=3与arr[3]=7比较交换后： [3,9,5,7,1]
第四次arr[0]=3与arr[4]=1比较交换后： [1,9,5,7,3]
第一趟排序最值1出现在第一位。
第一趟排序后1出现在第1位：[1,9,5,7,3]
第二趟排序后3出现在第2位：[1,3,9,7,5]
第三趟排序后5出现在第3位：[1,3,5,9,7]
第四趟排序后7出现在第4位，9排在最后一位，完成排序：[1,3,5,7,9]
程序示例如下（假设由小到大排序）：
package com.bhyj;
public class arraysort {
/**
* 选择排序
*/
public static void selectsort(int[] arr) {
/**
* 外循环控制排序趟数
* 总共需要arr.length-1趟
*/
for (int i = 0; i < arr.length - 1; i++) {
/**
* 内循环控制每一趟的比较次数
*/
for (int j = i+1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(string[] args) {
int[] arr = { 3, 9, 5, 7, 1 };
// 排序前
system.out.print("排序前：");
printarray(arr);
// 排序
arraysort.selectsort(arr);
system.out.println("");
// 排序后
system.out.print("排序后：");
printarray(arr);
}
/**
* 打印数组
*/
public static void printarray(int[] arr) {
system.out.print("[");
for (int i = 0; i < arr.length; i++) {
system.out.print(arr[i]);
if(i < arr.length-1){
system.out.print(",");
}
}
system.out.print("]");
}
}
输出结果为：
排序前：[3,9,5,7,1]
排序后：[1,3,5,7,9]
选择排序时间复杂度:o(n2)
关注微信公众号【java典籍】，收看更多java技术干货
▼微信扫一扫下图↓↓↓二维码关注
推荐阅读