常见排序算法 逃离我推掉我的手 2022-05-11 05:54 243阅读 0赞 ### 文章目录 ### * 排序 * * 排序概念 * 排序算法稳定性 * 常见排序算法 * * 插入排序 * 选择排序 * 交换排序 * 归并排序 # 排序 # ## 排序概念 ## 排序:就是将一组杂乱无章的数据按照一定规律(升序或者降序)组织起来。 排序码:通常数据元素有多个属性域,其中有一个属性域可用来区分元素,作为排序依据,该域即为排序码。 ## 排序算法稳定性 ## 如果在元素序列中有两个元素R\[i\]和R\[j\],他们的排序码相同,在排序之前R\[i\]在R\[j\]之前。如果排序之后R\[i\]在R\[j\]之前,则称这个排序算法是稳定的,否则这个排序算法不稳定。 **内部排序**:数据元素全部放在内存中的排序 **外部排序**:数据元素太多,不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 ## 常见排序算法 ## ### 插入排序 ### 基本思想:每一步将待排序的元素,按其排序码的大小,插入到已经排好序的一组元素的合适位置上去,直到元素插完为止。 * 直接插入排序 当插入第i个元素时,前面的元素已经排好序,此时用这个数依次往前比较,找到插入位置将该元素插入,原来位置上的元素顺序后移。 #void InsertSort(int*array,int size) { int i = 0; for(i=1;i<size;i++) { int k = array[i];//k为待插入元素 int end = i-1; //找插入位置 while(end >= 0 && k < array[end]) { array[end+1] = array[end];//搬移数据 end--; } array[end+1] = k; } } <table> <thead> <tr> <th>应用场景</th> <th>时间复杂度</th> <th>空间复杂度</th> </tr> </thead> <tbody> <tr> <td>1.接近有序;2.数据量小</td> <td>O(N<sup>2</sup>)</td> <td>O(1),稳定的排序算法</td> </tr> </tbody> </table> 优化 找位置——二分查找 搬数据 插数据 void BinarySearch_InsertSort(int* array,int size) { int i = 0; int j = 0; for(i=0;i<size;i++) { int left=0; int right=i-1; int temp=array[i]; while(right>=left) { int middle=left+(right-left)>>1; if(array[middle]>temp) right = middle-1; else left = middle+1; } //每次查找完,left总比right大1 //查找结果:最后,array[left]总比temp大 for(j=i-1;j>=left;j--) array[j+1]=array[j];//搬移数据 array[left]=temp;//插入数据 } return; } * 希尔排序 void ShellSort(int* array,int size) { int gap = 3; while(gap>=0) { int i = 0; for(i=gap;i<size;i++) { int k = array[i];//k为待插入元素 int end = i-gap; //找插入位置 while(end >= 0 && k < array[end]) { array[end+gap] = array[end];//搬移数据 end-= gap; } array[end+gap] = k; } gap--; } } <table> <thead> <tr> <th>应用场景</th> <th>稳定性</th> <th>时间复杂度</th> <th>空间复杂度</th> </tr> </thead> <tbody> <tr> <td>数据杂乱,数据量大</td> <td>不稳定</td> <td>与gap有关</td> <td>O(1)</td> </tr> </tbody> </table> ### 选择排序 ### * 选择排序 void SelectSort(int* array,int size) { int i = 0; for(i = 0;i<size-1;i++) { int j = 1; int maxpos = 0; for(;j<size-i;j++) { if(array[j]>array[maxpos]) maxpos = j; }//找最大元素下标 if(maxpos != size-i-1) Swap(&array[maxpos],&array[size-1-i]);//将最大元素放在区间最后 } } 优化 同时排序最大元素和最小元素 void SelectSort_OP(int* array,int size) { int begin = 0; int end = size-1; while(begin<end) { int minpos = begin; int maxpos = begin; int i = begin+1; //找最大及最小元素下标 while(i<=end) { if(array[i]>array[maxpos]) maxpos = i; if(array[i]<array[minpos]) minpos = i; ++i; } if(maxpos != end) Swap(&array[maxpos],&array[end]); if(minpos == end) minpos = maxpos;//最小元素有可能在end的位置,需要重新标记minpos if(minpos!= begin) Swap(&array[minpos],&array[begin]); begin++; end--; } } <table> <thead> <tr> <th>时间复杂度</th> <th>空间复杂度</th> <th>稳定性</th> <th>应用场景</th> </tr> </thead> <tbody> <tr> <td>O(n<sup>2</sup>)</td> <td>O(1)</td> <td>不稳定</td> <td>重复元素多</td> </tr> </tbody> </table> * 堆排序 void HeapAdjust(int* array,int size,int parent) { int child = (parent<<1)+1;//标记左孩子 while(child<size) { //找左右孩子中最大的 if(array[child] <array[child+1]) child+=1; //检测最大孩子是否比双亲大 if(child +1<size&&array[child]>array[parent]) { Swap(&array[child],&array[parent]); parent = child; child = (parent>>1)+1; } else return; } } void HeapSort(int* array,int size) { //1.建堆--升序:大堆 int end = size-1; int root = ((end-1)>>1); for(;root>=0;root--) { HeapAdjust(array,size,root); } //2.排序--删除 while(end>0) { Swap(&array[0],&array[end]); HeapAdjust(array,end,0); end--; } } <table> <thead> <tr> <th>时间复杂度</th> <th>空间复杂度</th> <th>稳定性</th> </tr> </thead> <tbody> <tr> <td>O(nlog<sub>2</sub>n)</td> <td>O(1)</td> <td>不稳定</td> </tr> </tbody> </table> ### 交换排序 ### * 冒泡排序 void BubbleSort(int* array,int size) { int i = 0; int j =0; for(i=0;i<size-1;i++) { int ischange = 0; for(j = 0;j<size-i-1;j++) { if(array[j]>array[j+1]) { ischange = 1; Swap(&array[j],&array[j+1]); } } if(!ischange) return; } } * 快速排序 基本思想:递归 任取待排序序列中的某元素作为基准值,按照排序码将待排序序列分割为两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程即可。 void QuickSort(int* array,int left,int right) { if(right-left > 1) { int boundary = Partion(array,left,right); //[left,right)找基准值来划分区间,最后返回基准值在区间中的位置 QuickSort(array,left,boundary); QuickSort(array,boundary,right); } } 找基准值并划分左右区间的方法: int Partion1(int *array,int left,int right) { //找基准值 int key = array[right-1];//[left,right) int begin = left; int end = right-1; while(begin<end) { //从左往右找比基准值大的元素 while(begin < end && array[begin]<= key) begin++; //从右往左找比基准值小的元素 while(begin < end && array[end]>=key) end--; if(begin<end) Swap(&array[begin],&array[end]); } if(begin != right-1) Swap(&array[begin],&array[right-1]); return begin; } //填坑法 int Partion2(int *array,int left,int right) { int key = array[right-1];//[left,right) int begin = left; int end = right-1; while(begin<end) { //从左往右找比基准值大的元素 while(begin < end && array[begin]<= key) begin++; if(begin<end) array[end] = array[begin]; //从右往左找比基准值小的元素 while(begin < end && array[end]>= key) end--; if(begin<end) { array[begin] = array[end]; begin++; } } array[begin] = key; return begin; } int Partion3(int *array,int left,int right) { int key = array[right-1];//[left,right) int cur = left; int prev = cur-1; while(cur<right) { if(array[cur]<key && ++prev != cur) Swap(&array[cur],&array[prev]); ++cur; } if(++prev != right-1) { Swap(&array[prev],&array[right-1]); } return prev; } 当代排序序列接近有序时,时间复杂度比较高,为了降低可以通过三数取中法: int GetMiddleIndex(int* array,int left,int right) { int mid = left+((right - left)>>1); if(array[left]<array[right]) { if(array[mid]<array[left]) return left; else if(array[mid]>array[right-1]) return right-1; else return mid; } else { if(array[mid] > array[left]) return left; else if(array[mid] < array[right-1]) return right-1; else return mid; } } <table> <thead> <tr> <th>时间复杂度</th> <th>空间复杂度</th> <th>应用场景</th> </tr> </thead> <tbody> <tr> <td>O(n*log<sub>2</sub>n)</td> <td>O(log<sub>2</sub>n)</td> <td>数据越随机</td> </tr> </tbody> </table> 循环做法 void QuickSortNor(int* array,int size) { int left = 0; int right = size; Stack s; StackInit(&s); StackPush(&s,size); StackPush(&s,0); while(!StackEmpty(&s)) { left = StackTop(&s); StackPop(&s); right = StackTop(&s); StackPop(&s); if(left < right) { int boundary = Partion3(array,left,right); //排左边--》将右半部分区间压栈 StackPush(&s,right); StackPush(&s,boundary+1); //排右边--》将左半部分区间压栈 StackPush(&s,boundary); StackPush(&s,left); } } } ### 归并排序 ### void MergeData(int* array,int left,int mid,int right,int* tmp) { int begin1 = left; int end1 = mid; int begin2 = mid; int end2 = right; int index = left; while(begin1<end1 && begin2<end2) { if(array[begin1] <= array[begin2]) tmp[index++] = array[begin1++]; else tmp[index++] = array[begin2++]; } while(begin1 < end1) tmp[index++] = array[begin1++]; while(begin2 < end2) tmp[index++] = array[begin2++]; } void _MergeSort(int* array, int left,int right,int* tmp) { if(right-left>1) { int mid = left+((right-left)>>1); _MergeSort(array,left,mid,tmp); _MergeSort(array,mid,right,tmp); MergeData(array,left,mid,right,tmp); memcpy(array+left,tmp+left,(right-left)*sizeof(int)); } } void MergeSort(int* array,int size) { int* tmp = (int*)malloc(sizeof(int)*size) if(NULL == tmp) { assert(0); return; } _MergeSort(array,0,size,tmp); free(tmp); }
相关 [排序算法] 常见的排序算法 前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序 前言 在实际需求中,我们可能要 雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 184 阅读
相关 算法(一)常见排序 算法-常见排序 这里写目录标题 算法-常见排序 一. 常见排序列表 二. 参考下马老师的快速排序记忆法 三. 排序 àì夳堔傛蜴生んèń/ 2022年11月14日 13:14/ 0 赞/ 103 阅读
相关 常见排序算法总结 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常 我会带着你远行/ 2022年08月23日 14:58/ 0 赞/ 143 阅读
相关 常见排序算法 注:点进链接查看算法具体实现!!! -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 156 阅读
相关 常见排序算法 常见排序: ![这里写图片描述][SouthEast] 1、直接插入排序 在给定数组中,拿出一个数M,与前面的数相比较,如果M大于前面的数,位置不变,如果小于前面的 迷南。/ 2022年06月05日 05:51/ 0 赞/ 195 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 225 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 226 阅读
相关 常见排序算法 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。(即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 244 阅读
还没有评论,来说两句吧...