Java三大排序算法实战
在这里作为本人之前有接触过一点数据结构的内容，在这里是记录我学习Java的过程，如果有所帮助则是锦上添花！
三大排序算法
1、冒泡排序
2、插入排序
3、选择排序
（说是三大排序，其实是最基础和最捞的排序了，但是这是一定要掌握的内容，不容有失。）
Ｏ（ｎ＾２）
1、冒泡排序
实现代码：
public class Main {
public static void main(String[] args) {
int[] arr = {8, 5, 0, 1, 4, 9, 2, 3, 6, 7};
bubble_ordering(arr);
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubble_ordering(int[] arr){
for (int j = 0; j < arr.length - 1; j++){
for (int i = 0; i < arr.length - 1; i++){
if (arr[i] > arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
for (int k = 0; k < arr.length;k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}
}
}
结果：
优化1：
可以观察到其实不用到最后一步已经排序完成了。如何提前结束循环呢，可以判断如果一趟里面没有发生一次交换，就可以结束了。（因为从最左边第一个开始的，如果一趟都没有发生交换，那么就说明已经按顺序排好了。）
因此可以添加一个布尔变量来作为flag判断是否已经排好。
public class Main {
public static void main(String[] args) {
int[] arr = {8, 5, 0, 1, 4, 9, 2, 3, 6, 7};
bubble_ordering(arr);
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubble_ordering(int[] arr){
for (int j = 0; j < arr.length - 1; j++){ //一共n-1趟
boolean flag = true; //用于判断提前结束排序
for (int i = 0; i < arr.length - 1; i++){ //每趟n-1轮 好像还可以优化
if (arr[i] > arr[i+1]){
flag = false; //说明还有交换，不能结束排序
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
if(flag) break; //说明这一趟没发生交换，结束排序
for (int k = 0; k < arr.length;k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}
}
}
输出结果
优化2：
由于每经过一趟，就有一个固定位置，那么接下来的一趟就可以减少一次排序时间（因为最右边那个最必最大）。
因此可以在嵌套的第二个for里面将n-1 改为n-j-1。
public class Main {
public static void main(String[] args) {
int[] arr = {8, 5, 0, 1, 4, 9, 2, 3, 6, 7};
bubble_ordering(arr);
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubble_ordering(int[] arr){
for (int j = 0; j < arr.length - 1; j++){ //一共n-1趟
boolean flag = true; //用于判断提前结束排序
for (int i = 0; i < arr.length - j - 1; i++){ //每趟n-j-1轮
if (arr[i] > arr[i+1]){
flag = false; //说明还有交换，不能结束排序
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
if(flag) break; //说明这一趟没发生交换，结束排序
for (int k = 0; k < arr.length;k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}
}
}
结果
2、插入排序
插入排序其实跟我们打牌一样，摸牌时牌堆时乱序的，但是一张张摸到手中进行排序，使它变得有序了。
代码：
public class Main {
public static void main(String[] args) {
int[] arr = {8, 5, 0, 1, 4, 9, 2, 3, 6, 7};
//bubble_ordering(arr);
insert_ordering(arr);
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
public static void insert_ordering(int[] arr){
for (int i = 1; i<arr.length; i++){
int temp = arr[i]; //把牌拿到手
int j = i - 1;
while(j >= 0 && temp < arr[j]){
arr[j + 1] = arr[j]; //j+1把j的位置占了,相当于一个个向右走
j--;
}
arr[j+1] = temp; //跳出循环了就说明temp找到位置了
for (int k = 0 ; k <arr.length; k++){
System.out.print(arr[k] + " ");;
}
System.out.println();
}
}
}
3、选择排序
选择排序其实就是每次都选择当前数组中最大的数排到最前面
或者最小的数排到最后面
代码：
public class Main {
public static void main(String[] args) {
int[] arr = {8, 5, 0, 1, 4, 9, 2, 3, 6, 7};
//bubble_ordering(arr);
//insert_ordering(arr);
choose_ordering(arr);
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
public static void choose_ordering(int[] arr){
for (int i = 0; i < arr.length - 1; i++){
int min = arr[i], pos = i; //记录数值和位置
for (int j = i + 1; j < arr.length;j++){ //遍历查看最小值
if(arr[j] < min){
min = arr[j];
pos = j;
}
}
int temp = arr[i]; //原来的位置
arr[i] = arr[pos];
arr[pos] = temp; //进行一个交换
for(int k = 0; k < arr.length; k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}
}
}