冒泡排序

• 決定冒泡的方向，每次冒泡相鄰元素比較，每次固定一個泡。
• 如果一趟未產(chǎn)生任何交換，則整個序列已排序，無需再比較。
• 時間復(fù)雜度：比較的次數(shù)n-1 … 1 , 總和 O(n^2) , 空間復(fù)雜度 O(1)

int a[100] = {1, 2, 10, 3, 5, 4, 2};
void swap(int i, int j) {
    if (i != j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
//冒泡排序, 從小到大
void bubbleSort(int a[], int n) {
    if (n <= 1) {
        return;
    }

    for (int i = 0; i < n - 1; i++) { //每次要確定的冒泡元素
        int sorted = 1;  //做一個優(yōu)化，如果一趟排序中都沒有產(chǎn)生交換，則不需要以后操作
        for (int j = n - 1; j > i; j--) { //從后往前冒
            if (a[j] < a[j - 1]) {
                swap(j, j-1);
                sorted = 0;
            }
        }

        if (sorted == 1) {
            break;
        }
    }
}

快速排序

• 快排核心找基準(zhǔn)數(shù)，把基準(zhǔn)數(shù)放到某一個位置，左邊的都比它小，右邊的都比它大。
• 如果我們以最左邊的為基準(zhǔn)，那么需要注意的是為什么從右邊找，因?yàn)閺淖筮呎?，你可能無法找到比它小的元素，這樣你就無法執(zhí)行基準(zhǔn)數(shù)和找到的數(shù)的交換，如果從右邊找，至少可以找到剛好等于基準(zhǔn)數(shù)的元素，這樣才滿足基準(zhǔn)數(shù)左邊都小于，右邊都大于的思想。
• 時間復(fù)雜度：如果每次被二分，總共被分成的是logn 趟， 每次比較的是 n 次， 時間復(fù)雜度 O(nlogn), 空間復(fù)雜度 O(1) 。

void quickSortByRange(int a[], int left, int right){
    if (left >= right) {
        return;
    }
    int l = left;
    int r = right;
    int pivotIndex = left;
    int pivot = a[left];
    //基準(zhǔn)數(shù)在左邊，為什么是從右邊找，而不是從左邊找呢，因?yàn)槿绻麖淖筮呎遥愫芸赡苷也坏?，這樣就無法執(zhí)行
    //基準(zhǔn)數(shù)和相遇點(diǎn)的交換了，而從左邊找，至少可以直接找到基準(zhǔn)數(shù)的這個位置
    while (left < right) {
        while (left < right && a[right] >= pivot) { //從右邊找到比基準(zhǔn)數(shù)小的那個
            right--;
        }
        while (left < right && a[left] <= pivot) {
            left++;
        }
        if (left < right) {
            swap(left, right);
        }
    }

    if (left <= right) { //在不出現(xiàn)越界的情況下，執(zhí)行基準(zhǔn)和相遇點(diǎn)的交換
        swap(pivotIndex, left);
        quickSortByRange(a, l, left - 1);
        quickSortByRange(a, left + 1, r);
    }
}
void quickSort(int a[], int n) {
    if (n <= 1) {
        return;
    }
    quickSortByRange(a, 0, n - 1);
}

插入排序

• 插入排序關(guān)鍵在于插入，分割為排序和未排序部分，不斷把右邊的元素插入到左邊的序列中，注意是相鄰元素交換。
• 時間復(fù)雜度：O(n^2), 空間復(fù)雜度 O(1)

void insertOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }
    
     //每次選定一個元素同前面的已排序的元素做對比，找到應(yīng)該插入的位置
    for (int i = 1; i < n; i++) {
        int key = array[i];
        
        int j = i - 1;
        while (j >= 0) {
            if (key > array[j]) {
                swap(array, j, j+1);
            }
            else {
                break;
            }
            j--;
        }
        
    }
}

選擇排序

• 選擇排序每次從未排序的隊列中選擇出最大或者最小元素，放到已排序的隊列末尾。
• 時間復(fù)雜度: O(n^2) , 空間復(fù)雜度: O(1)

///選擇排序,降序,
void selectOrder(int array[], int n) {
    if (n <= 1) {
        return;
    }

    //選擇排序，每次從無序的被選的元素中找最大或者最小的放到有序的環(huán)境中
    for (int i = 0; i < n; i++){
        int selectIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] > array[i]) {
                selectIndex = j;
            }
        }
       swap(array, i, selectIndex);
    }
  }
}

其他

• 因?yàn)榭炫艙碛斜容^好的平均時間復(fù)雜度，所以快排用的范圍相對來說更廣一些。