2022年数据库的算法参照 .pdf-得力文库

资源描述

《2022年数据库的算法参照 .pdf》由会员分享，可在线阅读，更多相关《2022年数据库的算法参照 .pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

2、冒泡排序为一列数字进行排序的过程分类排序算法数据结构数组最差时间复杂度O(n2)最优时间复杂度O(n)平均时间复杂度O(n2)最差空间复杂度O(n) total, O(1) auxiliary public static void sort(Comparable a) int N = a.length; for(int i=0;i0;j-) if(pareTo(aj-1)=-1) exchange(a,j,j-1); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1

3、页，共 7 页 - - - - - - - - - break; 交换位置：public static void change(Comparable a,int from,int to) Comparable t = afrom; afrom = ato; ato = t; 判断是否已经有序：public static boolean isSorted(Comparable a) for(int i=1;ia.length;i+) if(pareTo(ai-1)=-1) return false; return true 2. 选择排序：名师资料总结 - - -精品资料欢迎下载 - - -

4、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 分类排序算法数据结构数组最差时间复杂度(n2) 最优时间复杂度(n2) 平均时间复杂度(n2)最差空间复杂度(n) total, O(1) auxiliary public static void change(Comparable a) int N = a.length; for(int i=0;iN;i+) int min = i; for(int j=i+1;jN;j+) if(paraeTo(amin)=-1) min

5、 = j; exchange(a,i,min); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 时间复杂度：比较的次数：(n-1)+(n-2)+.+1+0N2/2 交换的次数：N 时间复杂度是：N2/2+NN2/2 3. 插入排序：public static void change(Comparable a) int N = a.length; for(int i=0;i0;j-) if(pareTo(aj-1)=-1) ex

6、change(a,j,j-1); else break; 时间复杂度：比较次数： N2/4 交换次数： N2/4 时间复杂度是：N2/2 极端情况：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 如果序列是排好序的，那么比较的次数是N-1 交换的次数是0 如果序列是随即的，那么比较的次数是N2/2 交换的次数是N2/2 4. 希尔排序 (shell sort) public static void sort(Comparable

7、 a) int N = a.length; int incs = 1391376,463792,198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1; for(int k=0;kincs.length;i+) int h = incsk; for(int i=h;i=h;j-=h) if(pareTo(aj-h) exchage(a,j,j-h); else break; 时间复杂度：n(3/2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

8、 - - - - - 第 5 页，共 7 页 - - - - - - - - - 5. 堆排序分类排序算法数据结构数组最差时间复杂度O( nlogn )最优时间复杂度O(nlogn )1平均时间复杂度 ( nlogn ) 最差空间复杂度O( n) total, O(1) auxiliary 6. 快速排序使用快速排序法对一列数字进行排序的过程分类排序算法数据结构 Varies 最差时间复杂度( n2)最优时间复杂度( nlog n )平均时间复杂度( nlog n) comparisons 最差空间复杂度根据实现的方式不同而不同public class Quicksort publi

9、c static final Random RND = new Random(); private void swap(Object array, int i, int j) Object tmp = arrayi; arrayi = arrayj; arrayj = tmp; private int partition(Object array, int begin, int end, Comparator cmp) int index = begin + RND.nextInt(end - begin + 1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

10、 - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - Object pivot = arrayindex; swap(array, index, end); for (int i = index = begin; i end; + i) if (pare(arrayi, pivot) begin) int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); public void sort(Object array, Comparator cmp) qsort(array, 0, array.length - 1, cmp); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -

展开阅读全文