注: 穩(wěn)定性: 相同的數在排序后順序不變就叫做穩(wěn)定

1.冒泡排序(超時):時間復雜度:O(n的平方),穩(wěn)定

int* sortArray(int* nums, int numsSize, int* returnSize){
    * returnSize = numsSize;
    // 冒泡排序
    // 整個排序過程分為size -1組,每一組為了將較大值交換傳遞到尾部,最后剩下一個不用交換,所以是size-1,
    for (int i = 0; i < numsSize - 1; i++) {
        // 每一組就是執(zhí)行比較大小然后交換,隨著i++組數增加,比較的次數就減少,
        int flag = 0;
        for (int j = 0; j < numsSize - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                flag = 1; // 只要后面的數還需要交換, 就證明排序沒有結束
            }
        }
        if (flag == 0) break; // 這一遍循環(huán)沒有進行交換,那就說明后面已經排好序了,結束
    }
    return nums;
}

缺點:

• 時間復雜度高,需要進行O(n)的兩輪比對;
• 交換位置的操作太頻繁,影響CPU執(zhí)行效率.

優(yōu)點:

• 穩(wěn)定 ,值相等時不會進行交換
• 原地排序不會開辟額外空間
• 最好情況面對已經排好序的數組,復雜度降低到O(n)

2.選擇排序(超時):時間復雜度:O(n的平方),不穩(wěn)定

// 方法1:低效的寫法,高效寫法請看方法2:
int* sortArray(int* nums, int numsSize, int* returnSize){
    * returnSize = numsSize;
    // 選擇排序
    for (int i = 0; i < numsSize - 1; i++) {
            // 注意點內層for循環(huán)
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] > nums[j]) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    return nums;
}
// 方法2:將交換優(yōu)化為賦值
for (int i = 0; i < numsSize - 1; i++) {
    // 將未排序組的第一個數標記為min
    int min = i;
    for (int j = i + 1; i < numsSize; j++) {
        if (nums[min] > nums[j]) {
            min = j;
        }
    }
    // 循環(huán)結束就拿到了min 指向最小的數  然后再交換到i的位置
    swap(nums, i, min);
}

• 就執(zhí)行效率來說,選擇排序是要優(yōu)于冒泡排序的, 因為冒泡排序在比較之后就會進行交換操作,而選擇排序不是,每次內循環(huán)就是找到最小值的下標,然后和頭部交換,雖然比較次數不會減少,但交換位置的操作少了,效率自然就高了.

缺點:

• 時間復雜度高,最好最壞都是O(n平方)
• 不穩(wěn)定

優(yōu)點:

• 原地排序,比冒泡高效

3.插入排序(方法2不會超時):時間復雜度:O(n的平方),穩(wěn)定, 最好情況能到O(n)

// 方法1:
int* sortArray(int* nums, int numsSize, int* returnSize){
    * returnSize = numsSize;
    // 插入排序
    for (int i = 1; i < numsSize; i++) {
        // 內循環(huán)是遞減的
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            } else {
                break;
            }
        }
    }
    return nums;
}
// 方法2:還是可以將交換優(yōu)化為賦值   
for (int i = 1; i < numsSize; i++) {
    int tmp = nums[i];  // 暫存
    int j;
    for (j = i; j > 0 && tmp < nums[j - 1]; j--) {
        // 暫存的這個值要是比前一位的值還小,就將前一位的值向后移,把前面的位置給tmp騰出來
        nums[j] = nums[j - 1];
    }
    // 移完了之后,就將暫存的臨時值放到騰出來的位置
    nums[j] = tmp;
}

• 缺點:時間復雜度高
• 優(yōu)點:1.有提前終止循環(huán)的情況,如果是面對近似有序的數組,效率奇高
• 2.原地排序不占額外空間,沒有交換位置的操作,執(zhí)行效率高
• 3.是一種穩(wěn)定的排序
• 最好情況能到O(n),吊打冒泡

4.快速排序(重要):時間復雜度O(nlogn),不穩(wěn)定

int partition(int* arr, int leftBound, int rightBound) {
    // 設定最后一個元素為樞紐元,  第一個元素為左指針
    int pivot = rightBound, left = leftBound;
    // 從頭到尾開始遍歷
    for (int i = leftBound; i <= rightBound; i++) {
        // 比樞紐元小的數就和left指針的值交換
        if (arr[i] < arr[pivot]) {
            // 防止left和i相等時,做無用的交換
            if (left != i) swap(arr, left, i);
            left ++;// 左指針右移一位
        }
    }
    // 循環(huán)完了之后,左指針左邊就是比樞紐元小的數,右邊就是比樞紐元大的數, 然后將左指針和樞紐元的位置交換
    swap(arr, left, pivot);
    return left;  // 將樞紐元返回
}
// 快速排序
void quickSort(int *arr, int leftBound, int rightBound) {
    if (leftBound > rightBound) return;
    // 采用劃分模塊的方法,先確定一個樞紐元,和他進行比較,小于他的放在左區(qū)域,大于他的放在右區(qū)域
    int pivot = partition(arr, leftBound, rightBound);
    // 將兩邊分區(qū)進行遞歸排序
    quickSort(arr, leftBound, pivot - 1);
    quickSort(arr, pivot + 1, rightBound);
}

缺點:

• 不穩(wěn)定
• 分區(qū)點的選擇有講究,選擇不當時最壞情況會退化為O(n平方)
• 需要把待排序的數組一次性讀入到內存里

優(yōu)點

• 速度快
• 原地排序

5.歸并排序()

和快排一樣,使用的是算法的分治思想,就是將一個大的問題分解為一個小問題,當問題分解到足夠小時,解決了這個小問題,大的問題也就迎刃而解.

void merge(int* arr, int leftPtr, int rightPtr, int rightBound) {
    // 中間值
    int mid = rightPtr - 1;
    int* temp = (int*)malloc(sizeof(int) * (rightBound - leftPtr + 1));
    
    // 定義三個指針
    int i = leftPtr, j = rightPtr, k = 0;
    
    while (i <= mid && j <= rightBound) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    // 處理 i 或者 j 提前結束
    while (i <= mid) temp[k++] = arr[i++];   // i 還有值
    while (j <= rightBound) temp[k++] = arr[j++];   // j 還有值
    
    // 將 temp 賦值給 arr
    for (int m = 0; m < (rightBound - leftPtr + 1); m++) {
        arr[leftPtr + m] = temp[m];
    }
}
void sort(int* arr, int left, int right) {
    if (left == right) return;
    // 分成兩半
    int mid = left + ((right - left) >> 1);
    // 左邊排序
    sort(arr, left, mid);
    // 右邊排序
    sort(arr, mid + 1, right);
    merge(arr, left, mid + 1, right);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    sort(nums, 0, numsSize - 1);
    return nums;
}

6.堆排序()

7.基數排序()

8.希爾排序()

9.計數排序()