java各種排序演算法及實現
先來看看8種排序之間的關係：
下圖是各種排序的比較：
1， 直接插入排序
（1）基本想法：在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排
好順序的，現在要把第n個數插到前面的有序數中，使得這n個數
也是排好順序的。如此反覆循環，直到全部排好順序。
在插入演算法中，如果有一個最小的數在數組的最後面，用插入演算法就會從最後一個
位置移動到第一個。
（2）實例
package cglib;
public class StringNumber {
public static void insertSort(int[] a) {
if (a == null || a.length < 2) {
return;
}
int length=a.length; //数组长度
int j; //当前值的位置
int i; //指向j前的位置
int key; //当前要进行插入排序的值
//从数组的第二个位置开始遍历值
for(j=1;j<length;j++){
key=a[j];
i=j-1;
System.out.println(" 将i="+i);
//a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移
while(i>=0 && a[i]>key){
System.out.println("进 i="+i);
a[i+1]=a[i]; //将a[i]值后移
i--; //i前移
System.out.println(" i="+i);
}//跳出循环(找到要插入的中间位置或已遍历到0下标)
System.out.println(" 退出while");
System.out.println(" i="+i);
a[i+1]=key; //将当前值插入
}
}
public static void main(String[] args) {
int[] array = { 3, -1, 0, -8, 2, 1 };
ArrayUtils.printArray(array);
insertSort(array);
ArrayUtils.printArray(array);
}
}
class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
} 輸出：
{3, -1, 0, -8, 2, 1}
将i=0
进 i=0
i=-1
退出while
i=-1
将i=1
进 i=1
i=0
退出while
i=0
将i=2
进 i=2
i=1
进 i=1
i=0
进 i=0
i=-1
退出while
i=-1
将i=3
进 i=3
i=2
退出while
i=2
将i=4
进 i=4
i=3
进 i=3
i=2
退出while
i=2
{-8, -1, 0, 1, 2, 3}希爾希爾（希爾增量數位（最小增量元素）將整個時間排列成真數個以下變化希爾（8個增量）。序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本上有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。
演算法最開始以一定的步長進行排序,然後會繼續以一定步長進行排序，最終演算法以步長為1進行排序。當步長為1時，演算法變成插入排序，這就保證了資料一 定會被排序。 Donald Shell 最初建議步長選擇為frac{n}{2}並且對步長取半直到步長達到 1。雖然這樣取可以比mathcal{O}(n^2)類別的演算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的空間。
希爾排序範例:n=10的一個陣列 58 27 32 93 65 87 58 46 9 65，步長為n/2。
第一次排序步長為10/2 = 5
58 27 32 93 65 87 58 46 9 65
1A 1B2A 2B
3A 3B 4A 4B
5A 5B
首先將待排序元素序列分組，以5為步長，(1A,1B), (2A,2B),(3A,3B)等為分組標記，大寫字母表示是該組的第幾個元素,數字相同的表示在同一組，這樣就分成5組，即(58,87), (27,58),(32,46),(93,9),(65,65)，然後分別對各分組進行直接插入排序，排序後5組為(58,87),(27,58), (32,46),(9,93),(65,65)，分組排序只是變成各個分組內的下表，下同。
第二次排序步長為5/2 = 2
58 27 32 9 65 87 58
2A 2B
.......... ................................
第三次排序步長為2/2 = 1
32 9 58 27 58 46 65 65 93 87
1A 1B 1C 1D 1E 1 1 四次排序步長為1/2 = 0 得到有序元素序列
9 27 32 46 58 58 65 65 87 93
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
增量序列的选择：Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征(查到的资料都这么讲)：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
package cglib;
public class StringNumber {
public static void main(String[] args) {
int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};
System.out.print("排序前：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
shellSort(arr);
System.out.print("排序后：");
for(int o: arr) {
System.out.print(o+" ");
}
System.out.println();
}
private static void shellSort(int[] arr) {
int j;
int len = arr.length;
for(int val=len>>1; val>0; val>>=1) {
//下面是对本次的所有分组做直接插入排序
for(int i=val; i<len; i++) {
System.out.println("for:i="+i);
System.out.println("for:arr[i]="+arr[i]);
System.out.println("for:val="+val);
int temp = arr[i];
/*
* 为什么每次都用temp比较呢？
* 因为直接插入就是找到temp的合适位置。
* 为什么temp<arr[j-val]这个条件可以放在for内呢？
* 因为原来的组内数据已经有序，找到位置就停止便是。
*
*/
for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
System.out.println("er:j="+j);
System.out.println("er:arr[j]="+arr[j]);
System.out.println("er:j-val="+(j-val));
System.out.println("er:arr[j-val]="+arr[j-val]);
/*
* 为什么是arr[j-val]不是arr[j]呢？
* 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val]
*/
arr[j] = arr[j-val];
System.out.println("赋值er:arr[j]="+arr[j]);
}
/*
* 注意不是arr[i] = temp
* 直接插入排序也是这样的。
* 为什么呢？
* 因为j是位置，i是待插入元素
*/
arr[j] = temp;
}
}
}
}输出：
排序前：44 33 99 10 30 20 59 78 23 48 for:i=5 for:arr[i]=20 for:val=5 er:j=5 er:arr[j]=20 er:j-val=0 er:arr[j-val]=44 赋值er:arr[j]=44 for:i=6 for:arr[i]=59 for:val=5 for:i=7 for:arr[i]=78 for:val=5 er:j=7 er:arr[j]=78 er:j-val=2 er:arr[j-val]=99 赋值er:arr[j]=99 for:i=8 for:arr[i]=23 for:val=5 for:i=9 for:arr[i]=48 for:val=5 for:i=2 for:arr[i]=78 for:val=2 for:i=3 for:arr[i]=10 for:val=2 er:j=3 er:arr[j]=10 er:j-val=1 er:arr[j-val]=33 赋值er:arr[j]=33 for:i=4 for:arr[i]=30 for:val=2 er:j=4 er:arr[j]=30 er:j-val=2 er:arr[j-val]=78 赋值er:arr[j]=78 for:i=5 for:arr[i]=44 for:val=2 for:i=6 for:arr[i]=59 for:val=2 er:j=6 er:arr[j]=59 er:j-val=4 er:arr[j-val]=78 赋值er:arr[j]=78 for:i=7 for:arr[i]=99 for:val=2 for:i=8 for:arr[i]=23 for:val=2 er:j=8 er:arr[j]=23 er:j-val=6 er:arr[j-val]=78 赋值er:arr[j]=78 er:j=6 er:arr[j]=78 er:j-val=4 er:arr[j-val]=59 赋值er:arr[j]=59 er:j=4 er:arr[j]=59 er:j-val=2 er:arr[j-val]=30 赋值er:arr[j]=30 for:i=9 for:arr[i]=48 for:val=2 er:j=9 er:arr[j]=48 er:j-val=7 er:arr[j-val]=99 赋值er:arr[j]=99 for:i=1 for:arr[i]=10 for:val=1 er:j=1 er:arr[j]=10 er:j-val=0 er:arr[j-val]=20 赋值er:arr[j]=20 for:i=2 for:arr[i]=23 for:val=1 for:i=3 for:arr[i]=33 for:val=1 for:i=4 for:arr[i]=30 for:val=1 er:j=4 er:arr[j]=30 er:j-val=3 er:arr[j-val]=33 赋值er:arr[j]=33 for:i=5 for:arr[i]=44 for:val=1 for:i=6 for:arr[i]=59 for:val=1 for:i=7 for:arr[i]=48 for:val=1 er:j=7 er:arr[j]=48 er:j-val=6 er:arr[j-val]=59 赋值er:arr[j]=59 for:i=8 for:arr[i]=78 for:val=1 for:i=9 for:arr[i]=99 for:val=1 排序后：10 20 23 30 33 44 48 59 78 99
选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
package cglib;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
public class StringNumber {
public static void main(String[] args){
Random random = new Random();
int[] array = new int[2000];
for (int j = 0; j < 2000; j++) {
array[j] = random.nextInt(100000);
}
System.out.println(Arrays.toString(array));
selectSortTest(array);
System.out.println(Arrays.toString(array));
}
public static void selectSortTest(int a[]) {
Date dateStart = new Date();
selectSort(a);
Date dateEnd = new Date();
System.out.println("选择排序耗费时间："
+ (dateEnd.getTime() - dateStart.getTime()));
}
public static void selectSort(int a[]){
int n = a.length;
for(int k=0; k<n-1; k++) {
int min = k;
for(int i=k+1; i<n; i++) {//找出最小值
if(a[i] < a[min]) {
min = i;
}
}
if(k != min) {
int temp = a[k];
a[k] = a[min];
a[min] = temp;
}
}
}
}
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
熱門話題
突破或從Java 8流返回？
Feb 07, 2025 pm 12:09 PM
Java 8引入了Stream API，提供了一種強大且表達力豐富的處理數據集合的方式。然而，使用Stream時，一個常見問題是：如何從forEach操作中中斷或返回？ 傳統循環允許提前中斷或返回，但Stream的forEach方法並不直接支持這種方式。本文將解釋原因，並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀： Java Stream API改進 理解Stream forEach forEach方法是一個終端操作，它對Stream中的每個元素執行一個操作。它的設計意圖是處
Java程序查找膠囊的體積
Feb 07, 2025 am 11:37 AM
膠囊是一種三維幾何圖形，由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下： 膠囊體積 = 圓柱體體積 兩個半球體體積 其中， r: 半球體的半徑。 h: 圓柱體的高度（不包括半球體）。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積： 體積 = π × r2 × h (4
如何在Spring Tool Suite中運行第一個春季啟動應用程序？
Feb 07, 2025 pm 12:11 PM
Spring Boot簡化了可靠，可擴展和生產就緒的Java應用的創建，從而徹底改變了Java開發。 它的“慣例慣例”方法（春季生態系統固有的慣例），最小化手動設置
