5種java排序算法匯總工具類
更新時間：2016年08月19日 15:33:03 投稿：lijiao
這篇文章主要總結了java的快速排序，希爾排序，插入排序，堆排序，歸并排序五種排序算法，感興趣的小伙伴們可以參考一下
工具類簡單明了地總結了java的快速排序，希爾排序，插入排序，堆排序，歸并排序五種排序算法，代碼中并沒有對這幾種排序算法的一個說明，關于思想部分希望在自行查閱相關說明，這里只是對這幾種算法進行一個概括，以供大家使用。
public class Sort {
public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a) {
insertionSort(a, 0, a.length - 1);
}
private static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a, int left, int right) {
int j; // 記錄第一個比tmp小的元素的后邊一位的位置
for (int p = left; p <= right; p++) {
AnyType tmp = a[p];
for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
public static <AnyType extends Comparable<? super AnyType>> void shellSort(AnyType[] arr) {
int j;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
AnyType tmp = arr[i];
for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
private static int leftChild(int i) {
return i * 2 + 1;
}
private static <AnyType extends Comparable<? super AnyType>> void perculateDown(AnyType[] arr, int i, int size) {
AnyType tmp = arr[i];
for (int child; (child = leftChild(i)) < size; i = child) {
if (child != size - 1 && arr[child].compareTo(arr[child + 1]) < 0) {
child++;
}
if (tmp.compareTo(arr[child]) < 0) {
arr[i] = arr[child];
} else {
break;
}
}
arr[i] = tmp;
}
public static <AnyType extends Comparable<? super AnyType>> void heapSort(AnyType[] arr) {
for (int i = arr.length / 2; i >= 0; i--) {
perculateDown(arr, i, arr.length);
}
for (int i = arr.length - 1; i >= 0; i--) {
swapReferences(arr, 0, i);
perculateDown(arr, 0, i);
}
}
private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] arr, int i, int j) {
AnyType tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
mergeSort(arr, 0, arr.length - 1, tmp);
}
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
if (start < end) {
int mid = (start + end) >> 1;
mergeSort(arr, start, mid, tmp);
mergeSort(arr, mid + 1, end, tmp);
merge(arr, start, mid, end, tmp);
}
}
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (arr[i].compareTo(arr[j]) < 0) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= end) {
tmp[k++] = arr[j++];
}
for (int m = start; m <= end; m++) {
arr[m] = tmp[m];
}
}
public static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr, int left, int right) {
if (left + LENGTH_DIFF <= right) {
AnyType pivot = medium(arr, left, right);
int i = left, j = right;
while (true) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
if (i < j) {
swapReferences(arr, i, j);
} else {
break;
}
}
swapReferences(arr, i, right);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
} else {
insertionSort(arr, left, right);
}
}
private static <AnyType extends Comparable<? super AnyType>> AnyType medium(AnyType[] arr, int left,
int right) {
int center = (left + right) / 2;
if (arr[center].compareTo(arr[left]) < 0) {
swapReferences(arr, center, left);
}
if (arr[left].compareTo(arr[right]) > 0) {
swapReferences(arr, left, right);
}
if (arr[center].compareTo(arr[right]) < 0) {
swapReferences(arr, center, right);
}
return arr[right];
}
private final static int LENGTH_DIFF = 20;
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關文章
本文主要介紹了java實現(xiàn)窗口刷新的示例代碼,通過重寫paintComponent()方法和調(diào)用repaint()方法,可以實現(xiàn)窗口的即時刷新,具有一定的參考價值,感興趣的可以了解一下2024-02-02
這篇文章主要介紹了java線程封閉之棧封閉和ThreadLocal,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
這篇文章主要介紹了SpringBoot快速遷移至Quarkus的方法步驟。文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
這篇文章主要介紹了JavaCV如何使用ffmpeg實現(xiàn)錄屏功能,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
這篇文章主要介紹了Spring核心容器IOC原理實例解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-02-02
Springboot啟動同時創(chuàng)建數(shù)據(jù)庫和表實現(xiàn)方法
這篇文章主要介紹了Springboot啟動同時創(chuàng)建數(shù)據(jù)庫和表，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2023-01-01
這篇文章主要介紹了Servlet第一個項目的發(fā)布，下面是用servlet實現(xiàn)的一個簡單的web項目，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了Java編程中的boolean對象的運用,是Java入門學習中的基礎知識,需要的朋友可以參考下2015-10-10
MyBatis批量插入/修改/刪除MySql數(shù)據(jù)
這篇文章主要給大家介紹了關于MyBatis批量插入/修改/刪除MySql數(shù)據(jù)的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要介紹了Spring Boot啟動過程完全解析(一),需要的朋友可以參考下2017-04-04