【資料結構】Java實作各類經典排序算法——選擇排序、冒泡排序

一、選擇排序

    顧名思義，選擇排序就是每次選出待選數組中最大的元素，放到待選數組右側即可。為了實作O(1)的空間複雜度呢，這個放到右側的操作通過元素在數組間交換來進行。

    第一次掃描整個大小為n的數組，最大的放數組最右邊；此後從左到右掃描數組前n-1、n-2...項，因為數組右端已經排序完成。下面是代碼實作：

public void chooseSort(int[] nums) {
        // 選擇排序
        for(int j = nums.length - 1; j > 0; j--) {
            int maxIndex = 0;
            for(int i = 1; i <= j; i++) {
                if(nums[i] > nums[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(nums, j, maxIndex);
        }
    }
           

    時間複雜度：代碼有兩重for循環，而且無論什麼情況下循環都不會提前中止。是以最壞、最好情況下，時間複雜度均為O(n2)；空間複雜度：顯然為O(1)；穩定性：當原數組中有大小相同的元素時，相同元素最左一個在排序過程中會被換到右邊去，是以不穩定。

二、冒泡排序

    這應該是很多同學接觸最早的排序算法了。和選擇排序類似，冒泡排序保證每一趟排序後，找出最大的元素放到數組最右側，隻是實作方案不同。選擇排序通過緩存、更新最大元素的index，最終把index對應元素一次交換到最右方進行；冒泡排序則通過控制相鄰元素的交換與不交換來把最大元素轉移到右側。以下是實作代碼：

public void bubbleSort(int[] nums) {
        // 冒泡排序
        for(int i = nums.length - 1; i > 0; i--) {
            boolean flag = true;  // 若此處不加flag位來提前結束，則算法循環結構與選擇排序完全一緻，最好情況下複雜度也為二次
            for(int j = 1; j <= i; j++) {
                if(nums[j-1] > nums[j]) {
                    swap(nums, j-1, j);
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }
           

    時間複雜度：可以看出，冒泡排序的循環結構和選擇排序是類似的，但在數組整體已經有序的情況下可以提前結束循環。是以最好情況為O(n)、最差為O(n2)、平均為O(n2)；空間複雜度：O(1)；穩定性：數組中有相同大小元素時，相同大小元素若不相鄰，則會在排序過程中被逐漸交換到相鄰，過程中相對位置明顯不改變。相鄰之後，相同大小元素區間内不會再進行交換，是以算法穩定。

    在原數組“基本有序”的情況下，冒泡排序時間複雜度可以接近線性。反序情況下，與選擇排序同為O(n2)時間複雜度，且因為交換次數過多，效率低于選擇排序。