数据结构与算法之排序算法

排序算法是指将一组数据按照特定的顺序进行排列的算法。在计算机科学中，排序算法是最基本的算法之一。常见的排序算法有插入排序、冒泡排序、选择排序、快速排序、归并排序等。排序算法的时间复杂度和空间复杂度是评价算法优劣的重要指标。其中，时间复杂度是指算法执行所需的时间，空间复杂度是指算法执行所需的内存空间。不同的排序算法适用于不同的场景，需要根据具体情况选择合适的算法。

以下是三种常见的排序算法及其实现代码：
1.插入排序
时间复杂度O(n^2)，空间复杂度O(1)，稳定性：稳定
public void sort() {
for (int i = 0; i < arr.length ; i++) {
int e = arr[i];
int j = 0;
for ( j = i;j > 0 && arr[j-1] >e; j--) {
arr[j] = arr[j-1];
}
arr[j] = e;
}
System.out.println(Arrays.toString(arr));
}

2.冒泡排序
时间复杂度O(n^2)，空间复杂度O(1)，稳定性：稳定
public void sort() {
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length- i-1; j++) {
if(arr[j] > arr[j+1]){
swap(j,j+1);
}
}
}
System.out.println(Arrays.toString(arr));
}

3.选择排序
时间复杂度O(n^2)，空间复杂度O(1)，稳定性：不稳定
public void sort() {
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(i,minIndex);
}
System.out.println(Arrays.toString(arr));
}