保定网站关键词优化,好用的网站开发软件,租服务器 wordpress,无经验做网站排序分为内部排序和外部排序#xff08;外部存储#xff09;
常见的七大排序#xff0c;这些都是内部排序 。 1、插入排序#xff1a;直接插入排序
1、插入排序#xff1a;每次将一个待排序的记录#xff0c;按其关键字的大小插入到前面已排序好的记录序列 中的适当位置…排序分为内部排序和外部排序外部存储
常见的七大排序这些都是内部排序 。 1、插入排序直接插入排序
1、插入排序每次将一个待排序的记录按其关键字的大小插入到前面已排序好的记录序列 中的适当位置直到全部记录插入完成为止。稳定排序算法 一个排序算法的稳定性与不稳定性是通过排序后相同元素的先后顺序 来判断的。 稳定性如果排序前后具有相同关键字的元素的相对顺序没有改变则排序算法被认为是稳定的。 不稳定性如果排序前后具有相同关键字的元素的相对顺序发生了改变则排序算法被认为是不稳定的。 从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后往前扫描如果该元素已排序大于新元素将该元素移到下一位置直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后这就保证了相同元素的顺序和排序前一样所以是稳定排序 重复扫描
2、代码
public class InsertSort {
/**
*
* method: insertSort
* Param: [arr]
* Return: void
* exception:
* Author: fsy
* Date: 19-5-29 下午3:50
* description:
*
*/
public void insertSort(int[] arr){//需要插入的数int insertNum;for (int i1; i arr.length ; i) {insertNumarr[i];//序列元素个数int ji-1;//将大于insertNum的元素往后移动while (j0arr[j]insertNum){arr[j1]arr[j];j--;}//找到位置插入当前元素arr[j1]insertNum;}}3、复杂度分析
时间复杂度
On²
空间复杂度
O1
4、总结
插入排序所需的时间取决于输入元素的初始顺序 。对于一个很大且其中的元素已经有序或接近有序的数组进行排序将会比随机顺序的数据或是逆序数据进行排序要快的多
2、插入排序希尔排序
1、希尔排序希尔排序的本质就是分组插入排序 又称缩小增量法。将整个无序序列分割成若干个子序列由相隔某个“增量”的元素组成分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序时再对全体元素进行一次直接插入排序 。因为进行直接插入排序时元素基本有序所以效率是很高的因此希尔排序在时间效率上有很大提高。希尔排序是不稳定排序算法
2、代码
public void shellSort(int[] d) { //d[]为增量数组RecordNode temp;int i, j;System.out.println(希尔排序);//控制增量增量减半若干趟扫描for (int k 0; k d.length; k) {//一趟中若干子表每个记录在自己所属子表内进行直接插入排序int dk d[k];for (i dk; i this.curlen; i) {temp r[i];for (j i - dk; j 0 temp.key.compareTo(r[j].key) 0; j - dk) {r[j dk] r[j];}r[j dk] temp;}System.out.print(增量dk dk );}
}3、复杂度分析
时间复杂度
Onlog2 n
空间复杂度
O1
4、总结
希尔排序更高效是因为它权衡了子数组的规模和有序性。排序之初各个子数组都很短排序之后子数组都是部分有序的这两种情况都很适合插入排序
3、选择排序简单选择排序
1、选择排序工作原理如下。首先在未排序序列中找到最小大元素存放在排序序列的初始位置。然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序列的末尾以此类推直到所有元素排序完毕。选择排序的主要优点是与数据移动有关如果某个元素位于正确的最终位置上则它不会被移动。选择排序每次交换一对元素它们当中至少有一个将被移到其最终位置上因此对n个元素的表进行排序最多n-1次交换。不稳定排序
2、代码
public static void sort(int[] a) {for (int i 0; i a.length; i) {int min i;//选出之后待排序中值最小的位置for (int j i 1; j a.length; j) {if (a[j] a[min]) {min j;}}//最小值不等于当前值时进行交换if (min ! i) {int temp a[i];a[i] a[min];a[min] temp;}}
}3、复杂度分析
时间复杂度
On²
空间复杂度
O1
4、总结
选择排序非常简单和直观但是也非常慢。无论是哪种情况哪怕原数组已经排序完成它也将花费将近n²/2次遍历来确认一遍。它的排序结果也是不稳定的。不耗费额外的内存空间
4、选择排序堆排序
1、堆的定义如下n个元素的序列k1k2… kn
当且仅当满足下列关系时称之为堆 把此序列对应的二维数组看成是一个完全二叉树那么堆的含义就是完全二叉树中任何一个非叶子节点的值均不大于或不小于其左、右孩子节点的值 。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可以使用大顶堆进行升序排序使用小顶堆进行降序排序。不稳定排序
基本思想以大顶堆为例堆排序的过程就是将待排序的序列构造成一个堆选出堆中最大的移走再把剩余的元素调整成堆找出最大的再移走重复直至有序
2、代码
/*** param a*/
public static void sort(int[] a) {for (int i a.length - 1; i 0; i--) {max_heapify(a, i);//堆顶元素(第一个元素)与Kn交换int temp a[0];a[0] a[i];a[i] temp;}
}/***** 将数组堆化* i 第一个非叶子节点。* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。* 叶子节点可以看作已符合堆要求的节点根节点就是它自己且自己以下值为最大。** param a* param n*/
public static void max_heapify(int[] a, int n) {int child;for (int i (n - 1) / 2; i 0; i--) {//左子节点位置child 2 * i 1;//右子节点存在且大于左子节点child变成右子节点if (child ! n a[child] a[child 1]) {child;}//交换父节点与左右子节点中的最大值if (a[i] a[child]) {int temp a[i];a[i] a[child];a[child] temp;}}
}
3、复杂度分析
时间复杂度Onlog₂ n
空间复杂度O1
4、总结
由于堆排序中初始化堆的过程比较次数较多因此不太使用于小序列 。由于多次任意下标相互交换位置相同元素之间原本相对的顺序被破坏了是不稳定排序。
5、交换排序冒泡排序
1、冒泡排序是一种简单排序。重复地走访过要排序的元素一次比较两个元素如果他们的顺序错误就把他们交换过来走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。只在顺序不符合大小要求时交换所以不会破坏相同元素间的顺序因此是稳定排序
比较相邻的元素如果第一个比第二个大就交换他们两个对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对这步做完最后的元素会是最大的数针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
2、代码
public static void sort(int[] a) {//外层循环控制比较的次数for (int i 0; i a.length - 1; i) {//内层循环控制到达位置for (int j 0; j a.length - i - 1; j) {//前面的元素比后面大就交换if (a[j] a[j 1]) {int temp a[j];a[j] a[j 1];a[j 1] temp;}}}
}
3、复杂度分析
时间复杂度
最好On最坏On²平均时间复杂度On²
空间复杂度O1
4、总结
是稳定的排序算法。
6、交换排序快速排序
1、快速排序使用分治法策略来把一个串行分为两个子串行。通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。不稳定排序算法
2、代码
public static void sortByStack(int[] a) {StackInteger stack new StackInteger();//初始状态的左右指针入栈stack.push(0);stack.push(a.length - 1);while (!stack.isEmpty()) {//出栈进行划分int high stack.pop();int low stack.pop();int pivotIndex partition(a, low, high);//保存中间变量if (pivotIndex low) {stack.push(low);stack.push(pivotIndex - 1);}if (pivotIndex high pivotIndex 0) {stack.push(pivotIndex 1);stack.push(high);}}
}private static int partition(int[] a, int low, int high) {if (low high) return -1;int left low;int right high;//保存基准的值int pivot a[left];while (left right) {//从后向前找到比基准小的元素插入到基准位置中while (left right a[right] pivot) {right--;}a[left] a[right];//从前往后找到比基准大的元素while (left right a[left] pivot) {left;}a[right] a[left];}//放置基准值准备分治递归快排a[left] pivot;return left;
}
3、复杂度分析
时间复杂度
最好Onlog₂ n最坏On²平均时间复杂度Onlog₂ n
空间复杂度O1
7、归并排序
1、归并排序归并排序算法是将两个或两个以上有序表合并成一个新的有序表即把待排序序列分为若干个子序列每个子序列是有序的然后再把有序子序列合并为整体有序序列。稳定排序算法
归并排序可通过两种方式实现
自上而下的递归自下而上的迭代
2、递归的方法代码
public class Merge {//归并所需的辅助数组private static int[] aux;public static void sort(int[] a) {//一次性分配空间aux new int[a.length];sort(a, 0, a.length - 1);}public static void sort(int[] a, int low, int high) {if (low high) {return;}int mid (low high) / 2;//将左半边排序sort(a, low, mid);//将右半边排序sort(a, mid 1, high);merge(a, low, mid, high);}/*** 该方法先将所有元素复制到aux[]中然后在归并会a[]中。方法咋归并时(第二个for循环)* 进行了4个条件判断* - 左半边用尽(取右半边的元素)* - 右半边用尽(取左半边的元素)* - 右半边的当前元素小于左半边的当前元素(取右半边的元素)* - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)*/public static void merge(int[] a, int low, int mid, int high) {//将a[low..mid]和a[mid1..high]归并int i low, j mid 1;for (int k low; k high; k) {aux[k] a[k];}for (int k low; k high; k) {if (i mid) {a[k] aux[j];} else if (j high) {a[k] aux[i];} else if (aux[j] aux[i]) {a[k] aux[j];} else {a[k] aux[i];}}}}
3、复杂度分析
时间复杂度O(nlog₂n)
空间复杂度On
4、总结主要缺点是所需的额外空间和N成正比N为待排序数组的长度
8、总结
各种排序性能对比
排序类型平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定直接插入排序O(n²)O(n)O(n²)O(1)稳定折半插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)不稳定归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定快速排序O(nlog₂n)O(nlog₂n)O(n²)O(nlog₂n)不稳定堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定计数排序O(nk)O(nk)O(nk)O(k)稳定桶排序O(nk)O(nk)O(n²)O(nk)(不)稳定基数排序O(d(nk))O(d(nk))O(d(nkd))O(nkd)稳定
稳定冒泡排序、直接插入排序、归并排序
不稳定选择排序、希尔排序、快速排序、堆排序
