基于C和C++的刷题代码设计源码

#define _CRT_SECURE_NO_WARNINGS 1 #include"Sort.h" #include "stack.h" void Print(int* pa, int n) { for (int i = 0; i < n; i++) { printf("%d ", pa[i]); } printf("\n"); } void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //插入排序 void InsertSort(int* pa, int n) { for (int i = 1; i < n; i++) { int end = i - 1; int tmp = pa[i]; while (end >= 0) { if (tmp < pa[end]) { pa[end + 1] = pa[end]; } else { break; } end--; } pa[end + 1] = tmp; } } //希尔排序 void ShellSort(int* pa, int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = 0; i < n - gap; i++) { int end = i; int tmp = pa[i + gap]; while (end >= 0) { if (tmp < pa[end]) { pa[end + gap] = pa[end]; } else { break; } end -= gap; } pa[end + gap] = tmp; } } } //选择排序 void SelectSort(int* pa, int n) { //第一种方法 /*for (int i = 0; i < n - 1; i++) { int min = i; int tmp = pa[i]; for (int j = i + 1; j < n; j++) { if (pa[j] < tmp) { tmp = pa[j]; min = j; } } Swap(&pa[i], &pa[min]); }*/ //优化之后的第二种方法 int lefti = 0, righti = n - 1; while (lefti < righti) { int mini = lefti, maxi = lefti; for (int i = lefti + 1; i <= righti; i++) { if (pa[i] < pa[mini]) { mini = i; } if (pa[i] > pa[maxi]) { maxi = i; } } Swap(&pa[mini], &pa[lefti]); if (lefti == maxi) { maxi = mini; } Swap(&pa[maxi], &pa[righti]); lefti++; righti--; } } //向下调整 - 建大堆 void Adjusedown(int* pa, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && pa[child + 1] > pa[child]) { child++; } if (pa[child] > pa[parent]) { Swap(&pa[child], &pa[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序 void HeapSort(int* pa, int n) { //建大堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { Adjusedown(pa, n, i); } int end = n - 1; while (end > 0) { Swap(&pa[0], &pa[end]); Adjusedown(pa, end, 0);//调整堆 end--; } } //冒泡排序 void BubbleSort(int* pa, int n) { for (int i = 0; i < n - 1; i++) { int falg = 0; for (int j = 1; j < n - i; j++) { if (pa[j - 1] > pa[j]) { falg = 1; Swap(&pa[j - 1], &pa[j]); } } if (falg == 0) { break; } } } //三数取中: 三个数比较大小取中间值 int GetMidNumi(int* pa, int lefti, int righti) { int midi = (lefti + righti) / 2; if (pa[lefti] < pa[midi]) { if (pa[midi] < pa[righti]) { return midi; } else if(pa[righti] > pa[lefti]) { return lefti; } else { return righti; } } else { if (pa[midi] > pa[righti]) { return midi; } else if(pa[righti] > pa[lefti]) { return lefti; } else { return righti; } } } //快速排序 //Hoare版本 void HoareQuickSort(int* pa, int lefti, int righti) { if (lefti >= righti) return; int begin = lefti, end = righti; //随机选keyi /*int randi = lefti + (rand() % (righti - lefti)); if (randi != lefti) Swap(&pa[lefti], &pa[randi]);*/ //三数取中 int midi = GetMidNumi(pa, lefti, righti); if (midi != lefti) Swap(&pa[midi], &pa[lefti]); int keyi = lefti; while (lefti < righti) { //找小 while (lefti < righti && pa[righti] >= pa[keyi]) righti--; //找大 while (lefti < righti && pa[lefti] <= pa[keyi]) lefti++; Swap(&pa[lefti], &pa[righti]); } Swap(&pa[keyi], &pa[lefti]); //小区间优化 if (end - begin + 1 > 10) { HoareQuickSort(pa, begin, lefti - 1); HoareQuickSort(pa, righti + 1, end); } else { InsertSort(pa + begin, end - begin + 1); } } //挖坑法 void HoleQuickSort(int* pa, int lefti, int righti) { if (lefti >= righti) return; int begin = lefti, end = righti; //三数取中 int midi = GetMidNumi(pa, lefti, righti); if (midi != lefti) Swap(&pa[midi], &pa[lefti]); int key = pa[lefti]; while (lefti < righti) { //找小 while (lefti < righti && pa[righti] >= key) righti--; pa[lefti] = pa[righti]; //找大 while (lefti < righti && pa[lefti] <= key) lefti++; pa[righti] = pa[lefti]; } pa[lefti] = key; //小区间优化 if (end - begin + 1 > 10) { HoareQuickSort(pa, begin, lefti - 1); HoareQuickSort(pa, righti + 1, end); } else { InsertSort(pa + begin, end - begin + 1); } } //前后指针法 void pointerQuickSort(int* pa, int lefti, int righti) { if (lefti >= righti) return; //三数取中 int midi = GetMidNumi(pa, lefti, righti); if (midi != lefti) Swap(&pa[midi], &pa[lefti]); int keyi = lefti; int prev = lefti; int cur = lefti + 1; while (cur <= righti) { if (pa[cur] < pa[keyi] && ++prev != cur) { Swap(&pa[cur], &pa[prev]); } cur++; } Swap(&pa[prev], &pa[keyi]); keyi = prev; //小区间优化 if (righti - lefti + 1 > 10) { pointerQuickSort(pa, lefti, keyi - 1); pointerQuickSort(pa, keyi + 1, righti); } else { InsertSort(pa + lefti, righti - lefti + 1); } } //非递归快排 void QuickSortNonR(int* pa, int lefti, int righti) { ST st; StackInit(&st); StackPush(&st, righti); StackPush(&st, lefti); while (!StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); //三数取中 int midi = GetMidNumi(pa, begin, end); if (midi != begin) Swap(&pa[midi], &pa[begin]); int keyi = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { if (pa[cur] < pa[keyi] && ++prev != cur) { Swap(&pa[cur], &pa[prev]); } cur++; } Swap(&pa[prev], &pa[keyi]); keyi = prev; if (keyi + 1 < end) { StackPush(&st, end); StackPush(&st, keyi + 1); } if (begin < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, begin); } } StackDestory(&st); } void _MergeSort(int* pa, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; _MergeSort(pa, begin, mid, tmp); _MergeSort(pa, mid + 1, end, tmp); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (pa[begin1] < pa[begin2]) { tmp[i++] = pa[begin1++]; } else { tmp[i++] = pa[begin2++]; } } while (begin1 <= end1) { tmp[i++] = pa[begin1++]; } while (begin2 <= end2) { tmp[i++] = pa[begin2++]; } memcpy(pa + begin, tmp + begin, sizeof(int) * (end - begin + 1)); } //归并排序 void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail\n"); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); } ////非递归归并排序 ////第一种写法 //void MergeSortNonR(int* pa, int n) //{ // int* tmp = (int*)malloc(sizeof(int) * n); // if (tmp == NULL) // { // perror("malloc fail\n"); // return; // } // // int gap = 1; // while (gap < n) // { // for (int i = 0; i < n; i += 2 * gap) // { // int begin1 = i, end1 = i + gap - 1; // int begin2 = i + gap, end2 = i + gap * 2 - 1; // int j = i; // // //修正下标 // if (end1 >= n) // { // end1 = n - 1; // begin2 = n; // end2 = n - 1; // } // if (begin2 >= n) // { // begin2 = n; // end2 = n - 1; // } // else if (end2 >= n) // { // end2 = n - 1; // } // // while (begin1 <= end1 && begin2 <= end2) // { // if (pa[begin1] < pa[begin2]) // { // tmp[j++] = pa[begin1++]; // } // else // { // tmp[j++] = pa[begin2++]; // } // } // // while (begin1 <= end1) // { // tmp[j++] = pa[begin1++]; // } // // while (begin2 <= end2) // { // tmp[j++] = pa[begin2++]; // } // } // memcpy(pa, tmp, sizeof(int) * n); // gap *= 2; // } // // free(tmp); //} //第二种写法 void MergeSortNonR(int* pa, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail\n"); return; } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + gap * 2 - 1; int j = i; if (end1 >= n || begi