二手交易网站建设的功能定位,沈阳市住房和城乡建设局网站首页,专业的盐城网站开发,寿光建设网站冒泡排序
冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法#xff0c;它通过重复地遍历要排序的数列#xff0c;比较相邻元素的大小并交换位置#xff0c;使得较大的元素逐渐向数列的末尾移动。
以下是Java实现的冒泡排序代码#xff1a;
public stat…冒泡排序
冒泡排序Bubble Sort是一种简单的排序算法它通过重复地遍历要排序的数列比较相邻元素的大小并交换位置使得较大的元素逐渐向数列的末尾移动。
以下是Java实现的冒泡排序代码
public static void bubbleSort(int[] arr) {for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}该算法的时间复杂度为O(n^2)其中n是待排序数列的长度。
选择排序
选择排序Selection Sort是一种简单直观的排序算法它通过每次从未排序的元素中选出最小或最大的元素将其放到已排序序列的末尾。
以下是Java实现的选择排序代码
public static void selectionSort(int[] arr) {for (int i 0; i arr.length - 1; i) {int minIndex i;for (int j i 1; j arr.length; j) {if (arr[j] arr[minIndex]) {minIndex j;}}if (minIndex ! i) {int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}
}该算法的时间复杂度为O(n^2)其中n是待排序数列的长度。
插入排序
插入排序Insertion Sort是一种简单直观的排序算法它通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
以下是Java实现的插入排序代码
public static void insertionSort(int[] arr) {for (int i 1; i arr.length; 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;}
}该算法的时间复杂度为O(n^2)其中n是待排序数列的长度。
快速排序
快速排序Quick Sort是一种高效的排序算法它通过分治的思想将待排序的数列分为两个部分一部分比另一部分的所有元素都小然后再对这两部分分别进行排序。
以下是Java实现的快速排序代码
public static void quickSort(int[] arr, int low, int high) {if (low high) {int pivot partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot 1, high);}
}private static int partition(int[] arr, int low, int high) {int pivot arr[low];while (low high) {while (low high arr[high] pivot) {high--;}arr[low] arr[high];while (low high arr[low] pivot) {low;}arr[high] arr[low];}arr[low] pivot;return low;
}该算法的平均时间复杂度为O(nlogn)其中n是待排序数列的长度。 归并排序
归并排序Merge Sort是一种高效的排序算法它通过分治的思想将待排序的数列分为两个部分分别对这两部分进行排序然后将它们合并成一个有序序列。
以下是Java实现的归并排序代码
public static void mergeSort(int[] arr, int low, int high) {if (low high) {int mid (low high) / 2;mergeSort(arr, low, mid);mergeSort(arr, mid 1, high);merge(arr, low, mid, high);}
}private static void merge(int[] arr, int low, int mid, int high) {int[] temp new int[high - low 1];int i low, j mid 1, k 0;while (i mid j high) {if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];}}while (i mid) {temp[k] arr[i];}while (j high) {temp[k] arr[j];}for (int p 0; p temp.length; p) {arr[low p] temp[p];}
}该算法的平均时间复杂度为O(nlogn)其中n是待排序数列的长度。 堆排序
堆排序Heap Sort是一种高效的排序算法它通过构建大顶堆或小顶堆来实现。
以下是Java实现的堆排序代码
public static void heapSort(int[] arr) {// 构建大顶堆for (int i arr.length / 2 - 1; i 0; i--) {adjustHeap(arr, i, arr.length);}// 交换堆顶元素和末尾元素并重新调整堆for (int j arr.length - 1; j 0; j--) {swap(arr, 0, j);adjustHeap(arr, 0, j);}
}private static void adjustHeap(int[] arr, int i, int length) {int temp arr[i];for (int k 2 * i 1; k length; k 2 * k 1) {if (k 1 length arr[k] arr[k 1]) {k;}if (arr[k] temp) {arr[i] arr[k];i k;} else {break;}}arr[i] temp;
}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}该算法的平均时间复杂度为O(nlogn)其中n是待排序数列的长度。 希尔排序
希尔排序Shell Sort是一种改进的插入排序算法它通过将待排序数列按照一定的间隔分组对每组进行插入排序然后逐渐缩小间隔直到间隔为1时整个数列已经基本有序此时再进行一次普通的插入排序即可。
以下是Java实现的希尔排序代码
public static void shellSort(int[] arr) {int gap arr.length / 2;while (gap 0) {for (int i gap; i arr.length; i) {int j i;int temp arr[j];while (j - gap 0 temp arr[j - gap]) {arr[j] arr[j - gap];j - gap;}arr[j] temp;}gap / 2;}
}该算法的平均时间复杂度为O(n^1.3)其中n是待排序数列的长度。
计数排序
计数排序Counting Sort是一种非比较的排序算法它通过统计每个元素出现的次数然后根据元素出现的次数来对元素进行排序。
以下是Java实现的计数排序代码
public static void countingSort(int[] arr) {int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {if (arr[i] max) {max arr[i];}}int[] count new int[max 1];for (int i 0; i arr.length; i) {count[arr[i]];}int index 0;for (int i 0; i count.length; i) {while (count[i] 0) {arr[index] i;count[i]--;}}
}该算法的时间复杂度为O(nk)其中n是待排序数列的长度k是待排序数列中的最大值。 桶排序
桶排序Bucket Sort是一种非比较的排序算法它通过将待排序数列分到有限数量的有序桶中然后对每个桶再进行排序最后将各个桶中的数据依次取出即可得到有序序列。
以下是Java实现的桶排序代码
public static void bucketSort(int[] arr) {int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for (int i 0; i arr.length; i) {if (arr[i] max) {max arr[i];}if (arr[i] min) {min arr[i];}}int bucketNum (max - min) / arr.length 1;ArrayListArrayListInteger bucketArr new ArrayList(bucketNum);for (int i 0; i bucketNum; i) {bucketArr.add(new ArrayList());}for (int i 0; i arr.length; i) {int num (arr[i] - min) / arr.length;bucketArr.get(num).add(arr[i]);}int index 0;for (int i 0; i bucketArr.size(); i) {Collections.sort(bucketArr.get(i));for (int j 0; j bucketArr.get(i).size(); j) {arr[index] bucketArr.get(i).get(j);}}
}该算法的时间复杂度为O(nk)其中n是待排序数列的长度k是待排序数列中的最大值。
基数排序
基数排序Radix Sort是一种非比较的排序算法它通过将待排序数列按照位数进行分组然后对每个位数进行计数排序最后将各个位数的数据依次取出即可得到有序序列。
以下是Java实现的基数排序代码
public static void radixSort(int[] arr) {int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {if (arr[i] max) {max arr[i];}}int maxDigit 0;while (max ! 0) {max / 10;maxDigit;}int mod 10, div 1;ArrayListArrayListInteger bucketList new ArrayList();for (int i 0; i 10; i) {bucketList.add(new ArrayList());}for (int i 0; i maxDigit; i, mod * 10, div * 10) {for (int j 0; j arr.length; j) {int num (arr[j] % mod) / div;bucketList.get(num).add(arr[j]);}int index 0;for (int j 0; j bucketList.size(); j) {for (int k 0; k bucketList.get(j).size(); k) {arr[index] bucketList.get(j).get(k);}bucketList.get(j).clear();}}
}该算法的时间复杂度为O(n*k)其中n是待排序数列的长度k是待排序数列中的最大值的位数。
