java数组插入排序
时间: 2023-11-15 16:58:15 浏览: 51
Java数组插入排序是一种简单的排序算法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。具体实现过程如下:
1. 从第一个元素开始,该元素可以认为已经被排序;
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤2~5。
下面是Java数组插入排序的代码实现:
```
public static void insertionSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
```
这段代码中,我们首先定义了一个长度为len的数组arr,然后使用for循环遍历数组,从第二个元素开始,将其插入到已经排好序的数组中。在循环中,我们使用temp变量来保存当前需要插入的元素,然后使用while循环将其插入到已经排好序的数组中。
相关问题
java数组的排序方法
Java数组的排序方法有多种,其中常用的包括冒泡排序、选择排序、快速排序、插入排序和归并排序等。下面简要介绍其中几种排序方法的原理和代码实现:
1. 冒泡排序:依次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换它们的位置,一轮下来可以将最大的元素放到最后。重复执行多轮,直到所有元素都有序。
2. 选择排序:从数组的第一个元素开始,依次与后面的元素进行比较,找到最小的元素并将其放到数组的第一个位置,然后从第二个元素开始,继续寻找最小的元素并放到第二个位置,以此类推,直到所有元素都有序。
3. 快速排序:选择一个基准元素,将数组分成两个部分,一部分比基准元素小,一部分比基准元素大,然后对这两部分分别进行递归排序,最终得到有序数组。
4. 插入排序:将数组分成有序区和无序区,每次从无序区取出一个元素,插入到有序区的合适位置,直到所有元素都有序。
5. 归并排序:将数组分成若干个子数组,对每个子数组进行排序,然后将排好序的子数组合并成一个有序数组。
下面是几种排序方法的代码实现,供参考:
冒泡排序:
```
public static int[] bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
```
选择排序:
```
public static int[] selectionSort(int[] arr) {
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;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
```
快速排序:
```
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
return arr;
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
```
插入排序:
```
public static int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
}
```
归并排序:
```
public static int[] mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
return arr;
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int m = 0; m < temp.length; m++) {
arr[left + m] = temp[m];
}
}
```
生成java数组插入算法
可以使用以下代码来生成一个随机的 Java 数组,并使用插入排序算法对其进行排序:
```
import java.util.Arrays;
import java.util.Random;
public class InsertionSort {
public static void main(String[] args) {
int[] arr = generateRandomArray(10);
System.out.println("Original array: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static int[] generateRandomArray(int size) {
int[] arr = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
return arr;
}
}
```
这个程序会生成一个长度为 10 的随机数组,并使用插入排序算法对其进行排序。你可以根据需要修改数组的长度和排序算法。