十大经典排序算法(2022年11月11日更新)
1、冒泡排序
冒泡排序是接下来的十大排序中最简单的排序。
1.1 方法描述
简单来说，排序方法就是重复地走过要排序的数列，一次比较相邻的两个元素，如果顺序不满足从小到大(从大到小)，就将这两个元素交换，重复地进行，知道没有再需要交换。排序方式：In-place（需要申请额外空间-临时变量）
1.2 算法描述
- 从第一个元素开始比较，比较相邻的元素。如果第一个比第二个大(小)，就交换他们两个。
- 对每一对相邻元素做同样的工作，不断重复，直到排序完成。
1.3 动图描述
1.4 代码实现(Java语言)
- 从小到大排序：
package Sort; // 自己定义的包
import java.util.Scanner; // 导入的外部jar包
public class BubbleSort {
public static void main(String[] args) {
/**
* 从小到大排序：
*/
System.out.println("请输入十个数：");
Scanner sc = new Scanner(System .in);
int [] arr = new int[10];
// 数组输入方法:(for循环)
for (int i = 0;i < arr.length;i++){
arr[i] = sc.nextInt();
}
// 双层for循环，第一层循环为每个数除了最后一个数，都要进行党的的一遍循环，故循环次数为（arr.length - 1）次.
for (int i = 0; i <arr.length;i++){
for (int j = 0;j<arr.length-i-1;j++){
// 若两数相比，前数比后数大，因为从小到大排序，故将两个数进行交换。交换需要一个临时变量，用来当中介，进行交换。
if (arr[j+1] < arr[j]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("从小到大排序为：");
// 使用foreach循环进行输出已排序好的数组。
for (int i:arr) {
System.out.print(i+" ");
}
}
}
- 从大到小排序：
package Sort; // 自己定义的包
import java.util.Scanner; // 导入的外部jar包
public class BubbleSort {
public static void main(String[] args) {
/**
* 从大到小：
*/
System.out.println("请输入十个数：");
Scanner scanner = new Scanner(System.in);
int [] arr = new int[10];
for(int i = 0;i <arr.length;i++){
arr[i] = scanner.nextInt();
}
for (int i = 0;i < arr.length; i++){
for (int j = 0; j < arr.length - i - 1; j++){
// 从大到小和从小到大排序基本相同，只有接下来交换的部分，当两数进行比较时，后数大于前数时，进行交换。
if (arr[j+1] > arr[j]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
System.out.println("从大到小为：");
for (int i:arr ) {
System.out.print(i+" ");
}
}
1.5 算法分析
- 最好情况-- O(n)：
初始数组就为从大到小(从小到大)，只需要比较 O(n)，n为数组的元素。 - 最坏情况--O(n2)：
若需要数组为从小到大排序，初始数组为从大到小。最坏的情况就是初始数组为倒序排序，故最坏情况为 O(n2)。所以复杂度为 O(n2) - 稳定性：
稳定。
2、选择排序
选择排序是表现最稳定的排序算法之一。
2.1 方法描述
首先在未排序的序列中找到最小(大)元素，存放到排序序列中的起始位置。然后，再从剩余未排序的元素中继续找最小(大)元素，然后存放到已排序序列的末尾。一次类推，直到所有元素均排序完成。
2.2 算法描述
n个元素的通过直接选择排序经过n-1次选择排序得到有序结果。
- 将数组分为无序区和有序区。初始无序区为所有未排数，有序区为空。
- 第 i 趟排序开始时，当前有序区为[1~i-1]，无序区为[i ~ n]。每趟排序从当前无序区找出最小(最大)元素，将他与 无序区的第一个元素交换。每一趟排序，无序区减少一个元素，而有序区增加一个元素。
- n-1趟结束，数组排序结束。
2.3 动图描述
2.4 代码实现(Java语言)
package Sort;
import java.util.Scanner;
public class SelectionSort {
public static int[] SelectionSort(int[] array) {
if (array.length == 0){
return array;
}
for (int i = 0;i < array.length; i++){
int minIndex = i;
for (int j = i; j < array.length; j++){
if (array[j] < array[minIndex]){ // 找到最小的数
minIndex = j; // 将最小的数的索引保存
}
}
// 将找到的最小数与无序区的第一个数进行交换
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入十个数：");
int [] arr = new int[10];
for (int i = 0;i < arr.length; i++){
arr[i] = scanner.nextInt();
}
int[] sort = SelectionSort(arr);
System.out.println("从小到大排序为：");
for (int i:sort) {
System.out.print(i+" ");
}
}
}
2.5 算法分析
- 最佳情况：
O(n2) - 最坏情况：
O(n2) - 稳定情况：
不稳定。