新手初學Java常見排序算法
更新時間：2021年07月07日 14:58:38 作者：隨性0528
排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列成一個關鍵字有序的序列
1、冒泡排序
排序原理：相鄰兩個元素比較，如果前者比后者大，則交換兩個元素。每執(zhí)行一次，都會確定一個最大值，其位置就固定了，下一次就不需要再參與排序了。
時間復雜度：O(n^2)
穩(wěn)定性：穩(wěn)定
具體實現：
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));
}
}
優(yōu)化：可以加一個標志位，當冒泡一次也沒有執(zhí)行的時候，就說明已經排好了，就不需要再冒泡了。
2、選擇排序
排序原理：從數組中找出最小值的下標，然后將最小值交換到前邊。每執(zhí)行一次前邊就會有一個最小值位置固定，之后就不再需要參與查找最小值了。
時間復雜度：O(n^2)
穩(wěn)定性：不穩(wěn)定
具體實現：
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)
穩(wěn)定性：穩(wěn)定
具體實現：
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));
}
}
優(yōu)化思路：將要插入的數先保存起來，然后交換的代碼就可以改成覆蓋，就相當于后移，等找到合適位置再把之前保存的值放進去。
4、希爾排序
排序原理：是插入排序的優(yōu)化版，插入排序在比較時只能一個一個比較，而希爾排序中加了一個增長量，可以跨元素比較，相對減少了比較交換的次數。
時間復雜度：O(n^1.3)
穩(wěn)定性：不穩(wěn)定
具體實現：
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)
穩(wěn)定性：穩(wěn)定
具體實現：
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)
穩(wěn)定性：不穩(wěn)定
具體實現：
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.退出循環(huán)
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));
}
}
總結
本篇文章就到這里了，希望能給你您帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
本文我們將討論如何在現有的Spring Boot項目中添加國際化。只需幾個簡單的步驟即可實現Spring Boot應用的國際化，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-10-10
這篇文章主要介紹了Java實現藍橋杯數獨游戲的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-02-02
Spring?Boot讓我們可以快速構建項目并運行web應用,大大簡化了Spring的復雜配置,本文主要介紹了SpringBoot進行Web開發(fā)的實現,感興趣的可以了解一下2023-10-10
本篇文章主要介紹了Java本地緩存的實現代碼，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
映射器是MyBatis最復雜也最重要的組件,也是基于MyBatis應用程序開發(fā)中,本文主要介紹了深入淺出MyBatis映射器,具有一定的參考價值,感興趣的可以了解一下2024-04-04
這篇文章主要介紹了SpringBoot實現版本升級到2.7.18全過程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
SpringBoot實現MapperScan添加動態(tài)配置(占位符)
這篇文章主要介紹了SpringBoot實現MapperScan添加動態(tài)配置(占位符)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教。2022-01-01
這篇文章主要介紹了jboss配置方法,較為簡明扼要的說明了jboss服務器所需要的JDK環(huán)境安裝設置以及jboss的安裝與下載,并分析了配置與使用中的常見問題,需要的朋友可以參考下2016-08-08
今天小編就為大家分享一篇java+selenium實現自動化打開頁面的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05
關于@Autowired注解和靜態(tài)方法及new的關系
這篇文章主要介紹了關于@Autowired注解和靜態(tài)方法及new的關系，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02