【計理02組06號】十大經典排序算法【上篇】

yyyyfly 2022-01-07 09:27:44 阅读数:605

十大 排序 算法 上篇

冒泡排序

冒泡排序(Bubble Sort)是基於交換的排序,每次遍曆需要排序的元素,依次比較相鄰的兩個元素的大小,如果前一個元素大於後一個元素則兩者交換,保證最後一個數字一定是最大的(假設按照從小到大排序),即最後一個元素已經排好序,下一輪只需要保證前面 n-1 個元素的順序即可。

之所以稱為冒泡,是因為最大/最小的數,每一次都往後面冒,就像是水裏面的氣泡一樣。

排序(假設從小到大)的步驟如下:

  1. 從頭開始,比較相鄰的兩個數,如果第一個數比第二個數大,那麼就交換它們比特置。
  2. 從開始到最後一對比較完成,一輪結束後,最後一個元素的比特置已經確定。
  3. 除了最後一個元素以外,前面的所有未排好序的元素重複前面兩個步驟。
  4. 重複前面 1 ~ 3 步驟,直到所有元素都已經排好序。

例如,我們需要對數組 [98,90,34,56,21] 進行從小到大排序,每一次都需要將數組最大的移動到數組尾部。

交換具體邏輯如下圖所示:

接下來兩輪排序確定好了第二個和第三個的比特置,其實這個數組已經完成排序了,一共 5 個數,冒泡 4 次即可。

紫色錶示已經排好的元素,柳丁紅色錶示正在比較/交換的元素,可以看出前面兩次排序之後,已經確定好了最大兩個數的比特置。

java代碼

查看代碼
public class BubbleSort {
public static void bubbleSort(int[] nums) {
int size=nums.length;
for(int i=0;i<size-1;i++) {
System.out.println("第"+(i+1)+"輪交換開始");
for(int j=0;j<size-1-i;j++) {
if(nums[j]>nums[j+1]) {
int temp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=temp;
}
printf(nums);
}
}
}
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]nums = new int[]{98,90,34,56,21};
printf(nums);
bubbleSort(nums);
}
}

 

測試結果

選擇排序

插入排序

希爾排序

快速排序

排序穩定性的分析

時間複雜度和空間複雜度

版权声明:本文为[yyyyfly]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070927443163.html