新手初學Java常見排序算法
1、冒泡排序
排序原理：相鄰兩個元素比較，如果前者比後者大，則交換兩個元素。每執行一次，都會確定一個最大值，其位置就固定瞭，下一次就不需要再參與排序瞭。
時間復雜度：O(n^2)
穩定性：穩定
具體實現：
public class Bubble {
/**
* 對數組a中的元素進行排序
*/
public static void sort(Comparable[] a){
//每冒泡一次，參與冒泡排序的元素個數就少一個
//需要排序的次數為數組個數減一
/*for (int i=a.length-1; i>0; i--){
for (int j=0; j<i; j++){
if (greater(a[j],a[j+1])){
exch(a, j,j+1);
}
}
}*/
for (int i=0; i<a.length-1; i++){
for (int j=0; j<a.length-i-1; j++){
if (greater(a[j],a[j+1])){
exch(a, j,j+1);
}
}
}
}
/**
* 比較u元素是否大於v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交換數組下標為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測試
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6};
sort(a);
System.out.println(Arrays.toString(a));
}
}
優化：可以加一個標志位，當冒泡一次也沒有執行的時候，就說明已經排好瞭，就不需要再冒泡瞭。
2、選擇排序
排序原理：從數組中找出最小值的下標，然後將最小值交換到前邊。每執行一次前邊就會有一個最小值位置固定，之後就不再需要參與查找最小值瞭。
時間復雜度：O(n^2)
穩定性：不穩定
具體實現：
public class Selelction {
/**
* 將數組排序
* @param a 待排序的數組
*/
public static void sort(Comparable[] a){
for (int i=0; i<a.length-1; i++){
//找出最小的值
int minIndex = i;
//註意這裡不需要減一
for (int j=i+1; j<a.length; j++){
//Comparable數組 不能直接用下標比較大小
if (greater(a[minIndex],a[j])){
minIndex = j;
}
}
//交換
if (minIndex != i){
exch(a, minIndex, i);
}
}
}
/**
* 比較第一個參數是否大於第二個參數
* @param a
* @param b
* @return 第一個參數是否大於第二個參數
*/
private static boolean greater(Comparable a, Comparable b){
return a.compareTo(b) > 0;
}
/**
* 交換數組的兩個元素
* @param a 數組
* @param i 數組下標
* @param j 數組下標
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測試方法
* @param args
*/
public static void main(String[] args) {
Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7};
sort(array);
System.out.println(Arrays.toString(array));
}
3、簡單插入排序
排序原理：將數組分成兩組，左邊一組是已排序的，右邊一組是未排序的，然後拿未排序的第一個與左邊的從後往前比較，如果比前邊的小就交換，直到前邊的值比它小或者等於它。
時間復雜度：O(n^2)
穩定性：穩定
具體實現：
public class Insertion {
/**
* 對數組a中的元素進行排序
*/
public static void sort(Comparable[] a){
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--){
if (greater(a[j-1],a[j])){
exch(a, j-1, j);
}else {
break;
}
}
}
}
/**
* 比較u元素是否大於v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交換數組下標為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測試
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
優化思路：將要插入的數先保存起來，然後交換的代碼就可以改成覆蓋，就相當於後移，等找到合適位置再把之前保存的值放進去。
4、希爾排序
排序原理：是插入排序的優化版，插入排序在比較時隻能一個一個比較，而希爾排序中加瞭一個增長量，可以跨元素比較，相對減少瞭比較交換的次數。
時間復雜度：O(n^1.3)
穩定性：不穩定
具體實現：
public class Shell {
/**
* 將數組排序
* @param a 待排序的數組
* @return 排好序的數組
*/
public static void sort(Comparable[] a){
//1.確定增長量h的值
int h=1;
while(h < a.length/2){
h = h*2+1;
}
//2.進行排序
while(h>=1){
//找到待排序的第一個值
for (int i=h; i<a.length; i++){
for (int j=i; j>=h; j-=h){
if (greater(a[j-h],a[j])){
exch(a, j, j-h);
}else{
break;
}
}
}
//h減小
h/=2;
}
}
/**
* 比較u元素是否大於v元素
*/
private static boolean greater(Comparable u, Comparable v){
return u.compareTo(v) > 0;
}
/**
* 交換數組下標為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//測試數據
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7};
sort(a);
System.out.println(Arrays.toString(a));
}
}
5、歸並排序
排序原理：使用瞭遞歸的思想，先把數組從中間遞歸分解，接著先排序左邊的子數組，然後再排序右邊的子數組，最後合並為一個數組。核心方法是merge方法。
時間復雜度：O(nlogn)
穩定性：穩定
具體實現：
public class Merge {
/**
* 輔助數組
*/
private static Comparable[] access;
/**
* 對數組a進行排序
* @param a
*/
public static void sort(Comparable[] a){
//1.初始化輔助數組
access = new Comparable[a.length];
//2.定義兩個下標值
int lo = 0;
int hi = a.length -1;
//3.調用分組排序函數
sort(a, lo, hi);
}
/**
* 對數組a中的lo到hi進行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保護
if (hi <= lo){
return;
}
//1.得到mid
int mid = lo + (hi-lo)/2;
//2.對左數組分組排序
sort(a, lo, mid);
//3.對右數組分組排序
sort(a, mid+1, hi);
//4.將兩個數組合並
merge(a, lo, mid, hi);
}
/**
* 將兩個數組進行排序合並
* @param a
* @param lo
* @param mid
* @param hi
*/
private static void merge(Comparable[] a, int lo, int mid, int hi){
//1.定義三個指針
int i=lo;
int p1=lo;
int p2=mid+1;
//2.分別遍歷兩個子數組，直到有一個數組遍歷完畢
while (p1 <= mid && p2 <= hi){
if (less(a[p1], a[p2])){
access[i++] = a[p1++];
}else{
access[i++] = a[p2++];
}
}
//3。將剩下的一個數組的剩餘值放到輔助數組中
while(p1 <= mid){
access[i++] = a[p1++];
}
while(p2 <= hi){
access[i++] = a[p2++];
}
//4。將輔助數組中的值覆蓋到原數組中
for (int index=lo; index<=hi; index++){
a[index] = access[index];
}
}
/**
* 比較第一個下標的值是不是小於第二個下標的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) <= 0;
}
/**
* 測試
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
6、快速排序
排序原理：把數組的第一個值設置為中間值，比中間值小的放到左邊，比中間值大的放到右邊。然後再對左邊的做相同的操作，最後是對右邊的做相同的操作。核心方法是partition方法，將小的數移到左邊，大的數移到右邊，最後返回中間值的下標。
時間復雜度：O(nlogn)
穩定性：不穩定
具體實現：
public class Quick {
/**
* 對數組a進行排序
* @param a
*/
public static void sort(Comparable[] a){
int lo = 0;
int hi = a.length-1;
sort(a, lo, hi);
}
/**
* 對數組a中的lo到hi進行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保護
if (hi <= lo){
return;
}
//獲取中間值
int mid = partition(a, lo, hi);
//對左子數組進行排序
sort(a, lo, mid-1);
//對右子數組進行排序
sort(a, mid+1, hi);
}
/**
* 將比子數組中第一個值小的數放到其左邊，大於的放到右邊，最後返回中間值的下標
* @param a
* @param lo
* @param hi
* @return
*/
private static int partition(Comparable[] a, int lo, int hi){
//1.定義兩個指針
int p1= lo;
int p2 = hi+1;
while (true){
//2.先移動右指針，找到第一個小於標準值的數
while(less(a[lo],a[--p2])){
if (p2 == lo){
break;
}
}
//3.移動左指針，找到第一個大於標準值的數
while(less(a[++p1],a[lo])){
if (p1 == hi){
break;
}
}
if (p1 >= p2){
//5.退出循環
break;
}else {
//4.交換兩個值
exch(a, p1, p2);
}
}
//6.最後把子數組的第一個值和右指針所指的值交換，最後返回其下標
exch(a, lo, p2);
return p2;
}
/**
* 比較第一個下標的值是不是小於第二個下標的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) < 0;
}
/**
* 交換數組中兩個下標的值
* @param a
* @param i
* @param j
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測試
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
總結
本篇文章就到這裡瞭，希望能給你您帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！