介绍java中的常见排序算法

Java中的排序算法主要包括以下几种：

1. 冒泡排序（Bubble Sort）
2. 选择排序（Selection Sort）
3. 插入排序（Insertion Sort）
4. 快速排序（Quick Sort）
5. 归并排序（Merge Sort）
6. 堆排序（Heap Sort）

下面分别进行详细介绍。

1.冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它通过不断交换相邻两个元素的位置，使得每次遍历结束后最大的元素被放在了最后面。时间复杂度为$O(n^2)$。

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

2.选择排序（Selection Sort） 选择排序也是一种简单的排序算法，它每次找出未排序部分中最小的元素，然后将其放在已排序部分的末尾。时间复杂度为$O(n^2)$。

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

3.插入排序（Insertion Sort） 插入排序也是一种简单的排序算法，它将未排序部分的第一个元素插入到已排序的部分中的正确位置上。时间复杂度为$O(n^2)$。

public static void insertionSort(int[] arr){    int n = arr.length;    for(int i = 1; i < n; i++){        int cur = arr[i];        int j = i - 1;        while(j >= 0 && arr[j] > cur){            arr[j+1] = arr[j];            j--;        }        arr[j+1] = cur;    }}

4.快速排序（Quick Sort） 快速排序是一种高效的排序算法，它基于分治思想，将问题分解为多个子问题。它每次选择一个基准元素将待排序的数组分为两个子数组，小于基准的放在左边，大于等于基准的放在右边，然后对两个子数组进行递归调用。时间复杂度为$O(nlogn)$。

public static void quickSort(int[] arr, int left, int right){    if(left < right){        int pivotPos = partition(arr, left, right);        quickSort(arr, left, pivotPos - 1);        quickSort(arr, pivotPos + 1, right);    }}private static int partition(int[] arr, int left, int right){    int pivot = arr[left];    int i = left;    int j = right;    while(i < j){        while(i < j && arr[j] >= pivot){            j--;        }        arr[i] = arr[j];        while(i < j && arr[i] < pivot){            i++;        }        arr[j] = arr[i];    }    arr[i] = pivot;    return i;}

5.归并排序（Merge Sort） 归并排序也是一种高效的排序算法，它基于分治思想，将待排序的数组分成两个子数组，然后对子数组进行排序，最后将两个子数组进行归并。时间复杂度为$O(nlogn)$。

public static void 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);    }}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 x = 0; x < temp.length; x++){        arr[left + x] = temp[x];    }}

6.堆排序（Heap Sort） 堆排序是一种高效的排序算法，它基于堆结构，将待排序的数组构建成大根堆或小根堆，然后将堆顶元素与末尾元素进行交换，并重新构建堆，重复以上步骤直到整个数组有序。时间复杂度为$O(nlogn)$。

public static void heapSort(int[] arr){    int n = arr.length;    for(int i = n/2-1; i >= 0; i--){        adjustHeap(arr, i, n);    }    for(int i = n-1; i > 0; i--){        int temp = arr[0];        arr[0] = arr[i];        arr[i] = temp;        adjustHeap(arr, 0, i);    }}private static void adjustHeap(int[] arr, int i, int n){    int temp = arr[i];    for(int j = 2*i+1; j < n; j = 2*j+1){       if(j + 1 < n && arr[j] < arr[j+1]){           j++;       }       if(arr[j] > temp){           arr[i] = arr[j];           i = j;       }else{           break;       }    }    arr[i] = temp;}

来源地址：https://blog.csdn.net/LJH_java10086/article/details/133976567