php网站建设 关键技术,做网站哪家正规,外贸平台实训总结,dede后台网站主页排序算法分类
排序#xff1a;将一组对象按照某种逻辑顺序重新排列的过程。 按照待排序数据的规模分为#xff1a; 内部排序#xff1a;数据量不大#xff0c;全部存在内存中#xff1b;外部排序#xff1a;数据量很大#xff0c;无法一次性全部存在内存中#xff0c;…排序算法分类
排序将一组对象按照某种逻辑顺序重新排列的过程。 按照待排序数据的规模分为 内部排序数据量不大全部存在内存中外部排序数据量很大无法一次性全部存在内存中因此排序中需要访问外存。 按照排序是否稳定分为 稳定排序相等的元素在排序前后的相对位置不变。例如a等于b且原序列a在b前排序后a仍在b前则为稳定排序。不稳定排序相等元素在排序前后的相对位置可能发生变化。 按照是否需要额外内存分为 原地排序在排序过程中不申请多余的存储空间只利用原来存储待排数据的存储空间进行比较和交换的数据排序。非原地排序需要额外内存空间存储数组副本以辅助排序。 按照排序方式分为 比较类排序通过比较来决定元素间的相对次序。非比较类排序不通过元素间的比较进行排序。
比较类排序
冒泡排序
冒泡排序是一种典型的交换排序。
算法原理
比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。这一步结束后排在最后的元素会是所有数据中最大的数针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
冒泡排序基本代码如下
void BubbleSort(vectorint nums){const int size nums.size();for(int i 0; i size; i)for(int j 0; j size-i-1; j)if(nums[j] nums[j1])swap(nums[j], nums[j1]);
}性能评价
当nums[j] nums[j1]时我们并不交换它们。所以冒泡排序是稳定的;共循环了(n-1)(n-2)…21n(n-1)/2,所以时间复杂度是O(n^2)。
快速排序
快速排序是从冒泡排序演变而来的实际上是在冒泡排序基础上的递归分治法。 快速排序在每一轮挑选一个基准元素并让其他比它大的元素移动到数列一边比它小的元素移动到数列的另一边从而把数列拆解成了两个部分。
快排也用了分治策略其本质框架类似二叉树的前序遍历。
其实现代码如下
void QuickSort(std::vectorint nums, int left, int right){if(left right){return;}//治int i left;int j right;while(i j){while(i j nums[j] nums[left]) --j;while(i j nums[i] nums[left]) i;std::swap(nums[i], nums[j]);}std::swap(nums[i], nums[left]);//“分”QuickSort(nums, left, i - 1);QuickSort(nums, i 1, right);
}注意事项 如果选取数列的第一个元素为基准元素则从right所指向的元素开始与基准元素进行比较如果选取数列的最后一个元素为基准元素则从left所指向的元素开始与基准元素进行比较。如果选取数列的第一个元素为基准元素left所指向的元素与基准元素第一次对比时left下标与基准元素下标相等即判断条件中添加等号如果选取数列的最后一个元素为基准元素right所指向的元素与基准元素第一次对比时right下标与基准元素下标相等。 时间复杂度O(nlogn) 空间复杂度O(1) 稳定性不稳定
插入排序
基本思想将待排序数据看成由已排序和未排序两部分组成。对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
算法流程
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。
其实现代码如下
void InsertSort(vectorint nums){const int size nums.size();for(int i 1; i size; i){int curr nums[i];int j i - 1;while(j 0 curr nums[j]){nums[j1] nums[j];--j;}nums[j1] curr;}
}性能评价
插入排序是稳定的。时间复杂度为O(n^2)。
希尔排序
在插入排序中当需要插入的数是较小的数时后移的次数明显增多对效率有影响.
希尔排序是对插入排序的优化。它与插入排序的不同之处在于它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
其实现代码如下
void ShellSort(std::vectorint nums){const int size nums.size();for(int gap size / 2; gap 0; gap / 2){for(int i gap; i size; i){int curr nums[i];int j i - gap;while(j 0 curr nums[j]){nums[jgap] nums[j];j - gap;}nums[jgap] curr;}}
}选择排序
基本思想首先在未排序数据找到最小的数然后把该最小数放到排序序列的末尾直到所有数据排序完毕。
其实现代码如下
void SelectionSort(vectorint nums){const int size nums.size();for(int i 0; i size-1; i){int minIndex i;for(int j i1; j size; j)if(nums[j] nums[minIndex])minIndex j;swap(nums[i], nums[minIndex]);}
}性能评价
简单选择排序是不稳定排序无论什么数据进去它的比较次数都是n(n-1)/2,所以时间复杂度是O(n^2)。
堆排序
首先将等待排序的数组构造成一个大根堆构造结束后整个数组当中的最大值就是堆顶元素 然后将堆顶元素与数组末尾元素交换位置交换结束后数组末尾元素为最大值剩下其他的待排序的数组个数为n-1个 将剩余的n-1个数再次构造成一个大根堆再将堆顶元素与数组第n-1个位置的元素交换位置重复上述步骤可以最终得到一个有序数组。
其实现代码如下
//堆调整
void Heapify(std::vectorint nums, int index, int heap_size){int parent_index index;int leftChild_index 2 * parent_index 1;while(leftChild_index heap_size){int maxValue_index leftChild_index1 heap_size nums[leftChild_index1] nums[leftChild_index] ? leftChild_index1 : leftChild_index;maxValue_index nums[maxValue_index] nums[parent_index] ? maxValue_index : parent_index;if(maxValue_index parent_index)return;std::swap(nums[maxValue_index], nums[parent_index]);parent_index maxValue_index;leftChild_index 2 * parent_index 1;}
}
//堆排序
void HeapSort(std::vectorint nums){if(nums.size() 2)return;int heap_size nums.size();//从下标最大的父节点开始。最后一个元素的下标是n-1最后一个父节点的下标是n/2-1for(int i heap_size/2 - 1; i 0; --i)Heapify(nums, i, heap_size);std::swap(nums[0], nums[--heap_size]);while(heap_size 0){Heapify(nums, 0, heap_size);std::swap(nums[0], nums[--heap_size]);}
}时间复杂度O(nlogn) 空间复杂度O(1) 稳定性不稳定
归并排序
简单归并排序即二路归并排序。
归并排序采用分治策略其本质框架类似二叉树的后序遍历左右子树的递归就是“分”根结点的处理部分就是“治”。 其实现代码如下
std::vectorint temp;
void MergeSort(std::vectorint nums, int left, int right){if(left right){return;}int mid left (right - left) / 2;//“分”MergeSort(nums, left, mid);MergeSort(nums, mid 1, right);//治int i left;int j mid 1;int t left;while(i mid j right){if(nums[i] nums[j]){temp[t] nums[i];}else{temp[t] nums[j];}}while(i mid){temp[t] nums[i];}while(j right){temp[t] nums[j];}for(int k left; k right; k){nums[k] temp[k];}
}时间复杂度O(nlogn) 空间复杂度O(n) 稳定性稳定
非比较类排序
基数排序
计数排序
桶排序
总结 不稳定排序记忆口诀一堆堆排序作业心态不稳快快速排序选择选择排序一些希尔排序朋友出去玩。
