<>1.排序概念:

排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

排序的稳定性:
两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则称该算法是具备稳定性的排序算法。

排序算法:实现原理,代码实现,分析算法稳定性,时间&空间复杂度,应用场景

<>插入排序:直接插入排序和希尔排序

<>直接插入排序:

原理:整个区间被划分为有序区间,无序区间。每次选择无序区间的第一个元素,在有序区间内选择合适的位置插入。
时间复杂度:O(N^2)
空间复杂度:O(1)
在排序时,没有用到辅助空间

空间复杂度:一个算法在运行期间需要空间和问题规模N的数学表达式
一个算法在运行期间是否借助:如果借助的辅助空间是常数(10,100,1000000)个空间→O1
如果借助的辅助空间是变量→newT[N]→O(N)
稳定性:稳定
插入排序应用场景:
比较耗费时间的操作:要搬移元素,如果搬移元素个数比较少,就比较适合插入排序 数列接近有序或者数据个数比较少
最有情况下:O(N)→数据有序
最差情况下:O(N^2)→数据逆序
实现:
public static void insertSort(int[] array){ for(int i=1;i<array.length;i++){
//有序区间:[0,i] //无序区间:[i,array.lenght] int v=array[i]; //无序区间的第一个数 int j=i-1;
//不写array[j]==v是保证排序的稳点性 for(j>=0&&array[j]>v;j--){ array[j+1]=array[j]; } array
[j+1]=v; } }
<>希尔排序

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

性能分析:

稳定性:不稳定
实现:
public static void shellSort(int[] array){ int gap=array.length; while(gap>1){
insertSortGap(array,gap); gap=(gap/3)+1; } insertSortGap(array,1); } private
static void insertSortGap(int[] array,int gap){ for(int i=1;i<array.length;i++){
int v=array[i]; int j=i-gap; for(;j>=0&&array[j]>v;j-=gap){ array[j+gap]=array[j
]; } array[j+gap]=v; } }
<>选择排序

<>选择排序

概念:每一次从无序区间选出最大(或最小)的一个元素,存放在无序区间的最后(或最前),直到全部待排序的数据元素排完

实现:
public static void selectSort(int[] array){ for(int i=0;i<array.length-1;i++){
int max=0; for(int j=1;j<array.length-i;j++){ if(array[j]>array[max]){ max=j; }
} int t=array[max]; array[max]=array[array.length-i-1]; array[array.length-i-1]=
t; } }
性能分析:

<>堆排序

原理:基本原理也是选择排序,只是不再使用遍历的方式查找无序区间的最大的数,而是通过堆来选择无序区间的最大的数。 注意:排升序要建大堆;排降序要选小堆。
实现:
public static void heapSort(int[] array){ createHeap(array); for(int i=0;i<
array.length-1;i++){ swap(array,0,array.length-1); shiftDown(array,array.length-
i-1,0); } } private void swap(int[] array,int i,int j){ int t=array[i]; array[i]
=array[j]; array[j]=t; } private void createHeap(int[] array){ for(int i=(array.
length-1)/2;i>=0;i--){ shiftDown(array,array.length,i); } } public static void
shiftDown(int[] array,int size,int index){ int left=2*index+1; while(left<size){
int max=left; int right=2*index+2; if(right<size){ if(array[right]>array[left]){
max=right; } } if(array[index]>=array[max]){ break; } int t=array[index]; array
[index]=array[max]; array[max]=t; index=max; left=2*index+1; } }
性能分析:

稳点性:不稳定

技术
©2019-2020 Toolsou All rights reserved,
Vue 中获取下拉框的文本及选项值(精华)2020年6月26日 C#类库 循环执行帮助类判断当前对象是不是数组的4种方式11-5 指定位置输出字符串笔记十四:研发管理中激励他人的第二大障碍keras数据生成器--数据增强科幻成真!“三体”被发现了(精华)2020年6月26日 C#类库model PageInput 艾伟也谈项目管理,基层管理杂谈最短路径Dijkstra (Python3)