当前位置：首页 > news >正文

选择排序，插入排序，快速排序的java简单实现

news 2025/6/17 5:31:22

代码功能

以下Java代码包含了三个排序算法的实现：
选择排序（Selection Sort）：通过不断选择剩余元素中的最小值来排序数组。
插入排序（Insertion Sort）：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
快速排序（Quick Sort）：使用分治法，通过一个基准值将数据分为两部分，对每部分递归排序。
代码还包含了一个生成30个随机整数的数组的函数，并使用上述三种排序算法对数组进行排序，同时计算并输出每种排序方法的执行时间。
在这里插入图片描述

代码

import java.util.Arrays;
import java.util.Random;public class SortTest {public static void main(String[] args) {int[] array = generateRandomArray(30);System.out.println("Original array: " + Arrays.toString(array));long startTime, endTime;// 选择排序startTime = System.nanoTime();int[] sortedArraySelection = selectionSort(array.clone());endTime = System.nanoTime();System.out.println("Sorted by selection sort: " + Arrays.toString(sortedArraySelection));System.out.println("Time taken by selection sort: " + (endTime - startTime) + " ns");// 插入排序startTime = System.nanoTime();int[] sortedArrayInsertion = insertionSort(array.clone());endTime = System.nanoTime();System.out.println("Sorted by insertion sort: " + Arrays.toString(sortedArrayInsertion));System.out.println("Time taken by insertion sort: " + (endTime - startTime) + " ns");// 快速排序startTime = System.nanoTime();int[] sortedArrayQuick = quickSort(array.clone(), 0, array.length - 1);endTime = System.nanoTime();System.out.println("Sorted by quick sort: " + Arrays.toString(sortedArrayQuick));System.out.println("Time taken by quick sort: " + (endTime - startTime) + " ns");}public static int[] generateRandomArray(int size) {Random random = new Random();int[] array = new int[size];for (int i = 0; i < size; i++) {array[i] = random.nextInt(1000);}return array;}public static int[] selectionSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}int temp = array[i];array[i] = array[minIndex];array[minIndex] = temp;}return array;}public static int[] insertionSort(int[] array) {for (int i = 1; i < array.length; i++) {int key = array[i];int j = i - 1;while (j >= 0 && array[j] > key) {array[j + 1] = array[j];j--;}array[j + 1] = key;}return array;}public static int[] quickSort(int[] array, int low, int high) {if (low < high) {int pivotIndex = partition(array, low, high);quickSort(array, low, pivotIndex - 1);quickSort(array, pivotIndex + 1, high);}return array;}public static int partition(int[] array, int low, int high) {int pivot = array[high];int i = (low - 1);for (int j = low; j < high; j++) {if (array[j] < pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int temp = array[i + 1];array[i + 1] = array[high];array[high] = temp;return i + 1;}
}