Java中的排序算法主要包括以下几种:文章来源:https://www.toymoban.com/news/detail-716371.html
- 冒泡排序(Bubble Sort)
- 选择排序(Selection Sort)
- 插入排序(Insertion Sort)
- 快速排序(Quick Sort)
- 归并排序(Merge Sort)
- 堆排序(Heap Sort)
下面分别进行详细介绍。文章来源地址https://www.toymoban.com/news/detail-716371.html
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;
}
到了这里,关于介绍java中的常见排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!