八大排序算法

### 八大排序算法知识点详解 #### 一、直接插入排序 **基本思想：** 直接插入排序的基本思想是在已排序序列中找到待插入项的合适位置，并将其插入。具体步骤如下： 1. 假设数组中的前 \( n-1 \) 个元素已排序。 2. 将第 \( n \) 个元素与前面已排序的元素逐个比较，如果该元素小于已排序元素，则将已排序元素向后移动一位。 3. 重复以上步骤，直至找到第 \( n \) 个元素的正确位置，并将其插入。 4. 重复整个过程，直至所有元素都排序完毕。 **实例分析：** 假设初始数组为 \([49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51]\)。排序过程如下： - 将 \( 38 \) 插入到已排序的 \([49]\) 中。 - 然后，将 \( 65 \) 插入到已排序的 \([38, 49]\) 中。 - 以此类推，直至数组完全排序。 **Java实现代码示例：** ```java public class insertSort { public insertSort() { int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51}; for (int i = 1; i < a.length; i++) { int j = i - 1; int temp = a[i]; for (; j >= 0 && temp < a[j]; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } // 输出排序后的数组 for (int i : a) { System.out.print(i + " "); } } } ``` #### 二、希尔排序（最小增量排序） **基本思想：** 希尔排序是直接插入排序的一种改进版，其主要思想是： 1. 将数组分成若干个子序列，每个子序列包含相隔一定增量 \( d \) 的元素。 2. 对每个子序列执行直接插入排序。 3. 逐步减小增量 \( d \)，重复上述步骤，直至 \( d = 1 \) 时，整个数组变为一个子序列，此时再执行一次直接插入排序即可。 **实例分析：** 假设初始数组为 \([1, 54, 6, 3, 78, 34, 12, 45, 56, 100]\)。首先按照 \( d = 5 \) 分组，得到两个子序列：\([1, 6, 78, 12]\) 和 \([54, 3, 34, 45, 56, 100]\)。分别对这两个子序列进行直接插入排序。随后逐步减少增量直至 \( d = 1 \)。 **Java实现代码示例：** ```java public class shellSort { public shellSort() { int[] a = {1, 54, 6, 3, 78, 34, 12, 45, 56, 100}; double d1 = a.length; while (true) { d1 = Math.ceil(d1 / 2); int d = (int) d1; for (int x = 0; x < d; x++) { for (int i = x + d; i < a.length; i += d) { int j = i - d; int temp = a[i]; for (; j >= 0 && temp < a[j]; j -= d) { a[j + d] = a[j]; } a[j + d] = temp; } } if (d == 1) break; } // 输出排序后的数组 for (int i : a) { System.out.print(i + " "); } } } ``` #### 三、简单选择排序 **基本思想：** 简单选择排序是一种简单直观的排序算法，其基本思想是： 1. 从未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。 2. 从未排序序列中找到最小（或最大）元素，然后放到已排序序列的末尾。 3. 重复步骤2，直到所有元素均排序完毕。 **实例分析：** 假设初始数组为 \([1, 54, 6, 3, 78, 34, 12, 45]\)。排序过程如下： - 第一轮选择排序后，数组变为 \([1, 54, 6, 3, 78, 34, 12, 45]\)。 - 第二轮选择排序后，数组变为 \([1, 3, 6, 54, 78, 34, 12, 45]\)。 - 以此类推，直至数组完全排序。 **Java实现代码示例：** ```java public class selectSort { public selectSort() { int[] a = {1, 54, 6, 3, 78, 34, 12, 45}; for (int i = 0; i < a.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[minIndex]) { minIndex = j; } } // 交换元素 int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } // 输出排序后的数组 for (int i : a) { System.out.print(i + " "); } } } ``` 以上介绍了三种排序算法——直接插入排序、希尔排序和简单选择排序的基本思想、实例及Java实现代码。接下来，我们将继续探讨剩余五种排序算法：堆排序、冒泡排序等。这些排序算法各有特点，在实际应用中可以根据数据的具体情况选择合适的算法来提高效率。