c 网站开发框架,设计网页公司哪里好,做网站美工要学什么,莱芜人才网最新招聘目录 插入排序
希尔排序
归并排序
快速排序 插入排序
排序原理#xff1a;
1.把所有元素分为两组#xff0c;第一组是有序已经排好的#xff0c;第二组是乱序未排序。
2.将未排序一组的第一个元素作为插入元素#xff0c;倒序与有序组比较。
3.在有序组中找到比插入…目录 插入排序
希尔排序
归并排序
快速排序 插入排序
排序原理
1.把所有元素分为两组第一组是有序已经排好的第二组是乱序未排序。
2.将未排序一组的第一个元素作为插入元素倒序与有序组比较。
3.在有序组中找到比插入元素小或者大的元素将插入元素放入该位置后面元素向后移动一位。 时间复杂度O(n^2)
稳定性当A与B相等排序前A若在B前排序后A仍然在B前就说明该排序是稳定的。
插入排序稳定 //比较两元素大小方法private static boolean greater(Comparable v,Comparable w){return v.compareTo(w)0;} //数组中 交换元素位置private static void exch(Comparable[] a,int i,int j){Comparable temp;temp a[i];a[i] a[j];a[j] temp;}
插入排序 public static void insertSort(Comparable[] a){for (int i 1; i a.length-1; i) {for (int j i1; j 0; j--) {if (greater(a[j-1],a[j])){exch(a,j-1,j);}else break;}}}
希尔排序
排序原理
1.选择一个增长量h按照h将数据分组。
2.每组进行插入排序。
3.减少增长量h直到h1重复步骤2
稳定性不稳定 public static void shellSort(Comparable[] a){int h 1;//确定hwhile (ha.length/2){h 2*h1;}// 希尔排序while (h1){for (int i h; i a.length; iih) {for (int j i; j h; jj-h) {if (greater(a[j-h],a[j])){exch(a,j-h,j);}else break;}}hh/2;}}
归并排序
排序原理
1.尽可能的一组数据拆分成两个元素相等的子组并对每一个子组继续拆分直到拆分后的每个子
组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组
3.不断的重复步骤2直到最终只有一个组为止。
时间复杂度O(nlogn)
稳定性 稳定 import java.util.Arrays;public class Merge {//归并需要的辅助数组private static Comparable[] assist;//判断v是否比w小private static boolean less(Comparable v,Comparable w){return v.compareTo(w)0;}//交换元素private static void exch(Comparable[] a,int i,int j){Comparable t a[i];a[i] a[j];a[j] t;}//对数组a排序public static void sort(Comparable[] a){// 1.初始化辅助数组assistassist new Comparable[a.length];// 定义lo变量和hi变量。分别记录数组中最小的索引和最大的索引int lo 0;int hi a.length-1;sort(a,lo,hi);}//对数组a中从lo到hi元素进行排序private static void sort(Comparable[] a,int lo,int hi){//安全检验if (hilo){return;}// 对lo和hi之间的数据进行分为两组int mid lo(hi-lo)/2;// 分别排序sort(a,lo,mid);sort(a,mid1,hi);//两组归并merge(a,lo,mid,hi);}//归并private static void merge(Comparable[] a,int lo,int mid,int hi){// 定义三个指针int i lo;int p1 lo;int p2 mid1;// 遍历移动p1指针和p2指针比较对应 索引处的值找出小的放到辅助数组对应分索引处while (p1midp2hi){if (less(a[p1],a[p2])){assist[i] a[p1];}else {assist[i] a[p2];}}//遍历如果p1的指针没有走完将p1剩余遍历到辅助数组中while (p1mid){assist[i] a[p1];}//遍历如果p2的指针没有走完将p2剩余遍历到辅助数组中while (p2hi){assist[i] a[p2];}// 把辅助数组中的元素复制到原数组中for (int index lo;indexhi;index){a[index] assist[index];}}public static void main(String[] args) {Integer[] a{7,8,4,5,6,1,3,9,2};Merge.sort(a);System.out.println(Arrays.toString(a));// [1, 2, 3, 4, 5, 6, 7, 8, 9]}}快速排序
排序原理 1.首先设定一个分界值通过该分界值将数组分成左右两部分
2.将大于或等于分界值的数据放到到数组右边小于分界值的数据放到数组的左边。此时左边部分
中各元素都小于或等于分界值而右边部分中各元素都大于或等于分界值
3.然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分
数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处
理。 4.重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧
部分的顺序。当左侧和右侧两个部分的数据排完序后整个数组的排序也就完成了。
时间复杂度
平均情况O(nlogn)最坏情况O(n^2)
稳定性不稳定 import java.util.Arrays;public class Quick {private static void exch(Comparable[] a,int i,int j){Comparable t a[i];a[i] a[j];a[j] t;}private static boolean less(Comparable v,Comparable w){return v.compareTo(w)0;}//对数组内的元素进行排序public static void sort(Comparable[] a){int lo 0;int hi a.length-1;sort(a,lo,hi);}//对数组a中从索引hi之间的元素进行排序public static void sort(Comparable[] a,int lo,int hi){if (lohi)return;int partition partition(a,lo,hi);sort(a,lo,partition-1);sort(a,partition1,hi);}private static int partition(Comparable[] a,int lo,int hi){//确定分界值Comparable key a[lo];//定义两个指针分别指向待切分元素的最小索引处和最大索引处的下一个位置int left lo;int right hi1;//切分 扫描while (true){//先从右边向左扫描移动right指针找到比分界值小的停止while (less(key,a[--right])){if (rightlo){break;}}//从左边向右扫描移动light指针找到比分界值大的停止while (less(a[left],key)){if (lefthi){break;}}//rightright时交换if (leftright){break;}else {exch(a,left,right);}}//交换分界值exch(a,lo,right);return right;}public static void main(String[] args) {Integer a[] {3,6,9,2,5,8,4,7,1};Quick.sort(a);System.out.println(Arrays.toString(a));// [1, 2, 3, 4, 5, 6, 7, 8, 9]}}
