简单排序
简单排序有三种, 冒泡排序,选择排序,插入排序
冒泡排序
冒泡排序是一种易于实现的排序算法, 以升序为例:
有n个数, 需要比较n-1轮, 每轮比较数组中相邻的两个数, 前者大就交换两数.
第一轮时, 最大的数就会如冒泡般移向队尾, 下一轮比较就可以少比较一个数.
//冒泡排序
void bubbleSort(int arr[], int n){
for (int i = 0; i < n-1 ; i++ ) {
for (int j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
swap(&arr[j-1], &arr[j]);
}
}
}
}
因为用的是C语言, 遇到了java中完全遇不到的两个bug.
第一点是交换值, 必须要传地址才有卵用, 否则毫无卵用
// 交换函数, 必须传递引用才能交换成功
// 传值只是将实参复制给了形参一份, 在函数内如何改变形参与实参无关
// 传递引用, &arr[i], 取地址, a = &arr[i], *a = *(&arr[i]) = arr[i]
// 因此改变的就是实参的值
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
另一点是获取数组长度.
按照道理, 用运算符sizeof可以计算出数组的容量（字节数）,在除以单个元素的容量就能得到数组的长度了.
(sizeof(array) / sizeof(array[0]));
结果我真的是naive. 当我想打印数组时, 搞了个函数
void printfArray(int arr[]){
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; i++) {
printf("%d, ", arr[i]);
}
}
怎么打都只能打出两个数字, 百思不得其解啊尼玛
在C/C++中, 数组在作为参数传递时, 会退化为同类型的指针, 并没有办法知道指针所指的内存容量，除非在申请内存时记住它。
无论数组长度为多少, 以int数组为例, sizeof(a)始终等于sizeof(int *), 所以函数中传递只能把传数组个数传过去
void printfArray(int arr[], int len){
for (int i = 0; i < len; i++) {
printf("%d, ", arr[i]);
}
}
选择排序
选择排序, 以升序为例:
第一轮比较, 从arr[0]开始依次比较, 找出最小的数的下标, 记录下来, 将arr[0]与最小值交换.
第二轮从arr[1]开始依次比较, 找出最小的数的下标, 记录下来, 将arr[1]与最小值交换.
...
直到交换完成
void selectSort(int arr[], int n){
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(&arr[i], &arr[min]);
}
}
插入排序
插入排序的思路是，将单个数字插入有序集合. 大致思想是, 先将第一个数看做有序区, 后面的数依次插入, 形成新的有序区, 直到排序完成.
以升序为例, 比如这样一个数组 {4, 2, 7, 3}
第一轮, 第一个数字4看做有序区, 后面的数字插入. 开始比较2和4，发现2更小，继续向前查找，没有数字，因此将2插入4的位置，4向后移。这时数组变成了{2, 4, 7, 3}
第二次，遍历到7，向前比较, 有序
第三次，3和7比较，7更大，3应该插入前面。继续向前比较，比较到2才找到了合适的位置。将3插入4的位置，4、7向后移动一位。
下面开始撸代码
// 直接插入排序
void insertSort(int arr[], int n){
for (int i = 0; i < n; i++) {
// 后面的数比前面的数大时, 准备插入
if (arr[i] > arr[i+1]) {
// 存储待插入的数
int temp = arr[i+1];
int j;
// 向前查找合适的插入位置
for (j = i; j>=0 && temp < arr[j]; j--) {
// 逐步后移数组
arr[j+1] = arr[j];
}
// 交换
arr[j+1] = temp;
}
}
}
网友评论