本文共 8359 字，大约阅读时间需要 27 分钟。
1、完成快排，堆排，计数排序算法，对比不同算法排序1亿数的时间
#define _CRT_SECURE_NO_WARNINGS#include#include #include #include #define NUM 100000000#define M 100000000#define SWAP(A, B) {int tmp; tmp = A; A = B; B = tmp;}int find_pivot(int* arr, int left, int right);void quick_sort(int* arr, int left, int right);void adjust_heap_node(int* arr, int dad, int arrlen);void heap_sort(int* arr, int N);int find_pivot(int* arr, int left, int right){ int pivot = right; //以数组元素中最右端的元素作为基准 int insertvalue = arr[right]; int i = left, k = left, j; //i和k相当于数组中的双指针 for (j = left; j < right; j++) //遍历数组中的元素 { if (arr[k] <= insertvalue) { k++; i++; } else { if (arr[i] <= insertvalue) { SWAP(arr[k], arr[i]); k++; i++; continue; } i++; } } SWAP(arr[k], arr[right]); return k; //C语言在函数中可以返回一个局部变量嘛}void quick_sort(int* arr, int left, int right){ if (left < right) { int pivot = find_pivot(arr, left, right); quick_sort(arr, left, pivot - 1); quick_sort(arr, pivot + 1, right); }}void adjust_heap_node(int* arr, int dad, int arrlen){ int son = 2 * dad + 1; while (son < arrlen) { if (son + 1 < arrlen && arr[son] < arr[son + 1]) { son++; } else if (arr[dad] < arr[son]) { SWAP(arr[dad], arr[son]); dad = son; son = 2 * dad + 1; continue; } else { break; } } return;}void heap_sort(int* arr, int N){ for (int dad = N / 2 - 1; dad >= 0; dad--) { adjust_heap_node(arr, dad, N-1); } SWAP(arr[0], arr[N - 1]); for (int i = N - 2; i > 1; i--) { adjust_heap_node(arr, 0, i); SWAP(arr[0], arr[i - 1]); } return;}void count_sort(int* arr){ int i, j, k; int* count = (int*)calloc(1, M * sizeof(int)); //int count[M] = { 0 }; //memset(count, 0, sizeof(int)); for (i = 0; i < NUM; i++) { count[arr[i]]++; } k = 0; for (i = 0; i < M; i++) { for (j = 0; j < count[i]; j++) { //printf("%d ", j); arr[k++] = i; } } //printf("\n");}void arr_print(int* arr, int N){ for (int i = 0; i < N; i++) { printf("%3d", arr[i]); } printf("\n");}int main(){ int i; int* arr = (int*)malloc(NUM * sizeof(int)); time_t start, end; srand(time(NULL)); for (i = 0; i < NUM; i++) { arr[i] = rand() % M; } //arr_print(arr, NUM); //quick_sort(arr, 0, NUM - 1); //heap_sort(arr, NUM); //arr_print(arr, NUM); start = time(NULL); //heap_sort(arr, NUM); count_sort(arr); //arr_print(arr, NUM); end = time(NULL); printf("use time = %d\n", end - start); system("pause"); return 0;}
2、使用qsort对一个链表进行排序
#define _CRT_SECURE_NO_WARNINGS#define N 100#include#include typedef struct Node{ int data; struct Node* pnext;}Node_t, *pNode_t;int compare(const void* p1, const void* p2) //一级指针强转成二级指针{ pNode_t* pNode1 = (pNode_t*)p1; pNode_t* pNode2 = (pNode_t*)p2; return (*pNode1)->data - (*pNode2)->data;}void ListPrint(pNode_t phead){ if (NULL == phead) { return; } while (phead) { printf("%d ", phead->data); phead = phead->pnext; } printf("\n");}int main(){ pNode_t arr[N]; int value; int cnt = 0; pNode_t phead = NULL; pNode_t ptail = NULL; while (scanf("%d", &value) != EOF) { pNode_t pnew = (pNode_t)calloc(1, sizeof(Node_t)); pnew->data = value; if (NULL == phead) { phead = pnew; ptail = pnew; } else { ptail->pnext = pnew; ptail = pnew; } cnt++; } ListPrint(phead); for (int i = 0; i < cnt; i++) { arr[i] = phead; phead = phead->pnext; } qsort(arr, cnt, sizeof(pNode_t), compare); for (int i = 0; i < cnt; i++) { printf("%d ", arr[i]->data); } printf("\n"); return 0;
3、使用哈希函数，将20个不同姓名的同学的插入数组，并且输入一个姓名，判断该姓名是否是已知的姓名
#define _CRT_SECURE_NO_WARNINGS#include#include #include #define MAXKEY 1000#define N 10int hash(char* key){ int h = 0, g; while (*key) { h = (h << 4) + *key++; g = h & 0xf0000000; if (g) h ^= g >> 24; h &= ~g; } return h % MAXKEY;}int main(){ char* pStr[N]; char name[N][20] = { 0 }; char str[20] = { 0 }; char* hashTable[MAXKEY] = { NULL }; for (int i = 0; i < N; i++) { fgets(name[i], 20, stdin); if (name[i][strlen(name[i]) - 1] == '\n') { name[i][strlen(name[i]) - 1] = '\0'; } pStr[i] = name[i]; } for (int i = 0; i < N; i++) { printf("%5s hashValue=%d\n", pStr[i], hash(pStr[i])); hashTable[hash(pStr[i])] = pStr[i]; } printf("need to find name:\n"); while (gets(str) != NULL) { if (hashTable[hash(str)] == NULL) { printf("It is not exist.\n"); } else { printf("It is in array number: %d\n", hash(str)); } printf("need to find name again:\n"); } system("pause");}
4、实现找第K大的数的单机查找和双机查找
//该段代码只实现了第K大的数的单机查找//我先实现了小顶堆对数组中前K个元素进行排序，从大到小，第k位即为现在的第k大//然后实现了将k-N-1个元素和第k个元素进行对比，若大于第k个元素，则替换掉第k个元素，再对//前K个数组元素建立最小堆并进行调整，最后结果输出arr[k-1]#define _CRT_SECURE_NO_WARNINGS#include#include #include #include #define NUM 10#define M 100#define SWAP(A, B) {int tmp; tmp = A; A = B; B = tmp;}void adjust_heap_node(int* arr, int dad, int arrlen);void heap_sort(int* arr, int k);void adjust_heap_node(int* arr, int dad, int arrlen){ int son = 2 * dad + 1; while (son < arrlen) { if (son + 1 < arrlen && arr[son] > arr[son + 1]) { son++; } else if (arr[dad] > arr[son]) { SWAP(arr[dad], arr[son]); dad = son; son = 2 * dad + 1; continue; } else { break; } } return;}void heap_sort(int* arr, int k){ for (int dad = k / 2 - 1; dad >= 0; dad--) { adjust_heap_node(arr, dad, k); } SWAP(arr[0], arr[k - 1]); for (int i = k - 1; i > 1; i--) { adjust_heap_node(arr, 0, i); SWAP(arr[0], arr[i-1]); } return;}void arr_print(int* arr, int N){ for (int i = 0; i < N; i++) { printf("%3d", arr[i]); } printf("\n");}int main(){ int i; int k; int* arr = (int*)malloc(NUM * sizeof(int)); time_t start, end; srand(time(NULL)); for (i = 0; i < NUM; i++) { arr[i] = rand() % M; } arr_print(arr, NUM); printf("please input the kth big number:\n"); scanf("%d", &k); //quick_sort(arr, 0, NUM - 1); //heap_sort(arr, NUM); //arr_print(arr, NUM); start = time(NULL); heap_sort(arr,k); for (int i = k; i < NUM; i++) { if (arr[i] > arr[k - 1]) { SWAP(arr[i], arr[k - 1]); heap_sort(arr, k); } } arr_print(arr, NUM); printf("the kth big number: %d\n", arr[k - 1]); end = time(NULL); printf("use time = %d\n", end - start); system("pause"); return 0;
#include#include #include #include #define N 1000#define SWAP(a,b) {int tmp = a; a = b; b = tmp;}int singleFind(int* arr, int k);int doubleFind(int* arr1, int* arr2, int k);void adjust_heap_node(int* arr, int dad, int arrlen);int compare(const void* p1, const void* p2){ return *(int*)p2 - *(int*)p1;}int main(){ int arr1[N] = { 0 }; int arr2[N] = { 0 }; int arr3[N] = { 0 }; srand(time(NULL)); for (int i = 0; i < N; ++i) { arr1[i] = rand() % N; arr2[i] = arr1[i]; arr3[i] = arr1[i]; } qsort(arr1, N, sizeof(int), compare); int res1 = singleFind(arr2, 10); int* p1 = arr3; int* p2 = arr3 + N / 2; qsort(p1, N / 2, sizeof(int), compare); qsort(p2, N - N / 2, sizeof(int), compare); int res2 = doubleFind(p1, p2, 10); return 0;}void adjust_heap_node(int* arr, int dad, int arrlen){ int son = 2 * dad + 1; while (son < arrlen) { if (son + 1 < arrlen && arr[son] > arr[son + 1]) { son++; } else if (arr[dad] > arr[son]) { SWAP(arr[dad], arr[son]); dad = son; son = 2 * dad + 1; continue; } else { break; } }}int singleFind(int* arr, int k) { //所有数据的下标范围0~N-1 //所有堆元素的下标范围0~k-1 //对前k个数字建堆 for (int dad = (k - 2) / 2; dad >= 0; --dad) { adjust_heap_node(arr, dad, k); } //剩余的元素，比较、取代，然后重建堆 for (int i = k; i < N; ++i) { if (arr[0] < arr[i]) { arr[0] = arr[i]; adjust_heap_node(arr, 0, k); } } return arr[0];}int doubleFind(int* arr1, int* arr2, int k){ if (k == 1) { return arr1[0] > arr2[0] ? arr1[0] : arr2[0]; } else { int num = k / 2; //要查找的数量 if (arr1[num - 1] > arr2[num - 1]) { return doubleFind(arr1 + num, arr2, k - num); } else if (arr1[num - 1] < arr2[num - 1]) { return doubleFind(arr1, arr2 + num, k - num); } else { if (k % 2 == 0) { return arr1[num - 1]; } else { return doubleFind(arr1 + num, arr2 + num, 1); } } }}
转载地址：http://txxmb.baihongyu.com/