排序算法的Java實現(xiàn)全攻略
更新時間：2015年08月06日 16:04:49 作者：zinss26914
這篇文章主要介紹了排序算法的Java實現(xiàn),包括Collections.sort()的使用以及各種經(jīng)典算法的Java代碼實現(xiàn)方法總結(jié),超級推薦!需要的朋友可以參考下
Collections.sort()
Java的排序可以用Collections.sort() 排序函數(shù)實現(xiàn)。
用Collections.sort方法對list排序有兩種方法：
第一種是list中的對象實現(xiàn)Comparable接口，如下：
/**
* 根據(jù)order對User排序
*/
public class User implements Comparable<User>{
private String name;
private Integer order;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
public int compareTo(User arg0) {
return this.getOrder().compareTo(arg0.getOrder());
}
}
測試一下：
public class Test{
public static void main(String[] args) {
User user1 = new User();
user1.setName("a");
user1.setOrder(1);
User user2 = new User();
user2.setName("b");
user2.setOrder(2);
List<User> list = new ArrayList<User>();
//此處add user2再add user1
list.add(user2);
list.add(user1);
Collections.sort(list);
for(User u : list){
System.out.println(u.getName());
}
}
}
輸出結(jié)果如下
a b
第二種方法是根據(jù)Collections.sort重載方法來實現(xiàn)，例如：
/**
* 根據(jù)order對User排序
*/
public class User { //此處無需實現(xiàn)Comparable接口
private String name;
private Integer order;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getOrder() {
return order;
}
public void setOrder(Integer order) {
this.order = order;
}
}
主類中這樣寫即可：
public class Test{
public static void main(String[] args) {
User user1 = new User();
user1.setName("a");
user1.setOrder(1);
User user2 = new User();
user2.setName("b");
user2.setOrder(2);
List<User> list = new ArrayList<User>();
list.add(user2);
list.add(user1);
Collections.sort(list,new Comparator<User>(){
public int compare(User arg0, User arg1) {
return arg0.getOrder().compareTo(arg1.getOrder());
}
});
for(User u : list){
System.out.println(u.getName());
}
}
}
輸出結(jié)果如下
a b
前者代碼結(jié)構(gòu)簡單，但是只能根據(jù)固定的屬性排序，后者靈活，可以臨時指定排序項，但是代碼不夠簡潔
擇優(yōu)用之。
常用排序算法
下面來看幾種經(jīng)典排序算法的Java代碼實踐：
冒泡排序
public static void bubbleSort(int A[], int n) {
int i, j;
for (i = 0; i < n - 1; i ++) {
for (j = 0; j < n - i - 1; j ++) {
if (A[j] > A[j + 1]) {
A[j] = A[j] ^ A[j + 1];
A[j + 1] = A[j] ^ A[j + 1];
A[j] = A[j] ^ A[j + 1];
}
}
}
}
直接插入排序
public static void insertSort(int A[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = A[i];
for (j = i - 1; j >= 0; j--) {
if (A[j] > tmp) {
A[j + 1] = A[j];
} else {
break;
}
}
A[j + 1] = tmp;
}
}
直接選擇排序
public static void selectSort(int A[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (A[j] < A[loc]) {
loc = j;
}
}
if (loc != i) {
A[i] = A[i] ^ A[loc];
A[loc] = A[i] ^ A[loc];
A[i] = A[i] ^ A[loc];
}
}
}
堆排序
/**
* 堆排序（從小到大）
*
* @param A
* @param n
*/
public static void heapSort(int A[], int n) {
int tmp;
// 構(gòu)建大根堆
buildMaxHeap(A, n);
for (int j = n - 1; j >= 1; j--) {
tmp = A[0];
A[0] = A[j];
A[j] = tmp;
maxheapIfy(A, 0, j);
}
}
/**
* 構(gòu)建大根堆
*
* @param A
* @param n
*/
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, n);
}
}
/**
* 維護從下標(biāo)i開始的最大堆
*
* @param A
* @param i
* @param n
*/
private static void maxheapIfy(int A[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && A[left] > A[i]) {
i = left;
}
if (right < n && A[right] > A[i]) {
i = right;
}
if (loc != i) {
A[i] = A[loc] ^ A[i];
A[loc] = A[loc] ^ A[i];
A[i] = A[loc] ^ A[i];
} else {
break;
}
}
}
快速排序
public static void quickSort(int A[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotPartition(A, bt, ed);
quickSort(A, bt, pivot - 1);
quickSort(A, pivot + 1, ed);
}
}
private static void swapVar(int A[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
A[bt] = A[bt] ^ A[mid];
A[mid] = A[bt] ^ A[mid];
A[bt] = A[bt] ^ A[mid];
}
}
private static int pivotPartition(int A[], int bt, int ed) {
// 取中間值作為stand，防止數(shù)組有序出現(xiàn)O(n^2)情況
swapVar(A, bt, ed);
int stand = A[bt];
while (bt < ed) {
while (bt < ed && A[ed] >= stand) {
ed--;
}
if (bt < ed) {
A[bt++] = A[ed];
}
while (bt < ed && A[bt] <= stand) {
bt++;
}
if (bt < ed) {
A[ed--] = A[bt];
}
}
A[bt] = stand;
return bt;
}
歸并排序
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
測試程序
來將以上算法歸納總結(jié)一下：
import java.util.Scanner;
public class JavaSort {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int A[], n;
while (cin.hasNext()) {
n = cin.nextInt();
A = new int[n];
for (int i = 0; i < n; i++) {
A[i] = cin.nextInt();
}
// bubbleSort(A, n);
// insertSort(A, n);
// selectSort(A, n);
// heapSort(A, n);
// quickSort(A, 0, n - 1);
mergeSort(A, 0, n - 1);
printArr(A);
}
}
/**
* 歸并排序
*
* @param A
* @param bt
* @param ed
*/
public static void mergeSort(int A[], int bt, int ed) {
if (bt < ed) {
int mid = bt + (ed - bt) / 2;
mergeSort(A, bt, mid);
mergeSort(A, mid + 1, ed);
mergeArray(A, bt, mid, ed);
}
}
/**
* 合并數(shù)組
*
* @param A
* @param bt
* @param mid
* @param ed
*/
private static void mergeArray(int A[], int bt, int mid, int ed) {
int i, j, k, len = ed - bt + 1;
int tmp[] = new int[len];
for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
if (A[i] <= A[j]) {
tmp[k] = A[i++];
} else {
tmp[k] = A[j++];
}
}
while (i <= mid) {
tmp[k++] = A[i++];
}
while (j <= ed) {
tmp[k++] = A[j++];
}
for (i = 0; i < k; i++) {
A[bt + i] = tmp[i];
}
}
/**
* 快速排序
*
* @param A
* @param bt
* @param ed
*/
public static void quickSort(int A[], int bt, int ed) {
if (bt < ed) {
int pivot = pivotPartition(A, bt, ed);
quickSort(A, bt, pivot - 1);
quickSort(A, pivot + 1, ed);
}
}
private static void swapVar(int A[], int bt, int ed) {
int mid = bt + (ed - bt) / 2;
if (mid != bt) {
A[bt] = A[bt] ^ A[mid];
A[mid] = A[bt] ^ A[mid];
A[bt] = A[bt] ^ A[mid];
}
}
/**
* 快排尋找基準(zhǔn)點位置
*
* @param A
* @param bt
* @param ed
* @return
*/
private static int pivotPartition(int A[], int bt, int ed) {
// 取中間值作為stand，防止數(shù)組有序出現(xiàn)O(n^2)情況
swapVar(A, bt, ed);
int stand = A[bt];
while (bt < ed) {
while (bt < ed && A[ed] >= stand) {
ed--;
}
if (bt < ed) {
A[bt++] = A[ed];
}
while (bt < ed && A[bt] <= stand) {
bt++;
}
if (bt < ed) {
A[ed--] = A[bt];
}
}
A[bt] = stand;
return bt;
}
/**
* 堆排序（從小到大）
*
* @param A
* @param n
*/
public static void heapSort(int A[], int n) {
int tmp;
// 構(gòu)建大根堆
buildMaxHeap(A, n);
for (int j = n - 1; j >= 1; j--) {
tmp = A[0];
A[0] = A[j];
A[j] = tmp;
maxheapIfy(A, 0, j);
}
}
/**
* 構(gòu)建大根堆
*
* @param A
* @param n
*/
private static void buildMaxHeap(int A[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
maxheapIfy(A, i, n);
}
}
/**
* 維護從下標(biāo)i開始的最大堆
*
* @param A
* @param i
* @param n
*/
private static void maxheapIfy(int A[], int i, int n) {
int left, right, loc;
while (i < n) {
left = 2 * i + 1;
right = 2 * i + 2;
loc = i;
if (left < n && A[left] > A[i]) {
i = left;
}
if (right < n && A[right] > A[i]) {
i = right;
}
if (loc != i) {
A[i] = A[loc] ^ A[i];
A[loc] = A[loc] ^ A[i];
A[i] = A[loc] ^ A[i];
} else {
break;
}
}
}
/**
* 直接選擇排序
*
* @param A
* @param n
*/
public static void selectSort(int A[], int n) {
int i, j, loc;
for (i = 0; i < n; i++) {
loc = i;
for (j = i + 1; j < n; j++) {
if (A[j] < A[loc]) {
loc = j;
}
}
if (loc != i) {
A[i] = A[i] ^ A[loc];
A[loc] = A[i] ^ A[loc];
A[i] = A[i] ^ A[loc];
}
}
}
/**
* 直接插入排序
*
* @param A
* @param n
*/
public static void insertSort(int A[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = A[i];
for (j = i - 1; j >= 0; j--) {
if (A[j] > tmp) {
A[j + 1] = A[j];
} else {
break;
}
}
A[j + 1] = tmp;
}
}
/**
* 冒泡排序
*
* @param A
* @param n
*/
public static void bubbleSort(int A[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (A[j] > A[j + 1]) {
A[j] = A[j] ^ A[j + 1];
A[j + 1] = A[j] ^ A[j + 1];
A[j] = A[j] ^ A[j + 1];
}
}
}
}
/**
* 打印數(shù)組
*
* @param A
*/
public static void printArr(int A[]) {
for (int i = 0; i < A.length; i++) {
if (i == A.length - 1) {
System.out.printf("%d\n", A[i]);
} else {
System.out.printf("%d ", A[i]);
}
}
}
}
您可能感興趣的文章:
- Java實現(xiàn)直接插入排序和折半插入排序算法示例
- 簡單講解奇偶排序算法及在Java數(shù)組中的實現(xiàn)
- 詳解快速排序算法中的區(qū)間劃分法及Java實現(xiàn)示例
- Java對數(shù)組實現(xiàn)選擇排序算法的實例詳解
- Java實現(xiàn)冒泡排序與雙向冒泡排序算法的代碼示例
- java實現(xiàn)歸并排序算法
- Java各種排序算法匯總(冒泡,選擇,歸并,希爾及堆排序等)
- java 合并排序算法、冒泡排序算法、選擇排序算法、插入排序算法、快速排序算法的描述
- 用java實現(xiàn)冒泡排序算法
- 深入探究TimSort對歸并排序算法的優(yōu)化及Java實現(xiàn)
相關(guān)文章
這篇文章主要介紹了淺談Tomcat三種運行模式，小編冒昧將兩篇文章略微整合了一下，有不足的地方，歡迎指出。需要的朋友可以參考。2017-10-10
Spring?Boot?RestController接口輸出到終端的操作代碼
這篇文章主要介紹了Spring?Boot?RestController接口如何輸出到終端,使用?HttpServletResponse?類，可以在使用curl執(zhí)行?Spring?Boot?REST接口的同時，在控制臺輸出一些信息，給運維人員知道當(dāng)前命令執(zhí)行的狀態(tài)，感興趣的朋友跟隨小編一起看看吧2023-09-09
java對象和json的來回轉(zhuǎn)換知識點總結(jié)
在本篇文章里小編給大家分享了一篇關(guān)于java對象和json的來回轉(zhuǎn)換知識點總結(jié)內(nèi)容，有興趣的朋友們可以學(xué)習(xí)下。2021-01-01
ElasticSearch啟動成功卻無法在瀏覽器訪問問題解決辦法
因工作的需要,要使用elasticsearch,安裝完了,啟動也成功了之后發(fā)現(xiàn)了問題,這篇文章主要給大家介紹了關(guān)于ElasticSearch啟動成功卻無法在瀏覽器訪問問題的解決辦法,需要的朋友可以參考下2024-10-10
這篇文章主要介紹了HashSet和TreeSet使用方法的區(qū)別解析，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
使用java + selenium + OpenCV破解網(wǎng)易易盾滑動驗證碼的示例
這篇文章主要介紹了使用java + selenium + OpenCV破解網(wǎng)易易盾滑動驗證碼,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
postman中POST請求時參數(shù)包含參數(shù)list設(shè)置方式
這篇文章主要介紹了postman中POST請求時參數(shù)包含參數(shù)list設(shè)置方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05
SpringMVC + jquery.uploadify實現(xiàn)上傳文件功能
文件上傳是很多項目都會使用到的功能，SpringMVC當(dāng)然也提供了這個功能。不過小編不建議在項目中通過form表單來提交文件上傳，這樣做的局限性很大。下面這篇文章主要介紹了利用SpringMVC + jquery.uploadify實現(xiàn)上傳文件功能的相關(guān)資料，需要的朋友可以參考下。2017-06-06
packages思維及使用Java添加Android平臺特定實現(xiàn)
這篇文章主要為大家介紹了packages思維及使用Java添加Android平臺特定實現(xiàn)在Flutter框架里的體現(xiàn)和運用詳解，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
這篇文章主要為大家詳細介紹了完整的B樹算法Java實現(xiàn)代碼,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-09-09