新手初學(xué)Java常見排序算法
更新時(shí)間：2021年07月07日 14:58:38 作者：隨性0528
排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列
1、冒泡排序
排序原理：相鄰兩個(gè)元素比較，如果前者比后者大，則交換兩個(gè)元素。每執(zhí)行一次，都會(huì)確定一個(gè)最大值，其位置就固定了，下一次就不需要再參與排序了。
時(shí)間復(fù)雜度：O(n^2)
穩(wěn)定性：穩(wěn)定
具體實(shí)現(xiàn)：
public class Bubble {
/**
* 對(duì)數(shù)組a中的元素進(jìn)行排序
*/
public static void sort(Comparable[] a){
//每冒泡一次，參與冒泡排序的元素個(gè)數(shù)就少一個(gè)
//需要排序的次數(shù)為數(shù)組個(gè)數(shù)減一
/*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;
}
/**
* 交換數(shù)組下標(biāo)為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測(cè)試
*/
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)化：可以加一個(gè)標(biāo)志位，當(dāng)冒泡一次也沒有執(zhí)行的時(shí)候，就說明已經(jīng)排好了，就不需要再冒泡了。
2、選擇排序
排序原理：從數(shù)組中找出最小值的下標(biāo)，然后將最小值交換到前邊。每執(zhí)行一次前邊就會(huì)有一個(gè)最小值位置固定，之后就不再需要參與查找最小值了。
時(shí)間復(fù)雜度：O(n^2)
穩(wěn)定性：不穩(wěn)定
具體實(shí)現(xiàn)：
public class Selelction {
/**
* 將數(shù)組排序
* @param a 待排序的數(shù)組
*/
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數(shù)組 不能直接用下標(biāo)比較大小
if (greater(a[minIndex],a[j])){
minIndex = j;
}
}
//交換
if (minIndex != i){
exch(a, minIndex, i);
}
}
}
/**
* 比較第一個(gè)參數(shù)是否大于第二個(gè)參數(shù)
* @param a
* @param b
* @return 第一個(gè)參數(shù)是否大于第二個(gè)參數(shù)
*/
private static boolean greater(Comparable a, Comparable b){
return a.compareTo(b) > 0;
}
/**
* 交換數(shù)組的兩個(gè)元素
* @param a 數(shù)組
* @param i 數(shù)組下標(biāo)
* @param j 數(shù)組下標(biāo)
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測(cè)試方法
* @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、簡(jiǎn)單插入排序
排序原理：將數(shù)組分成兩組，左邊一組是已排序的，右邊一組是未排序的，然后拿未排序的第一個(gè)與左邊的從后往前比較，如果比前邊的小就交換，直到前邊的值比它小或者等于它。
時(shí)間復(fù)雜度：O(n^2)
穩(wěn)定性：穩(wěn)定
具體實(shí)現(xiàn)：
public class Insertion {
/**
* 對(duì)數(shù)組a中的元素進(jìn)行排序
*/
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;
}
/**
* 交換數(shù)組下標(biāo)為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 測(cè)試
*/
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)化思路：將要插入的數(shù)先保存起來，然后交換的代碼就可以改成覆蓋，就相當(dāng)于后移，等找到合適位置再把之前保存的值放進(jìn)去。
4、希爾排序
排序原理：是插入排序的優(yōu)化版，插入排序在比較時(shí)只能一個(gè)一個(gè)比較，而希爾排序中加了一個(gè)增長(zhǎng)量，可以跨元素比較，相對(duì)減少了比較交換的次數(shù)。
時(shí)間復(fù)雜度：O(n^1.3)
穩(wěn)定性：不穩(wěn)定
具體實(shí)現(xiàn)：
public class Shell {
/**
* 將數(shù)組排序
* @param a 待排序的數(shù)組
* @return 排好序的數(shù)組
*/
public static void sort(Comparable[] a){
//1.確定增長(zhǎng)量h的值
int h=1;
while(h < a.length/2){
h = h*2+1;
}
//2.進(jìn)行排序
while(h>=1){
//找到待排序的第一個(gè)值
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;
}
/**
* 交換數(shù)組下標(biāo)為i和j的元素的位置
*/
private static void exch(Comparable[] a, int i, int j){
Comparable temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//測(cè)試數(shù)據(jù)
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、歸并排序
排序原理：使用了遞歸的思想，先把數(shù)組從中間遞歸分解，接著先排序左邊的子數(shù)組，然后再排序右邊的子數(shù)組，最后合并為一個(gè)數(shù)組。核心方法是merge方法。
時(shí)間復(fù)雜度：O(nlogn)
穩(wěn)定性：穩(wěn)定
具體實(shí)現(xiàn)：
public class Merge {
/**
* 輔助數(shù)組
*/
private static Comparable[] access;
/**
* 對(duì)數(shù)組a進(jìn)行排序
* @param a
*/
public static void sort(Comparable[] a){
//1.初始化輔助數(shù)組
access = new Comparable[a.length];
//2.定義兩個(gè)下標(biāo)值
int lo = 0;
int hi = a.length -1;
//3.調(diào)用分組排序函數(shù)
sort(a, lo, hi);
}
/**
* 對(duì)數(shù)組a中的lo到hi進(jìn)行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保護(hù)
if (hi <= lo){
return;
}
//1.得到mid
int mid = lo + (hi-lo)/2;
//2.對(duì)左數(shù)組分組排序
sort(a, lo, mid);
//3.對(duì)右數(shù)組分組排序
sort(a, mid+1, hi);
//4.將兩個(gè)數(shù)組合并
merge(a, lo, mid, hi);
}
/**
* 將兩個(gè)數(shù)組進(jìn)行排序合并
* @param a
* @param lo
* @param mid
* @param hi
*/
private static void merge(Comparable[] a, int lo, int mid, int hi){
//1.定義三個(gè)指針
int i=lo;
int p1=lo;
int p2=mid+1;
//2.分別遍歷兩個(gè)子數(shù)組，直到有一個(gè)數(shù)組遍歷完畢
while (p1 <= mid && p2 <= hi){
if (less(a[p1], a[p2])){
access[i++] = a[p1++];
}else{
access[i++] = a[p2++];
}
}
//3。將剩下的一個(gè)數(shù)組的剩余值放到輔助數(shù)組中
while(p1 <= mid){
access[i++] = a[p1++];
}
while(p2 <= hi){
access[i++] = a[p2++];
}
//4。將輔助數(shù)組中的值覆蓋到原數(shù)組中
for (int index=lo; index<=hi; index++){
a[index] = access[index];
}
}
/**
* 比較第一個(gè)下標(biāo)的值是不是小于第二個(gè)下標(biāo)的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) <= 0;
}
/**
* 測(cè)試
*/
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、快速排序
排序原理：把數(shù)組的第一個(gè)值設(shè)置為中間值，比中間值小的放到左邊，比中間值大的放到右邊。然后再對(duì)左邊的做相同的操作，最后是對(duì)右邊的做相同的操作。核心方法是partition方法，將小的數(shù)移到左邊，大的數(shù)移到右邊，最后返回中間值的下標(biāo)。
時(shí)間復(fù)雜度：O(nlogn)
穩(wěn)定性：不穩(wěn)定
具體實(shí)現(xiàn)：
public class Quick {
/**
* 對(duì)數(shù)組a進(jìn)行排序
* @param a
*/
public static void sort(Comparable[] a){
int lo = 0;
int hi = a.length-1;
sort(a, lo, hi);
}
/**
* 對(duì)數(shù)組a中的lo到hi進(jìn)行排序
* @param a
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, int lo, int hi){
//保護(hù)
if (hi <= lo){
return;
}
//獲取中間值
int mid = partition(a, lo, hi);
//對(duì)左子數(shù)組進(jìn)行排序
sort(a, lo, mid-1);
//對(duì)右子數(shù)組進(jìn)行排序
sort(a, mid+1, hi);
}
/**
* 將比子數(shù)組中第一個(gè)值小的數(shù)放到其左邊，大于的放到右邊，最后返回中間值的下標(biāo)
* @param a
* @param lo
* @param hi
* @return
*/
private static int partition(Comparable[] a, int lo, int hi){
//1.定義兩個(gè)指針
int p1= lo;
int p2 = hi+1;
while (true){
//2.先移動(dòng)右指針，找到第一個(gè)小于標(biāo)準(zhǔn)值的數(shù)
while(less(a[lo],a[--p2])){
if (p2 == lo){
break;
}
}
//3.移動(dòng)左指針，找到第一個(gè)大于標(biāo)準(zhǔn)值的數(shù)
while(less(a[++p1],a[lo])){
if (p1 == hi){
break;
}
}
if (p1 >= p2){
//5.退出循環(huán)
break;
}else {
//4.交換兩個(gè)值
exch(a, p1, p2);
}
}
//6.最后把子數(shù)組的第一個(gè)值和右指針?biāo)傅闹到粨Q，最后返回其下標(biāo)
exch(a, lo, p2);
return p2;
}
/**
* 比較第一個(gè)下標(biāo)的值是不是小于第二個(gè)下標(biāo)的值
* @param u
* @param v
* @return
*/
private static boolean less(Comparable u, Comparable v){
return u.compareTo(v) < 0;
}
/**
* 交換數(shù)組中兩個(gè)下標(biāo)的值
* @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;
}
/**
* 測(cè)試
*/
public static void main(String[] args) {
Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
sort(a);
System.out.println(Arrays.toString(a));
}
}
總結(jié)
本篇文章就到這里了，希望能給你您帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
Spring Boot REST國(guó)際化的實(shí)現(xiàn)代碼
本文我們將討論如何在現(xiàn)有的Spring Boot項(xiàng)目中添加國(guó)際化。只需幾個(gè)簡(jiǎn)單的步驟即可實(shí)現(xiàn)Spring Boot應(yīng)用的國(guó)際化，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
Java實(shí)現(xiàn)藍(lán)橋杯數(shù)獨(dú)游戲的示例代碼
這篇文章主要介紹了Java實(shí)現(xiàn)藍(lán)橋杯數(shù)獨(dú)游戲的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
SpringBoot進(jìn)行Web開發(fā)的實(shí)現(xiàn)
Spring?Boot讓我們可以快速構(gòu)建項(xiàng)目并運(yùn)行web應(yīng)用,大大簡(jiǎn)化了Spring的復(fù)雜配置,本文主要介紹了SpringBoot進(jìn)行Web開發(fā)的實(shí)現(xiàn),感興趣的可以了解一下2023-10-10
本篇文章主要介紹了Java本地緩存的實(shí)現(xiàn)代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05
映射器是MyBatis最復(fù)雜也最重要的組件,也是基于MyBatis應(yīng)用程序開發(fā)中,本文主要介紹了深入淺出MyBatis映射器,具有一定的參考價(jià)值,感興趣的可以了解一下2024-04-04
SpringBoot實(shí)現(xiàn)版本升級(jí)到2.7.18
這篇文章主要介紹了SpringBoot實(shí)現(xiàn)版本升級(jí)到2.7.18全過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-08-08
SpringBoot實(shí)現(xiàn)MapperScan添加動(dòng)態(tài)配置(占位符)
這篇文章主要介紹了SpringBoot實(shí)現(xiàn)MapperScan添加動(dòng)態(tài)配置(占位符)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。2022-01-01
這篇文章主要介紹了jboss配置方法,較為簡(jiǎn)明扼要的說明了jboss服務(wù)器所需要的JDK環(huán)境安裝設(shè)置以及jboss的安裝與下載,并分析了配置與使用中的常見問題,需要的朋友可以參考下2016-08-08
java+selenium實(shí)現(xiàn)自動(dòng)化打開頁面的方法
今天小編就為大家分享一篇java+selenium實(shí)現(xiàn)自動(dòng)化打開頁面的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-05-05
關(guān)于@Autowired注解和靜態(tài)方法及new的關(guān)系
這篇文章主要介紹了關(guān)于@Autowired注解和靜態(tài)方法及new的關(guān)系，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02