二级网站的建设方案,百度商家版下载,果洛州商城网站建设,网站开发工程师公司排序 #xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。 稳定性 #xff1a;假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录#xff0c;若经过排序#xff0c;… 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 #pragma once #include stdio.h #include assert.h #include stdlib.h #include time.h #include string.h #include memory.h //打印 void PrintArray(int* a, int n); // 排序实现的接口 // 插入排序 void InsertSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 选择排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n); // 快速排序递归实现 // 快速排序hoare版本 int PartSort1(int* a, int begin, int end); //三数取中 int GetMidindex(int* a, int begin, int end); // 快速排序挖坑法 int PartSort2(int* a, int begin, int end); // 快速排序前后指针法 int PartSort3(int* a, int begin, int end); void QuickSort(int* a, int left, int right); // 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right); // 归并排序递归实现 void MergeSort(int* a, int n); // 归并排序非递归实现 void MergeSortNonR(int* a, int n); // 计数排序 void CountSort(int* a, int n); #define _CRT_SECURE_NO_WARNINGS 1 #include Sort.h #include Stack.h //打印 void PrintArray(int* a, int n) { int i 0; for (i 0; i n; i) { printf(%d , a[i]); } printf(\n); } //插入排序 O(N^2) void InsertSort(int* a, int n) { assert(a); int i 0; for (i 0; i n - 1; i) { int end i; int tmp a[end 1]; //将end1的数据插入到[0,end]有序数组中 while (end 0) { if (tmp a[end]) { a[end 1] a[end]; end--; } else { break; } } a[end 1] tmp; } } // 希尔排序 O(N^1.3 N^2) void ShellSort(int* a, int n) { assert(a); //1. gap 1 相当于预排序让数组接近有序 //2. gap1就相当于直接插入排序保证有序 int gap n; while (gap 1) { gap gap / 3 1;//1是保证最后一次排序gap等于1 //gap1最后一次就相当于直接插入排序 int i 0; for (i 0; i n - gap; i) { int end i; int tmp a[end gap]; while (end 0) { if (tmp a[end]) { a[end gap] a[end]; end end - gap; } else { break; } } a[end gap] tmp; } //PrintArray(a, n); } } void Swap(int* p1, int* p2) { int tmp *p1; *p1 *p2; *p2 tmp; } // 选择排序 // O(N^2) void SelectSort(int* a, int n) { assert(a); int begin 0; int end n - 1; while (begin end) { int maxi begin; int mini begin; int i 0; for (i begin 1; i end; i) { if (a[i] a[maxi]) { maxi i; } if (a[i] a[mini]) { mini i; } } Swap(a[mini], a[begin]); //maxi和begin的位置重叠,maxi的位置需要修正 if (maxi begin)//max被换走了 { maxi mini;//找到max } Swap(a[maxi], a[end]); begin; end--; } } // 堆排序 void AdjustDwon(int* a, int n, int root) { int parent root; int child parent * 2 1; while (child n) { //选出较大的孩子 if (a[child 1] a[child] child 1 n) { child; } if (a[child] a[parent]) { Swap(a[parent], a[child]); parent child; child parent * 2 1; } else { break; } } } void HeapSort(int* a, int n) { //排升序建大堆还是小堆 int i 0; for (i (n - 1 - 1) / 2; i 0 ; i--) { AdjustDwon(a, n, i); } int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDwon(a, end, 0); --end; } } // 冒泡排序 O(N^2) void BubbleSort(int* a, int n) { int flag 1; int i 0; for (i 0; i n; i) { int j 0; for (j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { Swap(a[j], a[j 1]); flag 0; } } //如果一趟冒泡排序过程中没有发生交换则已经有序不需要再进行冒泡排序 if (flag 1) { break; } } } //三数取中 int GetMidindex(int* a, int begin, int end) { int mid (begin end) / 2 ; if (a[begin] a[mid]) { if (a[mid] a[end]) { return mid; } else if (a[begin] a[end]) { return begin; } else { return end; } } else//a[begin] a[mid] { if (a[mid] a[end]) { return mid; } else if (a[begin] a[end]) { return begin; } else { return end; } } } //左右指针法 int PartSort1(int* a, int begin, int end) { int mid GetMidindex(a, begin, end); Swap(a[mid], a[end]); int keyindex end;//右边做key while (begin end) { //左边先走,//left right防止在的时候超出而错过相遇 while (begin end a[begin] a[keyindex])//左边找比key大, { begin; } //右边找比key小 while (begin end a[end] a[keyindex]) { end--; } //交换left和right位置的值 Swap(a[begin], a[end]); } //交换key和相遇位置的值 Swap(a[begin], a[keyindex]); return begin; } // 快速排序挖坑法 int PartSort2(int* a, int begin, int end) { int mid GetMidindex(a, begin, end); Swap(a[mid], a[end]); //坑 int key a[end]; while (begin end) { //左边找比key大的 while (begin end a[begin] key) { begin; } //将找到的数填在end位置然后形成新的坑 a[end] a[begin]; //右边找比key小的数 while (begin end a[end] key) { end--; } //将找到的数填在begin的位置然后形成新的坑 a[begin] a[end]; } //begin和end相遇循环结束将key的值填入begin的位置 a[begin] key; return begin; } // 快速排序前后指针法 int PartSort3(int* a, int begin, int end) { int mid GetMidindex(a, begin, end); Swap(a[mid], a[end]); int key a[end]; int keyindex end; int cur begin; int prev begin - 1;; while (cur end) { while (a[cur] a[keyindex] prev ! cur) { Swap(a[cur], a[prev]); } cur; } Swap(a[prev], a[keyindex]); return prev; } //时间复杂度O(N*log N) //空间复杂度 O(log N) void QuickSort(int* a, int left, int right) { assert(a); //[left,div-1] , [div1,right] if (left right) return; if ((right - left 1) 10) { //int div PartSort1(a, left, right); //int div PartSort2(a, left, right); int div PartSort3(a, left, right); //PrintArray(aleft, right-left1); //printf([%d %d] %d [%d %d], left, div - 1, div, div 1, right); //printf(\n); QuickSort(a, left, div - 1); QuickSort(a, div 1, right); } else { //小于等于10个数直接选插入排序,不在递归排序 InsertSort(a left, right - left 1); } } // 快速排序 非递归实现 //递归改非递归 //--1.改循环斐波拉契数列求解一些简单递归才能改循环 //--2.栈模拟存储数据非递归 //非递归1.提高效率递归建立栈还是有消耗的但是对于现代的计算机这个优化微乎其微可以忽略不计 // 2.递归的最大缺陷是如果栈的深度太深可能会导致栈溢出因为系统栈空间一般不大在M级别 // 数据结构模拟非递归数据是存储在堆上的堆是G级别的空间 void QuickSortNonR(int* a, int left, int right) { assert(a); //栈来实现快速排序 Stack st;//定义栈 StackInit(st); //先入右边在入左边 StackPush(st, right); StackPush(st, left); while (!StackEmpty(st)) { int begin StackTop(st);//左边 StackPop(st);//先出一个 int end StackTop(st); StackPop(st); int div PartSort1(a, begin, end); //先处理左边 if (begin div - 1)//左边至少有两个数据 { StackPush(st, div - 1); StackPush(st, begin); } //处理右边 if (end div 1)//至少有两个数据 { StackPush(st, end); StackPush(st, div 1); } } //销毁栈防止内存泄漏 StackDestory(st); } void _MergeArray(int* a, int begin1, int end1, int begin2, int end2, int* tmp) { //递归完了得到两个有序数组 //归并 int left begin1; int rightend2; int index begin1; while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[index] a[begin1]; index; begin1; } else { tmp[index] a[begin2]; index; begin2; } } //应该还有一个数组还有剩余元素 while (begin1 end1) { tmp[index] a[begin1]; } while (begin2 end2) { tmp[index] a[begin2]; } //把归并好的在tmp数组的元素拷贝回原来数组a int i 0; for (i left; i right; i) { a[i] tmp[i]; } } void _MergeSort(int* a, int left, int right, int* tmp) { //递归截止条件 if (left right) { return; } //先递归 int mid (left right) / 2; //[left,mid],[mid1,right] _MergeSort(a, left, mid, tmp); _MergeSort(a, mid 1, right, tmp); _MergeArray(a, left, mid, mid 1, right, tmp); } // 归并排序递归实现 //时间复杂度 O(N*logN) //空间复杂度 O(N) void MergeSort(int* a, int n) { assert(a); int* tmp (int*)malloc(sizeof(int) * n); if (tmp NULL) { printf(申请内存失败\n); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp);//释放内存防止内存泄漏 } // 归并排序非递归实现 void MergeSortNonR(int* a, int n) { assert(a); int* tmp (int*)malloc(sizeof(int) * n); int gap 1; while (gap n) { int i 0; for (i 0; i n; i i 2 * gap) { //使用闭区间 //[i,igap-1],[igap,i2*gap-1] int begin1 i; int end1 i gap - 1; int begin2 i gap; int end2 i 2 * gap - 1; //1、合并时只有第一组第二组不需要合并 if (begin2 n) { break; } //2、合并时第二组只有部分数据需要修改边界值 if (end2 n) { end2 n - 1; } _MergeArray(a, begin1, end1, begin2, end2, tmp); } gap gap * 2; PrintArray(a, n); } } //计数排序 //时间复杂度O(Nrange) //空间复杂度O(range) //只适用于整型浮点型和字符串还是需要使用比较排序 void CountSort(int* a, int n) { assert(a); //找出最大值和最小值 int min a[0]; int max a[0]; for (int i 0; i n; i) { if (a[i] max) { max a[i]; } if (a[i] min) { min a[i]; } } int range max - min 1; //开辟一个数组 int* countArray (int*)malloc(sizeof(int) * range); //设置为0 memset(countArray, 0, sizeof(int) * range); //统计次数 for (int i 0; i n ; i) { countArray[a[i] - min]; } //排序 int index 0; for (int j 0; j range; j) { while (countArray[j]--) { a[index] j min; } } free(countArray); } #define _CRT_SECURE_NO_WARNINGS 1 #include Sort.h #include Stack.h void TestInsertSort() { int a[] { 2,1,4,3,9,6,4,0,5,8 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); InsertSort(a, sz); PrintArray(a, sz); } TestShellSort() { int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); ShellSort(a, sz); PrintArray(a, sz); } void TestSelectSort() { int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); SelectSort(a, sz); PrintArray(a, sz); } void TestHeapSort() { int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); HeapSort(a, sz); PrintArray(a, sz); } void TestBubbleSort() { int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); BubbleSort(a, sz); PrintArray(a, sz); } void TestQuickSort() { //int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int a[] { 2,1,4,3,9,6,4,0,5,8 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); QuickSort(a, 0,sz-1); PrintArray(a, sz); } void TestQuickSortNonR() { //int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int a[] { 2,1,4,3,9,6,4,0,5,8 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); QuickSortNonR(a, 0, sz - 1); PrintArray(a, sz); } void TestMergeSort() { //int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int a[] { 10,6,7,1,3,9,4,2 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); MergeSort(a, sz);//不是sz-1如果是sz-1,会导致最后一个元素没有排到 PrintArray(a, sz); } void TestMergeSortNonR() { //int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int a[] { 10,6,7,1,3,9,4 }; int sz sizeof(a) / sizeof(a[0]); //PrintArray(a, sz); MergeSortNonR(a, sz);//不是sz-1如果是sz-1,会导致最后一个元素没有排到 //PrintArray(a, sz); } void TestCountSort() { //int a[] { 20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 }; int a[] { 10,6,7,1,3,9,4 }; int sz sizeof(a) / sizeof(a[0]); PrintArray(a, sz); CountSort(a, sz);//不是sz-1如果是sz-1,会导致最后一个元素没有排到 PrintArray(a, sz); } void TestOP() { srand(time(0)); const int N 100000; 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); 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]; } 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 end6 clock(); int begin7 clock(); QuickSort(a5, 0, N-1); int end8 clock(); int begin9 clock(); QuickSortNonR(a5, 0, N - 1); int end10 clock(); /*int begin5 clock(); QuickSort(a5, 0, N - 1); int end5 clock(); int begin6 clock(); MergeSort(a6, N); int end6 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, end6 - begin5); printf(QuickSort:%d\n, end8 - begin7); printf(QuickSortNonR:%d\n, end10 - begin9); /*printf(QuickSort:%d\n, end5 - begin5); printf(MergeSort:%d\n, end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6);*/ } int main() { //TestInsertSort(); //TestShellSort(); //TestSelectSort(); //TestHeapSort(); //TestBubbleSort(); //TestQuickSort(); //TestQuickSortNonR(); //TestMergeSort(); //TestMergeSortNonR(); //MergeSortFile(Sort.txt); TestCountSort(); //TestOP(); return 0; } #pragma once #include stdio.h #include stdlib.h #include assert.h //用数组来实现 //静态的数组 //#define N 10 //struct Stack //{ // int _a[N]; // int _top; //}; //动态的数组 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top;//栈顶下标 int _capacity; }Stack; //初始化 void StackInit(Stack* pst); //销毁 void StackDestory(Stack* pst); //入栈 void StackPush(Stack* pst, STDataType x); //出栈 void StackPop(Stack* pst); //获取数据个数 int StackSize(Stack* pst); //返回1是空返回0是非空 int StackEmpty(Stack* pst); //获取栈顶的数据 STDataType StackTop(Stack* pst); #define _CRT_SECURE_NO_WARNINGS 1 #include Stack.h //初始化 void StackInit(Stack* pst) { assert(pst); //pst-_a NULL; //pst-_top 0; //pst-_capacity 0; pst-_a (STDataType*)malloc(sizeof(STDataType) * 4); pst-_top 0; pst-_capacity 4; } //销毁 void StackDestory(Stack* pst) { assert(pst); free(pst-_a); pst-_a NULL; pst-_top 0; pst-_capacity 0; } //入栈 void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst-_top pst-_capacity)//满了需要增容 { pst-_capacity * 2; STDataType* tmp (STDataType*)realloc(pst-_a, pst-_capacity*sizeof(STDataType) ); if (tmp NULL)//增容失败 { printf(增容失败\n); exit(-1); } else//将tmp给pst-_a,指向它 { pst-_a tmp; } } pst-_a[pst-_top] x; pst-_top; } //出栈 void StackPop(Stack* pst) { assert(pst); assert(pst-_top 0); --pst-_top; } //获取数据个数 int StackSize(Stack* pst) { assert(pst); return pst-_top; } //返回1是空返回0是非空 int StackEmpty(Stack* pst) { assert(pst); return pst-_top 0 ? 1 : 0; } //获取栈顶的数据 STDataType StackTop(Stack* pst) { assert(pst); assert(pst-_top 0); return pst-_a[pst-_top - 1];//pst-_top是元素的个数 }
