备战第十六届蓝桥杯——排序（冒泡、选择、插入）
学习排序算法的目的
（一）基础编程能力提升
理解算法逻辑：排序算法是计算机科学的基础内容。学习排序算法能够让开发者深入理解计算机处理数据的基本方式，如比较、交换和移动数据元素等操作。这有助于建立起严谨的编程思维，是进一步学习复杂算法和数据结构的重要基石。 代码实现能力锻炼：通过用 Java 实现各种排序算法，可以提高编写代码的能力。包括循环结构、条件判断、数组操作等基本编程技巧在排序算法中都有广泛应用，能够让开发者更加熟练地运用 Java 语言。
（二）性能优化考量
时间和空间复杂度分析：不同的排序算法具有不同的时间复杂度和空间复杂度。例如，简单的排序算法（如冒泡排序和选择排序）在最坏情况下时间复杂度为O(n²)，而更高效的排序算法（如快速排序、归并排序）在平均情况下时间复杂度为O(nlogn)。了解这些特性可以帮助开发者根据具体的应用场景和数据规模选择最合适的排序方法，以优化程序的性能。 实际应用中的优化决策：在处理大量数据时，排序操作的效率可能会对整个程序的性能产生重大影响。例如，在数据库管理系统中，数据的排序操作频繁出现，选择高效的排序算法能够大大提高系统的响应速度和处理能力。
（三）面试和学术要求 求职面试必备知识：在软件开发岗位的面试中，排序算法是常见的考点。能够熟练掌握并讲解排序算法的原理、实现方式以及时间和空间复杂度等内容，是展示自己编程基础和算法能力的重要方式。 学术研究和课程学习：在计算机科学相关的学术课程和研究中，排序算法是数据结构和算法领域的基本内容。掌握排序算法有助于理解更高级的学术概念，如算法设计与分析、数据挖掘中的排序应用等。
通用数组
int [] arr = {12,31,24,35,32,43,64,567,456,876,968,7,54632,45,435,346,45,74};冒泡排序
基本思想：冒泡排序的基本原理是比较相邻的元素，如果顺序不对（如从小到大排序时，前面的元素大于后面的元素），则交换它们的位置。每一轮遍历都会将未排序部分的最大元素 “冒泡” 到最后位置。经过多轮遍历，直到整个数组有序。
举例说明：对于数组int[] arr = {4, 3, 5, 1, 2}。第一轮比较，首先比较 4 和 3，因为 4 > 3，交换它们的位置得到{3, 4, 5, 1, 2}；接着比较 4 和 5，位置不变；再比较 5 和 1，交换得到{3, 4, 1, 5, 2}；继续比较 5 和 2，交换得到{3, 4, 1, 2, 5}。此时最大元素 5 已经 “冒泡” 到最后位置。然后对前面的{3, 4, 1, 2}重复这个过程。
package temp01;
public class Demo1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 12, 31, 24, 35, 32, 43, 64, 567, 456, 876, 968, 7, 54632, 45, 435, 346, 45, 74 };
bubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
选择排序
基本思想：选择排序的基本思路是在未排序的数组中找到最小（或最大）的元素，将其与数组的第一个（或最后一个）未排序元素交换位置。然后，在剩下的未排序元素中继续寻找最小（或最大）元素，重复这个过程，直到整个数组排序完成。 举例说明：假设有一个数组int[] arr = {5, 3, 4, 1, 2}。第一轮排序，在整个数组中找到最小的元素 1，将它与第一个元素 5 交换位置，数组变为{1, 3, 4, 5, 2}。第二轮，在剩下的{3, 4, 5, 2}中找到最小元素 2，与第二个元素 3 交换位置，得到{1, 2, 4, 5, 3}，以此类推，直到数组完全排序。
package temp01;
public class demo2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 12, 31, 24, 35, 32, 43, 64, 567, 456, 876, 968, 7, 54632, 45, 435, 346, 45, 74 };
selectionSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换元素
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
插入排序
基本思想：插入排序的基本思路是将未排序的元素逐个插入到已排序的部分合适的位置。从第二个元素开始，将其与前面已排序的元素依次比较，如果小于前面的元素，则将前面的元素向后移动一位，直到找到合适的位置插入该元素。
举例说明：对于数组int[] arr = {5, 3, 4, 1, 2}。首先将 3 与 5 比较，因为 3 < 5，将 5 向后移动一位，把 3 插入到 5 前面，得到{3, 5, 4, 1, 2}。接着处理 4，将 4 与 5 比较，4 <5，将 5 向后移动一位，再将 4 与 3 比较，4> 3，把 4 插入到 3 和 5 之间，得到{3, 4, 5, 1, 2}，依此类推。
package temp01;
public class demo3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 12, 31, 24, 35, 32, 43, 64, 567, 456, 876, 968, 7, 54632, 45, 435, 346, 45, 74 };
insertionSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ",");
}
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && current < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
}
腾讯云开发者
