目录
排序
稳定性
1. 插入
思想
实现
2、快排
快排
实现
hash表
应用
hash函数
设计的要点
常见hash函数设计
hash冲突
冲突的解决
实现
排序
使一个序列按照一定的次序(升序)进行排布。
稳定性
假如在一个序列中，有两个等值数据，记作 k[i], k[j]; 在排序前， i<j, (i,j 都是数组中的下标) 。排序后依然保持 k[i] 的存储位置在k[j]的前面，称为稳定的排序。否则 是不稳定的排序方式。
1. 插入
思想
插入 1. 把待插入元素，放入已有的序列当中 2. 把待插入元素，和有序序列中，最后一个数字进行比较， 3 如果 待插入元素大， 位置不需要变化的 4.反之，在有序序列中，比待插入元素都大数字，都整体后移。
实现
// arr，需要排序的数列 // len，数列的个数 void insert_order(int *arr, int len) { int i, j, k; // i指向待插入元素的下标 for (i = 1; i < len; i++) { // k存放待插元素本身 k = arr[i]; j = i – 1; //有序序列的最后一个元素 while (j >= 0 && arr[j] > k) { arr[j + 1] = arr[j]; j–;} arr[j + 1] = k; } }
2、快排
快排
分而治之 1.确定中枢(数组中第一个，假想中枢数字)， 2.拿中枢和最后面的比较， 中枢小，j– 。反之， a[i] = a[j] 3. 拿中枢和最前面的比较 中枢大， i++. 反之，a[j] = a[i] 4.i<j ,重复3,4步。反之,i == j ,a[i] = 中枢 5.递归 sort(a,0,i-1); 6.递归 sort(a,i+1,len);
实现
void quick_sort(int *arr, int left, int right) { int i, j, k; i = left; j = right; k = arr[i]; //假象的中间值。 while (i < j) // i == j { while (k <= arr[j] && i < j) j–; if (i < j) arr[i] = arr[j]; while (k >= arr[i] && i < j) i++; if (i < j) arr[j] = arr[i]; } arr[i] = k; if (left < i – 1) quick_sort(arr, left, i – 1); if (right > i + 1) quick_sort(arr, i + 1, right); }
hash表
一种既可以存储也可以查询的技术。
一般使用顺序表实现，需要支持随机访问数据。
应用
希望在大量数据中，快速o（1），o（logn）找到需要的数据。
存储位置=f(key)
存储位置就是数组中需要存储数据的地址。
f ，hash函数，根据需要存储内容可以计算出下标的函数
key，就是需要要存储的数据
hash函数
设计的要点
- 计算相对简单
- 地址分布均匀
常见hash函数设计
直接定值法
平方取中法
折叠法
求余法
hash冲突
f(key1) ==f(key2), key1!= key2 ; 需要存储的数据不同，但是调用了hash函数后，下标相同。 被称为hash函数冲突
冲突的解决
1、线性探测：尝试测试 =1,+2,+3,+4,+5……….+n n<数组的容量
2、二次探测：尝试测试+1，-1，+2，-2，+3，-3，+4，-4………=i^2 i^2<n 数组的容量
3、随机法：尝试测试 +rand（）%size
实现
typedef int DATATYPE; typedef struct { DATATYPE* head; int tlen; }HsTable; HsTable* CreateHsTable(int len) { HsTable* hs = malloc(sizeof(HsTable)); if(NULL == hs) { printf("CreateHsTable malloc1 error\\n"); return NULL; } hs->head = malloc(sizeof(DATATYPE)*len); if(NULL == hs->head) { printf("CreateHsTable malloc2 error\\n"); return NULL; } hs->tlen = len; for(int i = 0 ;i<len;i++) { hs->head[i]=-1; } return hs; } int HsFun(HsTable*hs,DATATYPE*data) { return *data%hs->tlen; } int HsTableInsert(HsTable*hs,DATATYPE*data) { int inx = HsFun(hs,data); while(hs->head[inx]!=-1) { printf("冲突 data:%d pos%d\\n",*data,inx); inx= (inx+ 1)%hs->tlen; } hs->head[inx] = *data; return 0; } int HsTableSearch(HsTable*hs,DATATYPE*data) { int inx = HsFun(hs, data); int old_inx = inx; while(hs->head[inx]!= *data) { inx= (inx+ 1)%hs->tlen; if(inx == old_inx) { return -1; } } return inx; } int main(int argc, char **argv) { HsTable* hs = CreateHsTable(10); int a[10]={31,22,75,34,12,11,44,67,90,3}; for(int i = 0 ;i<10;i++) { HsTableInsert(hs, &a[i]); } int want_num =75; int ret = HsTableSearch(hs, &want_num); if(-1 == ret) { printf("can't find\\n"); } else { printf("find it\\n"); } return 0; }
