排序算法的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);
}
}
/**
* 維護從下標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];
}
}
/**
* 快排尋找基準點位置
*
* @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);
}
}
/**
* 維護從下標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)
相關文章
這篇文章主要為大家詳細介紹了java控制臺實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了一下Java的雙親委派模式,雙親委派指得是，JVM在加載類時，會委派給ExtClassLoader和BootstrapClassLoader進?加載，如果沒加載到才由??進?加載,需要的朋友可以參考下2023-04-04
Spring Boot實現(xiàn)圖片上傳/加水印一把梭操作實例代碼
這篇文章主要給大家介紹了關于Spring Boot實現(xiàn)圖片上傳/加水印一把梭操作的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-11-11
在本篇文章中小編給大家整理了關于java8傳函數(shù)方法和相關知識點，需要的朋友們學習下。2019-04-04
zookeeper實戰(zhàn)之實現(xiàn)分布式鎖的方法
Zookeeper實現(xiàn)分布式鎖比Redis簡單，Zookeeper有一個特性，多個線程在Zookeeper里創(chuàng)建同一個節(jié)點時，只有一個線程執(zhí)行成功，Zookeeper主要是利用臨時有序節(jié)點這一特性實現(xiàn)分布式鎖，感興趣的朋友跟隨小編一起學習吧2022-11-11
java實現(xiàn)把對象數(shù)組通過excel方式導出的功能
本文主要介紹了java實現(xiàn)把對象數(shù)組通過excel方式導出的功能的相關知識。具有很好的參考價值，下面跟著小編一起來看下吧2017-03-03
本文主要介紹java多線程-同步塊的知識，這里整理了相關的詳細資料及簡單示例代碼，有興趣的小伙伴可以參考下2016-09-09
JavaSE實戰(zhàn)之酒店訂房系統(tǒng)的實現(xiàn)
這篇文章主要為大家詳細介紹了如何利用JavaSE實現(xiàn)酒店訂房系統(tǒng)，文中的示例代碼講解詳細，對我們學習JavaSE開發(fā)有一定的幫助，需要的可以參考一下2022-07-07
Spring中的EventListenerMethodProcessor組件詳解
這篇文章主要介紹了Spring中的EventListenerMethodProcessor組件詳解,EventListenerMethodProcessor 是 Spring 事件機制中非常重要的一個組件,它管理了一組EventListenerFactory組件,用來將應用中每個使用@EventListener注解定義的事件監(jiān)聽,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了SpringBoot?使用log4j2的配置,springboot默認是用logback的日志框架的，所以要在pom中配置排除logback。這里需要注意的是，其實不止一處使用了logback，所以要在starter中統(tǒng)一排除，然后引入log4j2，需要的朋友可以參考下2022-09-09