Excel能永久关闭科学计数吗(如何取消excel里的科学计数)
514
2022-05-29
排序
常见的排序算法
常见排序算法的实现
归并排序
基本思想
递归写法
通过调试看一下现象
归并顺序
排序
常见的排序算法
常见排序算法的实现
归并排序
基本思想
递归写法
通过调试看一下现象
归并顺序
归并排序递归子函数
归并排序递归实现
非递归写法
2^n^个元素的数组
随便几个元素的数组
修正下标
归并排序非递归实现 修正下标
归一部分拷一部分
归并排序非递归实现 归一部分拷一部分
归并排序的特性总结
时间复杂度
测性能
1000 一千
10000 一万 ==先抛弃选择和冒泡==
100000 十万 ==再抛弃直接插入==
1000000 一百万
10000000 一千万
代码
Sort.h
Sort.c
test.c
排序
常见的排序算法
常见排序算法的实现
归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:
实际上归并我们不是第一次接触,之前我们也是接触过的,比如合并两个有序数组这个就是归并思想
但是我们上面的题目是左区间有序,右区间也有序。我们正常题目肯定不会直接给你有序。这时候再深一点,你不是没有序吗,那我们再分,分到你无法再分,==也就是只有一个了,你能说一个没有序吗,肯定不行==,所以我们继续分治。
看上面的GIF也知道第一反应是递归
// 归并排序递归子函数 void _MergeSort(int* a, int left, int right, int* tmp){ //左大于右说明是空数组,空数组就跳 //左等于右就是我们要的单体有序 if (left >= right) return; //防溢出写法 int mid = left + (right - left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1,right, tmp); // int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int i = left; //跑空一组就直接跳 while (begin1<=end1 && begin2<=end2){ if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //把tmp数组拷贝回到原来的数组中 i = left; while (i<=right) { a[i] = tmp[i]; i++; } }
// 归并排序递归实现 void MergeSort(int* a, int n) { assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); //子函数 _MergeSort(a, 0, n - 1, tmp); //不用了就free掉 free(tmp); //然后置空 tmp = NULL; }
我们看到上面好像没啥问题,那是用为数组元素个数真的太有好了,一直没有落单的元素,好的不真实
越界情况讨论
但是出现另一种恶心情况 ==重复拷贝==
所以接下来我们需要解决index问题
我们修正到n-1,同样也可以把数组修不存在,让他不进下面的循环也就可以不会进行归并
// 归并排序非递归实现 void MergeSortNonR(int* a, int n) { assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); int gap = 1; int i = 0; while (gap
我们也可以像递归那样归一半分拷贝一部分,就不需要修正了,因为修正要考虑很多边界情况,有点繁琐
// 归并排序非递归实现 void MergeSortNonR(int* a, int n) { assert(a); //首先创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); //空就直接错 assert(tmp); int gap = 1; int i = 0; while (gap
归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度:O(N*logN)
空间复杂度:O(N)
稳定性:稳定
时间复杂度:O(N*logN)
归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。
==归并排序总时间=分解时间+子序列排好序时间+合并时间==
无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计。
==则:归并排序总时间=子序列排好序时间+合并时间==
测性能
代码
#pragma once #include
#define _CRT_SECURE_NO_WARNINGS 1 #include "Sort.h" #include"Stack.h" // 打印数组 void PrintArray(int* a, int n) { assert(a); int i = 0; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } // 插入排序 void InsertSort(int* a, int n) { assert(a); int i = 0; for (i = 0; i < n - 1; i++) { int end = i; int x = a[end+1]; while (end >= 0) { //要插入的数比顺序中的数小就准备挪位置 if (a[end] > x) { a[end + 1] = a[end]; end--; } else { //插入的数比顺序中的要大就跳出 break; } } //跳出来两种情况 //1.end == -1 的时候 //2.break 的时候 //把x给end前面一位 a[end + 1] = x; } } // 希尔排序 void ShellSort(int* a, int n) { //分组 int gap = n; //多次预排序(gap>1)+ 直接插入(gap == 1) while (gap>1){ //gap /= 2; //除以三我们知道不一定会过1,所以我们+1让他有一个必过1的条件 gap = gap / 3 + 1; //单组多躺 int i = 0; for (i = 0; i < n - gap; i++) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; //步长是gap end -= gap; } else { break; } } a[end + gap] = x; } } } //数据交换 void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } // 选择排序 void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end){ //单趟 //最大数,最小数的下标 int mini = begin;//这边假设是刚开始的下标 int maxi = end; //这边假设是末尾的下标 int i = 0; for (i = begin; i <= end; i++) { if (a[i] < a[mini]) mini = i; if (a[i] > a[maxi]) maxi = i; } //最小的放前面 Swap(&a[begin], &a[mini]); if (begin == maxi) //如果最大数就是begin位置的,那么交换的时候最大数连带着下标一起动 maxi = mini; //最大的放后面 Swap(&a[end], &a[maxi]); begin++; end--; } } //向下调整函数 void AdjustDown(int* a, int n, int parent) { assert(a); //创建一个孩子变量,有两个孩子就在这个上加1就行 int child = parent * 2 + 1; #if HEAP while (child < n) { //选大孩子 if (child + 1 < n && a[child] < a[child + 1]) { child++; } //大的孩子还大于父亲就交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } #elif !HEAP while (child < n) { //选小孩子 if (child + 1 < n && a[child] > a[child + 1]) { child++; } //小的孩子还小于父亲就交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } #endif // HEAP } // 堆排序 我们之前讲过升序建大堆 void HeapSort(int* a, int n) { //建堆时间复杂度O(N) //建大堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; //堆排序时间复杂度O(N*logN) while (end>0){ //交换 把最大的放到后面 Swap(&a[0], &a[end]); //在向下调整 AdjustDown(a,end,0); end--; } } // 冒泡排序 void BubbleSort(int* a, int n) { //多躺 int j = 0; for (j = 0; j < n - 1; j++) { //交换标记变量 int flag = 0; //单趟 int i = 0; for (i = 0; i < n - 1-j; i++) { if (a[i] > a[i + 1]) { //交换标记改变 flag = 1; Swap(&a[i], &a[i + 1]); } } //标记还是0就跳出 if (!flag) break; } } //三数取中 int GetMinIndex(int* a, int left, int right) { //这样可以防止 int 溢出 int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; } else //a[left] >= a[mid] { if (a[mid] > a[right]) return mid; else if (a[left] < a[right]) return left; else return right; } } // 快速排序hoare版本 单趟排序 //最左边做key [left,right] 我们这里给区间 int PartSort1(int* a, int left, int right) { //三数取中 int mini = GetMinIndex(a, left, right); //把中间的数放到最左边,交换即可 Swap(&a[mini], &a[left]); //还是最左边为keyi int keyi = left; //左右相遇就停止 while (left < right) { //最左边为key,那么最右边就先动 //找小于key的 while (left < right && a[right] >= a[keyi]) { right--; } //然后再动右边的 //找大于key的 while (left < right && a[left] <= a[keyi]) { left++; } Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[right]); //返回正确位置后的keyi return left; } // 快速排序挖坑法 int PartSort2(int* a, int left, int right) { assert(a); //三数取中 int mini = GetMinIndex(a, left, right); //把中间的数放到最左边,交换即可 Swap(&a[mini], &a[left]); //先把Key存下来 int Key = a[left]; //挖坑 int pit = left; while (left
#define _CRT_SECURE_NO_WARNINGS 1 #include "Sort.h" // 测试排序的性能对比 void TestOP() { //设置随机起点 srand(time(NULL)); //将要创建的数组大小 const int N = 10000000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); int* a9 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { //保证两个数组是一样的 a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; a9[i] = a1[i]; } int begin1 = clock();//开始时间 //InsertSort(a1, N); int end1 = clock(); //结束时间 int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); //SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); //BubbleSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSort(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); QuickSortNonR(a7, 0, N - 1); int end7 = clock(); int begin8 = clock(); MergeSort(a8, N); int end8 = clock(); int begin9 = clock(); MergeSort(a9, N); int end9 = clock(); printf("InsertSort:%d\n", end1 - begin1);//结束时间减去开始时间 printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end5 - begin5); printf("QuickSort:%d\n", end6 - begin6); printf("QuickSortNonR:%d\n", end7 - begin7); printf("MergeSort:%d\n", end8 - begin8); printf("MergeSortNonR:%d\n", end9 - begin9); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); free(a9); } //测试插入排序 void TestInsertSort() { int a[] = { 1,5,3,7,0,9 }; InsertSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试希尔排序 void TestShellSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; ShellSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试选择排序 void TestSelectSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; SelectSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试堆排序 void TestHeapSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; HeapSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试冒泡排序 void TestBubbleSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; BubbleSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试单趟排序 void TestPartSort1() { int a[] = { 5,5,5,5,5,5,5,5,5,5 }; PartSort1(a,0 ,sizeof(a) / sizeof(a[0])-1); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试快速排序 void TestQuickSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试快速排序--非递归 void TestQuickSortNonR() { int a[] = { 9,1,2,5,7,4,8,6,3,5 }; QuickSortNonR(a, 0, sizeof(a) / sizeof(a[0]) - 1); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试归并排序--递归 void TestMergeSort() { int a[] = { 10,6,7,1,3,9,4,2 }; MergeSort(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } //测试归并排序--非递归 void TestMergeSortNonR() { int a[] = { 10,6,7,1,3,9,4,2,5 }; MergeSortNonR(a, sizeof(a) / sizeof(a[0])); PrintArray(a, sizeof(a) / sizeof(a[0])); } int main(){ //TestInsertSort(); //TestShellSort(); //TestSelectSort(); //TestHeapSort(); //TestBubbleSort(); //TestPartSort1(); //TestQuickSort(); //TestQuickSortNonR(); //TestMergeSort(); //TestMergeSortNonR(); TestOP(); return 0; }
数据结构
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。