Java實現基本排序算法的示例代碼
1. 概述
排序概念：就是將一串記錄按照其中某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性：通俗的將就是數據元素不發生有間隔的交換，例如：
內部排序：數據元素全部放在內存中的排序
外部排序：數據元素太多不能一次加載到內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
註意：以下的排序默認排升序。默認待排序列為：2，5，1，3，8，6，9，4，7，0，6
2. 插入排序
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
2.1 直接插入排序
1. 思想：
對於一個元素，將其與前面元素進行比較，將其插入到合適的位置。
排升序：將待排元素依次與序列中元素從右往左比，若待排元素小，則繼續往前比，找到合適位置插入，原來元素的位置按順序往後搬移。
2. 畫圖說明：
說明：第一個元素默認它有序，所以從第二個元素開始進行比較然後插入，5比2大，繼續下一個，將1依次比較插入2前面，將3依次比較插入5前面，8比5大，不用管，繼續下一個，將6依次比較插在8面，9比8大，不用管，將7依次比較，插在8前面，將0依次比較插在1前面，將6依次比較插在7前面，插入完成。
3.代碼展示：
public class InsertSort {
public static void insertSort(int[] array){
for(int i = 1;i < array.length;i++){ //讓從1下標開始，因為如果隻有一個元素，它自己默認有序
int key = array[i]; //從數組中的第二個元素開始比較，進行插入
int end = i-1; //end的位置是要插入元素的前一個位置
while(end >= 0 && key < array[end]){ //end不能越界，找待插入的位置，此處註意：key不能小於等於array[end]，否則為不穩定
array[end+1] = array[end];
end--;
}
array[end+1] = key; //找到位置進行插入，因為上面end--瞭，所以這裡要插入的位置為end+1
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
insertSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結果：
4.特性總結：
時間復雜度：循環嵌套，O(N^2)，最優情況：當序列接近有序，插入的元素比較少，為O(N)
空間復雜度：不借助輔助空間，O(1)
穩定性：數據元素不發生有間隔的交換，穩定
應用場景：數據量小，接近有序
2.2 希爾排序（縮小增量排序）
1. 思想：
選一個整數為數據元素的間隔，將間隔相同的數據元素分為一組，分別對這些組進行插入排序，間隔減小，重復上述操作，當間隔減少到1的時候，數據元素即排好序瞭。
2. 畫圖說明：
說明：gap為間隔，這裡依次將gap=4，2，1，先把間隔為4的數據元素用插入排序排好序，再利用插入排序排gap=2 的數據元素，依次重復上述操作，即可。
3. 代碼展示：
public class ShellSort {
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap = gap/3+1;
for(int i = gap;i < array.length;i++){ //跟插入排序一樣，都從一組數的第二個元素開始，因為第一個數默認有序
int key = array[i];
int end = i - gap; //end的位置也是代排數的前一個，但這裡間隔為gap，所以前一個位置為i-gap
while(end >= 0 && key < array[end]){ //與插入排序保持不變,找待插入的位置
array[end+gap] = array[end]; // key小於前一個數，讓end位置的元素往後移一位，
end -= gap; //end每次向左走的時候一次走gap的間隔
}
array[end+gap] = key; //找到待排位置將key插入相應位置
}
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
shellSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結果：
4. 特性總結：
希爾排序是對直接插入排序的優化。
當gap>1時都是預排序，目的是讓數組元素接近有序，當gap==1時，數組已經接近有序瞭，這樣插入排序將會很快，整體而言，達到瞭優化的效果。
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算。
gap的取法有多種，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，後來，Kunth提出取gap = [gap/3]+1。在Kunth所著的《計算機程序設計技巧》第3卷中，利用大量的實驗統計資料得出，當n很大時，關鍵碼的平均比較次數和對象平均移動次數大約在n^1.25到1.6n^1.25范圍內，這是利用直接插入排序作為子序列排序方法的情況下得到的。
故時間復雜度暫記為：O(N^1.25)~O(1.6N^1.25)
空間復雜度：沒有借助輔助空間，O(1)
穩定性：數據元素發生瞭有間隔的交換，不穩定
應用場景：數據比較隨機
3. 選擇排序
每一次從待排數據元素中選出最小（最大）的元素，存放在序列的起始（末尾）位置，直到全部待排序的數據元素全部排完。
3.1 直接選擇排序
1. 思想：
思路1：
找出序列中的最大的元素，若它不在序列的末尾，將它與末尾元素交換位置，依次循環。
思路2：
每次找元素的時候，找一個最大的和一個最小的，最大的和最後一個交換位置，最小的和第一個交換位置，依次循環
2. 畫圖說明：
思路1：
說明：先找到序列的最大元素與序列最後一個元素交換，序列的最後的位置朝前移一個，再找新序列的最大元素再與最後一個交換位置，依次循環。
思路2：
說明：這種方法是一次找兩個元素，跟上面那種本質上一樣，隻是一次交換瞭兩個元素，將最大的與最後一個交換，將最小的與第一個交換
3. 代碼展示：
public class SelectSort {
public static void selectSort1(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){ //選擇的趟數，size-1是因為當選擇到序列剩一個元素時就不用選瞭
int pos = 0; //pos標記最大元素的位置，剛開始是默認為第一個位置
for(int j = 1;j < size-i;j++){ //j=1是因為默認第一個元素的位置為最大元素的位置，所以從第二個元素的位置開始比較
//size-i是因為每趟選擇完後，序列都要減少一個
if(array[j] > array[pos]){
pos = j; //找到最大元素位置，更新pos
}
}
if(pos != size-i-1){ //如果最大元素的位置剛好是最後一個位置，則不需要交換，反之進行交換
swap(array,pos,size-i-1);
}
}
}
public static void selectSort2(int[] array){
int left = 0; //序列的左邊界
int right = array.length-1; //序列的右邊界
while(left < right){ //當序列中至少存在倆元素時
int minPos = left; //剛開始將最小元素的位置設定為序列的第一個位置
int maxPos = left; //剛開始將最大元素的位置也設定為序列的第一個位置
int index = left+1; //從序列的第二個元素開始找最大元素和最小元素的位置
//找最大元素和最小元素的位置
while(index <= right){
if(array[index] < array[minPos]){
minPos = index;
}
if(array[index] > array[maxPos]){
maxPos = index;
}
index++;
}
if(minPos != left){ //當最小的元素不在序列的最左端時交換位置
swap(array,minPos,left);
}
//這裡我是先交換最小的元素，但是如果最大的元素在最左側，那麼會將maxPos位置的元素更新為最小的元素，導致後面
//交換最大元素的時候maxPos標記的元素不準確，所以下面將maxPos的位置更新瞭一下
//註意：如果是先交換最大的元素，則更新minPos的位置
if(maxPos == left){
maxPos = minPos;
}
// if(minPos == right){
// minPos = maxPos;
// }
if(maxPos != right){ //當最大元素不在序列的最右端時交換位置
swap(array,maxPos,right);
}
left++; //左邊界+1
right--; //右邊界-1
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {9,5,1,3,8,6,2,4,7,6,0};
selectSort1(array);
for(int i : array){
System.out.print(i+" ");
}
System.out.println();
selectSort2(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
4：特性總結：
時間復雜度：找元素，交換元素是循環嵌套，O(N^2)
空間復雜度：沒有借助輔助空間，O(1)
穩定性：數據元素存在有間隔的交換，不穩定
缺陷：找最大元素或者最小元素的時候重復比較
3.2 堆排序
1. 思想：
堆排序是利用堆積樹（堆）這種數據結構設計的一種算法，它是選擇排序的一種，它是通過堆來進行選擇數據。
註意：排升序，建大根堆，排降序，建小根堆。
堆排序分為兩部分：建堆，利用向下調整建堆，再利用堆刪除的思想排序。
向下調整：
前提：要調整的節點的兩個左右子樹都已滿足堆的特性
方法：建大堆，將根的元素與左右孩子較大的元素交換，建小堆，將根的元素與左右孩子較小的元素交換
堆刪除思想：
將堆頂元素與最後一個元素交換位置
堆中有效元素減少一個
再對堆頂元素向下調整
2. 畫圖說明：
因為數據元素多，二叉樹的圖看著不太清晰，所以我用以下序列：0，5，3，4，1，2
建堆：
利用堆刪除思想排序：
3. 代碼展示：
public class HeapSort {
//向下調整
public static void shiftDown(int[] array,int parent,int size){
int child = parent*2+1; //默認將左孩子設為parent的孩子，因為不知道右邊孩子是否存在
while(child<size){
if(child+1<size && array[child+1]>array[child]){ //如果右孩子存在，比較哪個孩子值大
child += 1; //將child設為較大的孩子
}
if(array[parent]<array[child]){ //如果parent小，將parent與child交換
swap(array,parent,child);
parent = child; //更新parent
child = parent*2+1; //更新child
}else{ //如果已經滿足堆特性則直接返回
return;
}
}
}
//堆排序
public static void heapSort(int[] array){
//建堆
int size = array.length;
int lastLeaf = ((size-1)-1)/2; //找到倒數第一個非葉子節點
for(int root=lastLeaf;root>=0;root--){ //從該結點開始，依次向下調整直到根節點
shiftDown(array,root,size);
}
//利用堆刪除思想排序,從最後一個元素開始與堆頂元素交換，然後對堆頂元素進行向下調整
int end = size-1;
while(end>0){
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
heapSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結果：
4. 特性總結：
時間復雜度：n個元素進行比較，而且太向下調整，調整的深度為完全二叉樹的深度，故時間復雜度為：O(NlogN),logN是log以2為底的N
空間復雜度：沒有借助輔助空間，O(1)
穩定性：元素發生瞭有間隔的交換，不穩定
應用場景：求前k個最小或者最大，可以和其他排序結合起來增加效率
4. 交換排序
基本思想就是根據序列中兩個記錄鍵值的比較結果來交換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
4.1 冒泡排序
1. 思想：
依次將序列元素進行比較，若array[i]>array[i+1],交換兩個元素的位置，直到最後一個元素，從中可以得出，每躺冒泡隻能確定一個元素的位置，若序列有n個元素，則需要進行n-1躺冒泡，因為序列最後一個元素的位置不用確定。
從比較的次數可以看出：第一躺比較的次數為n-1，第二躺的比較次數為n-2…..即每趟冒泡比較的次數在遞減，即比較次數是為n-1-i，i為冒泡的趟數。
2. 畫圖說明：
3. 冒泡排序的優化：
從上圖可以看出第10躺冒泡沒有進行，因為序列已經有序，即數據元素不在發生交換。
優化：在每趟進行的開始給一個標記isChage=false，如果該躺冒泡發生瞭元素交換，將isChange=true，在每趟冒泡完進行判斷，如果是Change==false，即沒有發生交換，說明序列已經有序，即不用在繼續冒泡，直接返回即可。
4. 代碼展示：
public class BubbleSort {
public static void bubbleSort(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){
boolean isChange = false; //為瞭優化冒泡排序給的標記，當元素不發生交換的時候說明已經有序
for(int j = 0;j < size-1-i;j++){
if(array[j+1] < array[j]){
swap(array,j,j+1);
isChange = true;
}
}
if(isChange == false){ //如果元素不發生交換，直接返回
return;
}
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
bubbleSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結果：
5. 特性總結：
時間復雜度：冒泡的趟數，每趟的比較次數，O(N^2)
空間復雜度：不借助輔助空間，O(1)
穩定性：數據元素雖然發生瞭交換，但是沒有間隔交換，穩定
4.2 快速排序
4.2.1. 思想
快速排序是Hoare提出的一種二叉樹結構的交換排序方法。
基本思想為：任取待排元素序列中的某個元素作為基準值（這裡我們取最右側元素為基準值），按照該基準值將序列劃分為兩個區間，左側比基準值小，右側比基準值大，再分別用快速排序遞歸排左區間和右區間。
參考代碼：
public static void quickSort(int[] array,int left,int right){ //左閉右開
if(right-left > 1){ //遞歸的返回條件，區間最少得有兩個元素
int div = partition(array,left,right);
quickSort(array,left,div); //遞歸排左側
quickSort(array,div+1,right); //遞歸排右側
}
}
故隻要實現分割方法即可。
4.2.2 三種分割方式
1. Hoare法
思想：在左邊找比基準值大的，右邊找比基準值小的，兩個交換位置，最後將較大一側的第一個元素與基準值交換位置。
畫圖說明：
參考代碼：
//分割區間方法1：hoare：左邊找比基準值大的，右邊找比基準值小的，兩個交換位置,最後再將基準值放到中間的位置
public static int partition1(int[] array,int left,int right){
int key = array[right-1]; //找基準值，以最右側元素為基準值
int begin = left; //在左側找的下標
int end = right-1; //在右側找的下標
while(begin < end){
while(array[begin] <= key && begin < end){ //左側找大的，不能越界
begin++;
}
while(array[end] >= key && end > begin){ //右側找小的，不能越界
end--;
}
if(begin != end){
swap(array,begin,end); //begin與end不在同一位置的時候交換，否則沒有交換的必要
}
}
if(begin != right-1){
swap(array,begin,right-1); //將基準值與begin位置的元素交換，begin或者end都行
}
return end; //將分割的位置返回，begin與end都可以
}
2. 挖坑法
思想：將基準值存入key中，基準值的位置為第一個坑位，在左側找比基準值大的，放到第一個坑位上，此時這個元素的原始位置又形成瞭一個新的坑位，再從右側找比基準值小的，放到前面的坑位上，依次循環，即將序列分割為兩部分。
畫圖說明：
參考代碼：
//分割區間方法二：挖坑法：基準值是一個坑位，左側找大的放到基準值的坑位上，此時形成瞭新的坑位，再在右側找小的放到上一個坑位，依次循環
public static int partition2(int[] array,int left,int right){
int key = array[right-1]; //取最右側元素為基準值，end的位置形成瞭第一個坑位
int begin = left;
int end = right-1;
while(begin < end){
while(begin < end && key >= array[begin]){ //在左側找比基準值大的
begin++;
}
if(begin < end){
array[end] = array[begin]; //填end坑位，重新生成begin坑位
}
while(begin < end && key <= array[end]){ //在右側找比基準值小的
end--;
}
if(begin < end){
array[begin] = array[end]; //填begin坑位，重新生成end坑位
}
}
array[begin] = key; //將基準值填充在最後一個坑位
return end;
}
3. 前後標記法
思想：給兩個標記cur，pre，pre標記cur的前一個，cur開始標記第一個元素，依次往後走，cur小於區間的右邊界，如果cur小於基準值並且++pre不等於cur交換cur與pre位置的元素，最後交換++pre與基準值位置的元素。
畫圖說明：
參考代碼：
//分割區間方法三：前後標記法
public static int partition3(int[] array,int left,int right){
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當cur位置的元素小於基準值並且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準值交換的位置，所以當++pre！=right-1的時候，交換基準值的位置
swap(array,pre,right-1);
}
return pre;
}
4.2.3 快速排序的優化
快速排序的優化：對基準值的選取進行優化，這樣做是為瞭選取的基準值盡可能的將區間的左右側分的均勻一點兒。
優化方法：三數取中法取基準值，三數：區間的中間元素，最左側元素，最右側元素，取它們三個的中間值。
參考代碼：
//快排優化：三數取中法來取基準值，左側，右側，中間這三個數的中間值來作為基準值,這裡返回的是基準值下標
public static int getIndexOfMid(int[] array,int left,int right){
int mid = left+((right-left)>>1);
if(array[left] < array[right-1]){ //最右側的下標為right-1
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(array[mid] < array[right-1]){
return right-1;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}
具體與之前代碼結合方式，我這裡選取一種分割方法來進行優化：
參考代碼：
//分割區間方法三：前後標記法
public static int partition3(int[] array,int left,int right){
int index = getIndexOfMid(array,left,right); //用三數取中法獲得基準值的下標
if(index != right-1){
swap(array,index,right-1); //如果下表不在最右側就交換
}
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當cur位置的元素小於基準值並且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準值交換的位置，所以當++pre！=right-1的時候，交換基準值的位置
swap(array,pre,right-1);
}
return pre;
}
4.2.4 快速排序的非遞歸方式
非遞歸的快速排序借助棧這一數據結構
參考代碼：
//非遞歸的快速排序，利用棧來保存分割的區間，傳參隻需要傳數組即可
public static void quickSort(int[] array){
Stack<Integer> s = new Stack<>();
s.push(array.length);
s.push(0);
while(!s.empty()){
int left = s.pop();
int right = s.pop();
if(right - left == 0){
continue;
}
int div = partition(array,left,right);
s.push(right);
s.push(div+1);
s.push(div);
s.push(left);
}
}
4.2.5 快速排序的特性總結
時間復雜度：有比較，遞歸，O(NlogN)
空間復雜度：存在遞歸，遞歸的深度為完全二叉樹的深度，O(logN)
穩定性：數據元素發生有間隔的交換，不穩定
應用場景：數據凌亂且隨機
5. 歸並排序
1. 思想：
歸並排序是將兩個有序序列進行合並，但是我們拿到是一個數組，所以得先將數組遞歸均分為兩部分，再將兩部分進行合並。
2. 畫圖說明：
遞歸均分：
從下往上合並：
3. 代碼展示：
public class MergeSort {
public static void mergeSort(int[] array,int left,int right,int[] temp){
if(right - left > 1){
int mid = left+((right-left)>>1);
mergeSort(array,left,mid,temp); //遞歸均分左側
mergeSort(array,mid,right,temp); //遞歸均分右側
mergeData(array,left,mid,right,temp); //合並兩個序列，[left,mid) , [mid,right)
System.arraycopy(temp,left,array,left,right-left); //拷貝到原數組，源，起始位置，新，起始位置，長度
}
}
public static void mergeData(int[] array,int left,int mid,int right,int[] temp){
//[begin1,end1),[begin2,end2),為兩個合並的區間
int begin1 = left;
int end1 = mid;
int begin2 = mid;
int end2 = right;
int index = left; //輔助數組的下標
while(begin1 < end1 && begin2 < end2){
if(array[begin1] <= array[begin2]){
temp[index++] = array[begin1++];
}else{
temp[index++] = array[begin2++];
}
}
while(begin1 < end1){
temp[index++] = array[begin1++];
}
while(begin2 < end2){
temp[index++] = array[begin2++];
}
}
//重新包裝一下，便於用戶傳參
public static void mergeSort(int[] array){
int[] temp = new int[array.length];
mergeSort(array,0,array.length,temp);
}
}
4. 非遞歸的歸並排序
給一個間隔，用間隔來表示區間
參考代碼：
//非遞歸的歸並排序
public static void mergeSortNor(int[] array){
int size = array.length;
int[] temp = new int[size];
int gap = 1; //先每兩個元素歸並
while(gap < size){
for(int i = 0;i < size;i+=gap*2){
int left = i;
int mid = i+gap;
int right = mid+gap;
if(mid > size){ //防止mid越界
mid = size;
}
if(right > size){ //防止right越界
right = size;
}
mergeData(array,left,mid,right,temp);
}
System.arraycopy(temp,0,array,0,size);
gap <<= 1;
}
}
5. 特性總結：
時間復雜度：O(NlogN)
空間復雜度：借助瞭輔助空間，為輔助數組的大小，O(N)
穩定性：數據元素不發生有間隔的交換，穩定
應用場景：適合外部排序
6. 計數排序（非比較類型的排序）
1. 思想：
計數排序又稱鴿巢原理，是對哈希直接定址法的變形應用
步驟：
統計相同元素出現次數
根據統計的結果將序列回收到原來的序列中
2. 畫圖說明：
3. 代碼展示：
public class CountSort {
public static void countSort(int[] array){
//找出數組的最大值與最小值
int maxNum = array[0];
int minNum = array[0];
for(int i = 1;i < array.length;i++){
if(array[i] > maxNum){
maxNum = array[i];
}
if(array[i] < minNum){
minNum = array[i];
}
}
int range = maxNum - minNum + 1; //序列元素的范圍大小
int[] count = new int[range]; //new一個范圍大小的數組
for(int i = 0;i < array.length;i++){
count[array[i]-minNum]++; //讀取
}
int index = 0; //存入原數組的下標
for(int i = 0;i < range;i++){
while(count[i] > 0){
array[index] = i + minNum;
index++;
count[i]--;
}
}
}
}
4. 性能總結：
時間復雜度：O(N)
空間復雜度：O(M),M為數據范圍的大小
穩定性：數據元素沒有進行有間隔的交換，穩定
應用場景：數據元素集中在某個范圍
7. 排序算法總結
| 排序方法 | 最好 | 平均 | 最壞 | 空間復雜度 | 穩定性 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
| 希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不穩定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | 不穩定 |
| 歸並排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 穩定 |
以上就是Java實現基本排序算法的示例代碼的詳細內容，更多關於Java排序算法的資料請關註WalkonNet其它相關文章！