排序

冒泡排序

void BubbleSort(int* a, int n) {  // 冒泡排序法，添加数组长度参数
    for (int i = 0; i < n - 1; i++) {
        for (int j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) {
                int t = a[j - 1];
                a[j - 1] = a[j];
                a[j] = t;
            }
        }
    }
}

void printArr(int* a, int n) {    // 添加数组长度参数
    for (int i = 0; i < n; i++)   // 修正循环条件
        printf("%d  ", a[i]);
    printf("\n");
}

int main() {
    int a[] = { 23,54,12,67,879,567,435,45,32,4,54,345 };
    int n = sizeof(a) / sizeof(a[0]);  // 计算数组长度

    BubbleSort(a, n);      // 传递数组和长度
    printArr(a, n);        // 传递数组和长度

    return 0;
}</code></pre>
</div>

快速排序
定义开头的[0]为left,定义[n]为right,定义[0]为标准
原理:
通过left和right与标准的不断对比和移动，最后使得标准的左侧都比标准小，右侧都比标准大

#include<stdio.h>

void FastSort(int* a, int left, int right) {
    if (left < right) {
        int boss = a[left];       // 选择基准值
        int hole = left;          // 孔位初始指向第一个元素

        while (left < right) {
            // 从右向左查找小于基准值的元素
            while (left < right && a[right] >= boss) {
                right--;
            }
            a[hole] = a[right];
            hole = right;

            // 从左向右查找大于基准值的元素
            while (left < right && a[left] <= boss) {
                left++;
            }
            a[hole] = a[left];
            hole = left;
        }
        a[hole] = boss; // 将基准值放到中间位置

        // 递归对左右两部分排序
        FastSort(a, 0, hole - 1);
        FastSort(a, hole + 1, right);
    }
}

//遍历
void p(int* a, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d  ", a[i]);
    }
    printf("\n");
}

int main() {
    int a[] = { 4, 3, 30, 45, 54, 54, 67, 213, 435, 567, 879, 345 };
    int n = sizeof(a) / sizeof(a[0]);
    FastSort(a, 0, n - 1);
    p(a, n);
    return 0;
}

直接插入排序
循环开始：从数组的第二个元素（索引为1）开始，因为单个元素本身就是有序的。
保存当前元素：将当前元素arr[i]保存到key中。
比较和移动：将key与前面已排序部分的元素进行比较，如果前面的元素大于key，则将该元素向后移动一位。
插入位置：找到第一个小于等于key的元素位置，将key插入到该位置。

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j;
    for (i = 1; i < n; i++) { // 从数组的第二个元素开始循环
        int key = arr[i]; // 将当前元素赋值给key
        j = i - 1;

        // 将比key大的元素都依次向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 将key插入到正确的位置
    }
}

// 打印数组的函数
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6 }; // 定义一个数组
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组的长度

    insertionSort(arr, n); // 调用排序函数对数组进行排序

    printf("排序后的数组: \n");
    printArray(arr, n); // 打印排序后的数组
    return 0;
}

希尔排序

#include<stdio.h>

void insert(int* a, int n) {
	int gap = n / 2;
	while (gap >= 1) {
		for (int i = gap; i < n; i++) {
			int temp = a[i];
			int j = i;
			while(j>=gap && a[j - gap] > temp) {
				a[j] = a[j - gap];
				j -= gap;
			}
			a[j] = temp;
		}
		gap /= 2;
	}
	
}

void printArray(int arr[], int n) {
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main() {
	int arr[] = { 234,5,5678,54,68,7,546,3,42,5,789,0 }; // 定义一个数组
	int n = sizeof(arr) / sizeof(arr[0]); // 计算数组的长度

	insert(arr, n); // 调用排序函数对数组进行排序

	printf("排序后的数组: \n");
	printArray(arr, n); // 打印排序后的数组
	return 0;
}

直接选择排序

#include<stdio.h>

void insert(int* a, int n) {
	int temp, min;
	for (int i = 0; i < n - 1; i++) {
		min = i;
		for (int j = i + 1; j < n; j++) {
			if (a[j] < a[min]) {
				min = j;
			}
		}
		if (min != i) {
			temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

void printArray(int arr[], int n) {
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main() {
	int arr[] = { 234,5,5678,54,68,7,546,3,42,5,789,0 }; // 定义一个数组
	int n = sizeof(arr) / sizeof(arr[0]); // 计算数组的长度

	insert(arr, n); // 调用排序函数对数组进行排序

	printf("排序后的数组: \n");
	printArray(arr, n); // 打印排序后的数组
	return 0;
}

插帽龟，他很稳（插入，冒泡，归并）
插帽龟喜欢选帽插，插完就慌了（慌了=方了，n的平方）
快龟堆，见到n老（nlog n）