Java | 数组排序算法

**Java 中的数组排序算法**

在 Java 中，数组是最基本的数据结构之一。然而，在实际应用中，我们经常需要对这些数组进行排序，以便更好地组织和管理数据。在本文中，我们将讨论 Java 中常见的几种数组排序算法。

###1. 冒泡排序冒泡排序是一种简单的排序算法，它通过反复比较相邻元素并交换它们来实现。具体来说，冒泡排序会从头到尾地扫描一遍数组，然后再次扫描，从而不断地将最大的元素"浮"到顶部。

**代码示例**

javapublic class BubbleSort {
 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;
 }
 }
 }
 }

 public static void main(String[] args) {
 int[] arr = {5,2,8,3,1,6,4};
 bubbleSort(arr);
 System.out.println("排序后数组:");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }
}

**注释**

* `bubbleSort`方法首先获取数组的长度，然后开始从头到尾地扫描一遍数组。
* 在每次扫描中，比较相邻元素并交换它们，以便将最大的元素"浮"到顶部。
* 这个过程重复进行，直到整个数组被排序。

###2.选择排序选择排序是一种简单的排序算法，它通过在每一步中选择一个最小或最大元素来实现。具体来说，选择排序会从头到尾地扫描一遍数组，然后再次扫描，从而不断地将最小或最大元素"选出"。

**代码示例**

javapublic class SelectionSort {
 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;
 }
 }

 public static void main(String[] args) {
 int[] arr = {5,2,8,3,1,6,4};
 selectionSort(arr);
 System.out.println("排序后数组:");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }
}

**注释**

* `selectionSort`方法首先获取数组的长度，然后开始从头到尾地扫描一遍数组。
* 在每次扫描中，找到当前未排序区间中的最小元素，并将其交换到当前未排序区间的起始位置。
* 这个过程重复进行，直到整个数组被排序。

###3. 插入排序插入排序是一种简单的排序算法，它通过在每一步中将一个元素插入到已经排好序的部分中来实现。具体来说，插入排序会从头到尾地扫描一遍数组，然后再次扫描，从而不断地将元素插入到正确的位置。

**代码示例**

javapublic class InsertionSort {
 public static void insertionSort(int[] arr) {
 int n = arr.length;
 for (int i =1; i < n; 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 void main(String[] args) {
 int[] arr = {5,2,8,3,1,6,4};
 insertionSort(arr);
 System.out.println("排序后数组:");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }
}

**注释**

* `insertionSort`方法首先获取数组的长度，然后开始从头到尾地扫描一遍数组。
* 在每次扫描中，将当前元素与已经排好序的部分进行比较，并将其插入到正确的位置。
* 这个过程重复进行，直到整个数组被排序。

###4. 归并排序归并排序是一种高效的排序算法，它通过递归地将两个有序列表合并成一个更大的有序列表来实现。具体来说，归并排序会从头到尾地扫描一遍数组，然后再次扫描，从而不断地将元素合并到正确的位置。

**代码示例**

javapublic class MergeSort {
 public static void mergeSort(int[] arr) {
 int n = arr.length;
 if (n <=1) return;

 // 将数组分成两个部分，并分别进行排序 int mid = n /2;
 int[] left = new int[mid];
 int[] right = new int[n - mid];

 System.arraycopy(arr,0, left,0, mid);
 System.arraycopy(arr, mid, right,0, n - mid);

 mergeSort(left);
 mergeSort(right);

 // 将两个有序列表合并成一个更大的有序列表 merge(left, right, arr);
 }

 private static void merge(int[] left, int[] right, int[] arr) {
 int i =0;
 int j =0;
 int k =0;

 while (i < left.length && j < right.length) {
 if (left[i] <= right[j]) {
 arr[k++] = left[i++];
 } else {
 arr[k++] = right[j++];
 }
 }

 while (i < left.length) {
 arr[k++] = left[i++];
 }

 while (j < right.length) {
 arr[k++] = right[j++];
 }
 }

 public static void main(String[] args) {
 int[] arr = {5,2,8,3,1,6,4};
 mergeSort(arr);
 System.out.println("排序后数组:");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }
}

**注释**

* `mergeSort`方法首先获取数组的长度，然后开始从头到尾地扫描一遍数组。
* 在每次扫描中，将数组分成两个部分，并分别进行排序。
* 将两个有序列表合并成一个更大的有序列表。
* 这个过程重复进行，直到整个数组被排序。

###5. 快速排序快速排序是一种高效的排序算法，它通过选择一个基准元素，并将其他元素分成两部分，以便将小于或大于基准元素的元素分别放在两边。具体来说，快速排序会从头到尾地扫描一遍数组，然后再次扫描，从而不断地将元素排列到正确的位置。

**代码示例**

javapublic class QuickSort {
 public static void quickSort(int[] arr) {
 int n = arr.length;
 if (n <=1) return;

 //选择基准元素，并将其他元素分成两部分 int pivot = partition(arr,0, n -1);

 // 将小于或大于基准元素的元素分别放在两边 quickSort(Arrays.copyOfRange(arr,0, pivot));
 quickSort(Arrays.copyOfRange(arr, pivot +1, arr.length));

 System.out.println("排序后数组:");
 for (int i : arr) {
 System.out.print(i + " ");
 }
 }

 private static int partition(int[] arr, int low, int high) {
 int pivot = arr[high];
 int i = low -1;

 for (int j = low; j < high; j++) {
 if (arr[j] <= pivot) {
 i++;
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }