插入排序和归并排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了插入排序和归并排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2520字,纯文字阅读大概需要4分钟。
内容图文
插入排序思想:在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使这n个数也是排好顺序的。如此反复循环,直到全部排好顺序.(当待排序数据全部有序时,时间复杂度为O(N),最坏情况下时间复杂度为O(N*N),与待排序数据的状态有关).
public class InsertSort {
public static void insertSort(int[] arr) {
if(arr == null || arr.length < 2)
return ;
for(int i = 1; i < arr.length; i++) {
for(int j = i -1; j >= 0 && arr[j] > arr[j+1]; j--)
swap(arr, j , j+1);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = new int[] {3,434,24,656,57,54,88,66};
System.out.print("原始数组:");
for(int i = 0; i < arr.length; i++)
if(i != arr.length - 1)
System.out.print(arr[i] + " ");
else
System.out.println(arr[i]);
insertSort(arr);
System.out.print("插入排序后:");
for(int i = 0; i < arr.length; i++)
if(i != arr.length - 1)
System.out.print(arr[i] + " ");
else
System.out.println(arr[i]);
}
}
运行结果:
归并排序思想:归并排序是利用归并的思想实现的排序方法,即分治法,分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案合在一起,即分而治之。
public class MergeSort {
public static void mergeSort(int[] arr) {
if(arr == null || arr.length < 2)
return ;
sortProgress(arr, 0, arr.length - 1);
}
public static void sortProgress(int[] arr, int L, int R) {
if(L == R)
return ;
int mid = L + ((R - L) >> 1);
sortProgress(arr, L, mid);
sortProgress(arr, mid+1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R){
int[] help = new int[R- L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while(p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2]? arr[p1++]: arr[p2++];
}
while(p1 <= mid) {
help[i++] = arr[p1++];
}
while(p2 <= R) {
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++)
arr[L + i] = help[i];
}
public static void main(String[] args)
{
int[] arr = new int[] {45,3,5445,34,676,545,66,88};
System.out.print("原始数组:");
for(int i = 0; i < arr.length; i++)
if(i != arr.length - 1)
System.out.print(arr[i] + " ");
else
System.out.println(arr[i]);
mergeSort(arr);
System.out.print("归并排序后:");
for(int i = 0; i < arr.length; i++)
if(i != arr.length - 1)
System.out.print(arr[i]+" ");
else
System.out.println(arr[i]);
}
}
运行结果:
插入排序优点:稳定排序
缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候
归并排序优点:效率高,时间复杂度为O(N*logN),是一种稳定的算法.
缺点:归并排序需要O(n)的辅助空间,而与之效率相同的快排和堆排分别需要O(logn)和O(1)的辅助空间,在同类算法中归并排序的空间复杂度略高
内容总结
以上是互联网集市为您收集整理的插入排序和归并排序全部内容,希望文章能够帮你解决插入排序和归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。