冒泡排序

插入排序

可视化学习网站

void inserting_sort(int arr[], int len) {
	int i, j;
	int X;
	for (i = 1; i < len; i++) {
		X = arr[i];
		// arr[j] > X 只要 X 前面的数小于X, 就退出循环
		for (j = i - 1; j >= 0 && arr[j] > X; j--) {	// j 是要比较的元素的索引
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = X;

	}
}

外循环执行 N-1 次，这很明显。
但内循环执行的次数取决于输入：

• 在最好的情况下，数组已经排序并且 (a [j]> X) 总是为假。所以不需要移位数据，并且内部循环在O（1）时间内运行，
• 在最坏的情况下，数组被反向排序并且 (a [j]> X) 总是为真。插入始终发生在数组的前端，并且内部循环在O（N）时间内运行。
  因此，最佳情况时间是O(N × 1) = O(N) ，最坏情况时间是O(N × N) = O(N2).

归并排序

参考视频：排序算法：归并排序【图解+代码】

给定一个 N 个项目的数组，归并排序将：

1. 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组
2. 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程…，
3. 最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组

void merge(int arr[], int temp[], int left, int mid, int right) {
    // 标记左半区第一个未排序的元素
    int l_pos = left;
    // 标记右半区第一个未排序的元素
    int r_pos = mid + 1; 
    // 临时数组的下标元素
    int pos = left;

    // 合并
    while (l_pos <= mid && r_pos<= right) {
        if(arr[l_pos] < arr[r_pos]) { // 左半区，第一个剩余元素最小
            temp[pos++] = arr[l_pos++]; // 将更小的元素放到临时数组中 
        }else { // 右半区，第一个元素更小
            temp[pos++] = arr[r_pos++];
        }
    }

    // 合并左半区剩余的元素
    while (l_pos <= mid) {
        temp[pos++] = arr[l_pos++];
    }
    // 合并右半区剩余的元素
    while (r_pos <= right) {
        temp[pos++] = arr[r_pos++];
    }

    // 将临时的元素赋值返回给原来的数组
    while (left<=right) {
        arr[left] = temp[left];
        left++;
    }
}

void msort(int arr[],int temp[],int left, int right){
    // 如果只有一个元素，那么就不需要被划分
    // 只有一个元素的区域本身就是有序的，只需要被规并即可
    if(left < right) { // 只有left < right 的时候才划分
        // 找中间点 
        // 将【left, right】区域，划分为 【left, mid】【mid+1, right】两个区域
        int mid = (left + right) / 2;   

        // 对 【left, mid】递归的继续进行划分，直到只有一个元素的区域为止
        msort(arr, temp, left, mid);
        // 对 【mid+1, right】递归的继续进行划分
        msort(arr, temp, mid+1, right);

        // 此时，arr数组就被划分了很多个只有一个元素的区域

        // 划分完成后，就开始进行合并
        merge(arr, temp, left, mid, right);
    }

}


void merge_sort(int arr[], int n){
    int* temp = (int*)malloc(sizeof(int) * n);
    if(temp != NULL){
        msort(arr, temp, 0, n - 1);
        free(temp);
    } else {
        printf("error: failed to allocate memory");
    }
}

这段代码实现的是归并排序算法。它的时间复杂度可以通过递推公式来计算，假设n表示数组的大小，则：

T(n) = 2 * T(n/2) + O(n)

其中，2 * T(n/2)表示对两个规模为n/2的子问题进行递归调用，O(n)表示对两个子问题合并的时间复杂度。因此，根据主定理（Master Theorem），可以得到归并排序的时间复杂度为O(nlogn)。

需要注意的是，在实际应用中，由于归并排序涉及到大量的数组操作，而且需要在递归过程中不断地创建和销毁临时数组，因此其空间复杂度也比较高。具体来说，空间复杂度为O(n)

• 什么是主定理？

主定理（Master Theorem）是一种经典的算法复杂度分析方法，用于求解递归式的渐进复杂度。它的形式如下：T(n) = a * T(n/b) + f(n)。其中，a表示递归的子问题个数，n/b表示每个子问题的规模，f(n)表示除了递归之外剩余操作的时间复杂度。
根据主定理，可以将递归式划分为以下三种情况：

如果f(n) = O(n^c)，且logb(a) < c，则T(n) = Θ(n^c)。

如果f(n) = Θ(n^c)，且logb(a) = c，则T(n) = Θ(n^c logn)。

如果f(n) = Ω(n^c)，且存在常数d < 1和k ≥ 0，使得af(n/b^c) ≤ df(n)对所有足够大的n都成立，则T(n) = Θ(f(n))。

希尔排序

代码视频参考1

思路参考视频

void shell_sort(int arr[], int n){
    int i, j, inc, key;

    // 初始增量为 n/2       
    for(inc = n/2; inc > 0; inc = inc / 2) {
        // 每一趟采用插入排序
        for(i = inc; i < n; i++) { 
            key = arr[i];
            // 遍历 i 到 0 （中间有间隔，每个inc）
            for(j = i; j >= inc && key < arr[j-inc]; j -= inc) { 
                arr[j] = arr[j-inc];
            }
            arr[j] = key;
        }
    }
}

计数排序

void counting_sort(int arr[], int len){
    if(len < 1) return;

    // 寻找最大元素
    int max = arr[0];
    int i;
    for(i = 1; i < len - 1; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }

    // 分配一个长度为max + 1 的数组存储计数，并初始化为0
    int * count = (int*) malloc(sizeof(int) * (max + 1));
    memset(count, 0, sizeof(int)* (max+1));

    // 计数
    for(i = 0; i < len; i++) {
        count[arr[i]]++;
    }

    // 统计计数的累计值
    for(i = 0; i < max + 1; i++) {
        count[i] += count[i-1];
    }

    // 创建一个临时的数组保存结果
    int* output = (int*) malloc(sizeof(int)*len);


    // 将结果放到正确的位置上
    for(i = 0; i < len; i++) {
        output[count[arr[i] - 1]] = arr[i];
        count[arr[i]]--;
    }

    for(i = 0; i < len; i++) {
        arr[i] = output[i];
    }
}

堆排序