新手初學(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)文章
Springboot如何配置Scheduler定時(shí)器
這篇文章主要介紹了Springboot如何配置Scheduler定時(shí)器問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2025-03-03
這篇文章主要為大家詳細(xì)介紹了java課程設(shè)計(jì)之坦克大戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
idea創(chuàng)建SpringBoot自動(dòng)創(chuàng)建Lombok無效果的問題解決方案
這篇文章主要介紹了idea創(chuàng)建SpringBoot自動(dòng)創(chuàng)建Lombok無效果的問題解決方案,感興趣的朋友跟隨小編一起看看吧2024-12-12
Java中的javaBean、vo、entity、domain和pojo
這篇文章主要介紹了Java中的javaBean、vo、entity、domain和pojo用法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
詳解SpringBoot如何優(yōu)雅的進(jìn)行測(cè)試打包部署
這篇文章主要為大家詳細(xì)介紹了SpringBoot如何優(yōu)雅的進(jìn)行測(cè)試打包部署,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-12-12
profiles.active多環(huán)境開發(fā)、測(cè)試、部署過程
這篇文章主要介紹了profiles.active多環(huán)境開發(fā)、測(cè)試、部署,主要講如何使用profiles.active這個(gè)變量，讓我們?cè)陂_發(fā)過程快速切換環(huán)境配置，以及如何使一個(gè)部署適配各種不同的環(huán)境，需要的朋友可以參考下2023-03-03
java實(shí)現(xiàn)flappy Bird小游戲
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)flappy Bird小游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要介紹了JAVA獲取Image的三種方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
在Java中,有些場(chǎng)景需要遍歷集合中的元素,然后根據(jù)條件進(jìn)行刪除元素的操作,本文結(jié)合示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2023-11-11
Lombok 的@StandardException注解解析
@StandardException 是一個(gè)實(shí)驗(yàn)性的注解，添加到 Project Lombok 的 v__1.18.22 版本中，在本教程中，我們將使用 Lombok 的 @StandardException 注解自動(dòng)生成異常類型類的構(gòu)造函數(shù),需要的朋友可以參考下2023-05-05