客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
排序操作在程序设计中是非常基础和常见的，也是算法的基础部分，我对几种常见的比较排序算法进行了整理。 选择排序思想：遍历数组，每次遍历都在未排序的部分找到最小元素的下标，在此次遍历结束后将最小元素放到遍历开始的位置。 性能：时间复杂度为O(n2)，算法比较次数与初始序列状态无关，性能在所有排序算法中最差。
void Violence_Sort(int* A, int len){ for(int i=0;i<len;i++) { int k = i; for(int j=i;j<len;j++) if(A[j]<A[k]) k = j; if(k != i){ int t = A[i]; A[i] = A[k]; A[k] = t; } } }
插入排序（insert sort）思想： 将当前元素与它前面已排好序的元素依次进行比较，最后放置在合适的位置，初始时可从第二个元素开始，认为第一个元素已排好序。 性能：算法时间复杂度为O(n2)，在序列规模较小时，性能比较好，且元素比较次数与初始序列杂乱程度相关，最优复杂度为O(n)。
void Insert_Sort(int* A, int len){ for(int i=1;i<len;i++) { int key = A[i]; int j = i - 1; while(j >= 0 && key < A[j]){ A[j+1] = A[j]; j--; } A[j+1] = key; } }
希尔排序（shell sort)思想：利用插入排序的思想，考虑到插入排序在序列基本有序且数量较少时性能较高，因此先对序列进行逻辑上的分组然后插入排序，如：设定初始增量为x，则0，0+x，0+x+x ...为一组，1，1+x，1+x+x ...为第二组，共有x组，分别进行排序。那个随后减少增量，增加分组，直到增量为1。 性能：算法时间复杂度为O(n1.3) -O(n2)，性能取决于增量序列。 void shellSort(int A[], int len){ for(int gap = len/2; gap > 0; gap /= 2){ for(int i = gap; i < len; i++){ int key = A[i]; int j; for(j = i-gap; j>=0 && A[j] > key; j-= gap) A[j+gap] = A[j]; A[j+gap] = key; } } }
冒泡排序（bubble sort）思想：从左往右遍历，比较相邻两个元素的大小，将大的一个放在后面，每遍历一趟，可找到一个最大值放置在最后，经过n-1趟遍历即可。 性能：时间复杂度为O(n2)，元素比较次数与初始状态无关，性能略低于插入排序。
void Bubble_Sort(int* A,int len){ for(int i=1;i<len;i++) for(int j=0;j<len-i;j++) { if(A[j]>A[j+1]){ int t = A[j+1]; A[j+1] = A[j]; A[j] = t; } } }
归并排序（merge sort)思想：使用分治思想，将原始序列分为两部分分别排序，然后合并，重点在于合并过程。 性能：时间复杂度为O(nlgn)，不过合并过程会使用额外的存储空间，占用内存。
void Merge(int A[], int low, int mid, int high){ int cp[high-low+1]; for(int i = low; i <= high; i++) cp[i-low] = A[i]; int l = low, r = mid+1; for(int i = low; i <= high; i++){ if(l > mid) {A[i] = cp[r - low]; r++;} else if(r > high) {A[i] = cp[l - low]; l++;} else if(cp[l-low] <= cp[r-low]) {A[i] = cp[l -low]; l++;} else {A[i] = cp[r -low]; r++;} } } void Merge_Sort(int A[], int low, int high){ if(high > low){ int mid = (low+high)/2; Merge_Sort(A, low, mid); Merge_Sort(A, mid+1, high); Merge(A, low, mid, high); } }
快速排序（quick sort)思想：与归并排序类似，也使用分治思想，选择一个元素值（一般选择最后一个元素），将比它小的放在左边部分，比它大的放在右边，然后对两部分分别进行上述操作知道递归结束，关键步骤在于元素的分类，且只占用O(1)的额外存储空间。 性能：时间复杂度为O(nlgn)，与归并排序不同，该算法占用常数级额外存储，在大规模序列排序应用中性能较好。
int patition(int* p, int left, int right){ int key = p[left]; while(left < right){ while(left<right && key <= p[right]) right--; if(left<right) p[left++] = p[right]; while(left<right && key >= p[left]) left++; if(left<right) p[right--] = p[left]; } p[left] = key; return left; } void quick_sort(int* p, int left, int right){ if(left >= right) return; int mid = patition(p, left, right); quick_sort(p, left, mid-1); quick_sort(p, mid+1, right); }
堆排序（heap sort）思想：使用堆数据结构进行排序，堆是一种用数组存储的二叉树，根据父节点和子节点的大小关系分为最大堆和最小堆，这里使用最大堆进行排序。 性能：时间复杂度为O(nlgn)，在实际使用中，堆排序的排序性能通常逊与快速排序。 void Max_Heapify(int* A, int i,int size){ int l = 2*i; int r = 2*i + 1; int large = i; if(l <= size && A[l] > A[i]) large = l; else large = i; if(r <= size && A[r] > A[large]) large = r; if(large != i){ int t = A[large]; A[large] = A[i]; A[i] = t; Max_Heapify(A, large, size); } } void Build_Max_Heap(int* A, int size){ for(int i=size/2;i>0;i--) Max_Heapify(A,i,size); } void Heap_Sort(int* A, int len){ Build_Max_Heap(A, len); while(len-1){ int t = A[1]; A[1] = A[i]; A[i] = t; len--; Max_Heapify(A,1,len); } }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论