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 + " ");
 }
 }
}

**注释**

* 冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
* 这种算法适用于小规模数据的排序。

###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 + " ");
 }
 }
}

**注释**

*选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
* 这种算法适用于小规模数据的排序。

###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 + " ");
 }
 }
}

**注释**

* 插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
* 这种算法适用于小规模数据的排序。

###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++];
 }
 }

 // 将剩余元素复制到结果数组中 System.arraycopy(left, i, arr, k, left.length - i);
 System.arraycopy(right, j, arr, k + (left.length - i), right.length - 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 + " ");
 }
 }
}

**注释**

* 归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)。
* 这种算法适用于大规模数据的排序。

###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, n));
 }

 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;
 }
 }

 // 将基准元素放到正确的位置上 int temp2 = arr[i +1];
 arr[i +1] = arr[high];
 arr[high] = temp2;

 return i +1;
 }

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

**注释**

* 快速排序的时间复杂度为O(n log n)，空间复杂度为O(log n)。
* 这种算法适用于大规模数据的排序。

以上就是本文对JAVA经典排序算法的介绍。每种算法都有其特点和应用场景，选择合适的算法可以提高程序的效率和性能。