三种排序方法

74 阅读 0 评论 49 点赞

我是靠谱客的博主单纯酸奶，最近开发中收集的这篇文章主要介绍三种排序方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

冒泡排序

原理：对比相邻的元素值，如果满足条件就交换元素值，把较小的元素值移动到数组前面，把大的元素值移动到数组后面（也就是交换两个元素的位置），这样数组元素就像气泡一样从底部上升到顶部。
例如数组{5，3，-8，9，-1}，冒泡排序过程如下
5，3，-8，9，-1
3，5，-8，9，-1
3，-8，5，9，-1
3，-8，5，9，-1
3，-8，5，-1，9
通过四次比较，此时取得整个数组中最大值9
3，8，5，-1，9
3，8，5，-1，9
3，5，8，-1，9
3，5，-1，8，9
通过三次比较，取得仅次最大值的值8
3，5，-1，8，9
3，5，-1，8，9
3，-1，5，8，9
通过两次比较，取得大小排第三的值5
3，-1，5，8，9
-1，3，5，8，9
最后比较获得最后两值-1，3的大小，完成排序

代码如下：
package com.briup.day8;

public class A {
public static void main(String[] agrs) {
int[] arr = {90,81,87,32,21,93};
for(int i = 0; i < arr.length ; i++) {
for(int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
show(arr);
System.out.println();
}
}

public static void show(int[] arr) {
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}

}

选择排序

原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
例如数组{5，3，-9，1，-6}，选择排序过程如下
5，3，-9，1，-6
3，5，-9，1，-6
-9，5，3，1，-6
-9，5，3，1，-6
-9，5，3，1，-6
通过四次比较取得数组中的最小值-9
-9，5，3，1，-6
-9，3，5，1，-6
-9，1，5，3，-6
-9，-6，5，3，1
通过三次比较取得第二小的值-6
-9，-6，5，3，1
-9，-6，3，5，1
-9，-6，1，5，3
通过两次比较取得第三小的值1
-9，-6，1，5，3
-9，-6，1，3，5
最后比较3，5的大小，完成排序

代码如下：
package com.briup.day8;

public class B {
public static void main(String[] agrs) {
int[] arr = {90,8,1,4,5,7};
for(int i = 0; i < arr.length; i++) {
for(int j = i+1; j < arr.length; j++) {
if(arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
show(arr);
System.out.println();
}
}
public static void show(int[] arr) {
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

插入排序

原理：从第一个元素开始，左边视为已排序数组，右边视为待排序数组，从左往右依次取元素，插入左侧已排序数组，对插入新元素的左侧数组重新生成有序数组
需要注意的是，在往有序数组插入一个新元素的过程中，我们可以采用按顺序循环比较，也可以通过折半查找法来找到新元素的位置，两种方式的效率取决于数组的数据量
例如数组{1，-3，5，2，-6}，插入排序过程如下：
1，-3，5，2，-6
-3，1，5，2，-6
-3，1，5，2，-6
-3，1，5，2，-6
-6，-3，1，5，2
通过四次比较，取得的数组中的最小值-6
-6，-3，1，5，2
-6，-3，1，5，2
-6，-3，1，5，2
-6，-3，1，5，2
三次比较获得第二小的值-3
-6，-3，1，5，2
-6，-3，1，5，2
-6，-3，1，5，2
通过两次比较获得第三小的值1
-6，-3，1，5，2
-6，-3，1，2，5
最后比较2，5的大小，完成排序

代码如下：
package com.briup.day8;

public class C {
public static void main(String[] args) {
int[] arr = {2,5,1,3,6};
for(int i = 1; i < arr.length; i++) {
for(int j = i; j > 0; j–) {
if(arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
} else {
break;
}
}
show(arr);
System.out.println();
}
}
public static void show(int[] arr) {
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}