Java核心算法详解：插入、冒泡、选择与快速排序
5星
- 浏览量: 0
- 大小:None
- 文件类型：TXT
简介：
本书深入浅出地解析了四种经典的Java排序算法——插入排序、冒泡排序、选择排序及快速排序，帮助读者理解并灵活运用这些基础但重要的编程技巧。
### Java核心算法详解
#### 一、直接插入排序（Direct Insertion Sort）
**基本思想**：
直接插入排序是一种简单的排序方法，通过构建有序序列来完成。具体来说，在已排好序的部分找到当前元素的正确位置并插入。
**步骤说明**:
1. **初始化**: 认为数组的第一个元素已经处于正确的顺序。
2. **遍历**: 从第二个元素开始遍历整个数组。
3. **比较与移动**: 对于每个未排序的元素，将其与其前面已排序部分中的所有元素逐个进行比较，并在必要时将较大值向后移一位以腾出插入位置。
4. **定位并插入**: 当找到正确的位置后，把当前元素插入到该位置。
**代码实现**：
```java
public void insertSort(int[] array) {
int temp = 0;
for (int i = 1; i < array.length; i++) {
int j = i - 1;
temp = array[i];
for (; j >= 0 && temp < array[j]; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
}
```
#### 二、冒泡排序（Bubble Sort）
**基本思想**：
冒泡排序通过多次遍历数组，每次比较相邻的两个元素，并在必要时交换它们的位置。每一轮循环结束后，最大的未排定位置的数会被“浮”到已处理部分的末端。
**步骤说明**:
1. **初始遍历**: 从第一个元素开始进行两两对比。
2. **交换操作**: 如果前一个值大于后一个，则两者调换；否则保持不变。
3. **重复过程**: 每一轮结束时，最大的未排序数字会移动到数组的末端。继续此步骤直到整个序列有序。
**代码实现**：
```java
public void bubbleSort(int[] array) {
int temp;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
```
#### 三、简单选择排序（Selection Sort）
**基本思想**：
选择排序通过每次从剩余未排定的部分中找到最小值，并将其放到当前序列的最前端来完成整个数组的排序。
**步骤说明**:
1. **寻找最小元素**: 在每一轮迭代开始时，确定子数组中的最小元素。
2. **交换操作**: 将此最小值与该轮的第一位未排定位置进行调换。
3. **重复过程**: 从第二位开始重复上述两步直到整个序列有序。
**代码实现**：
```java
public void selectSort(int[] array) {
int position = 0;
for (int i = 0; i < array.length; i++) {
int j = i + 1;
position = i;
int temp = array[i];
for (; j < array.length; j++) {
if (array[j] < temp) {
temp = array[j];
position = j;
}
}
array[position] = array[i];
array[i] = temp;
}
}
```
#### 四、快速排序（Quick Sort）
**基本思想**：
快速排序采用分治策略，将数组分为较小和较大的两部分。通过递归地对这两部分进行相同的操作来完成整个序列的排序。
**步骤说明**:
1. **选择基准**: 从数组中选取一个元素作为基准。
2. **分区操作**: 将所有小于或等于基准值的元素放到左边，大于它的放到右边，并将这个基准值放置在中间位置。
3. **递归执行**: 对左右两个子序列分别进行快速排序。
**代码实现**：
```java
public void qsort(int[] array) {
if (array.length > 1) {
_qsort(array, 0, array.length - 1);
}
}
private void _qsort(int[] array, int low, int high) {
if (low < high) {
int middle = getMiddle(array, low, high);
_qsort(array, low, middle - 1);
_qsort(array, middle + 1, high);
}
}
private int getMiddle(int[] array, int low, int high) {
int tmp = array[low];
while (low < high) {
while (low < high && array[high] >= tmp)
high--;
array[low] = array[high];
while (low < high && array[low] <= tmp)
low++;
array[high] = array[low];
}
array[low] = tmp;
return low;
}
```
### 总结
全部评论 (0)
