大家好,本文主要讲java中几种常见排序算法的总结。有兴趣的同学过来看看。如果对你有帮助,记得收藏。
目录
本节的目标;【插入排序】【优化版】【希尔排序】【选择排序】【栈排序】【冒泡排序】介绍一种冒泡排序的优化方法;【快速排序】【合并排序】【正文】【代码介绍;】 【排序汇总】
本节目标;
本文分析了常用比较排序算法的基本原理和实现方法。
:分析排序算法的性能。
:分析Java中常见的排序方法
1 排序
排序是根据一个或一些关键字的大小,将一串记录按升序或降序排列的操作。
在通常的上下文中,排序通常是指升序。
2 稳定性
两个相同的数据,如果排序算法能保证排序后它们的相对位置不变,就说该算法具有稳定分布。
【插入排序】
【优化版】
分析步骤;
第一步;将第一个元素的index设置为I,让index和I指向同一个元素。
在第二部分中,J循环用于查找除第一个元素之外的最小元素,并将其交给索引。
第三步是与第一个元素交换索引。
public static void insert sort(int[]array){
for(int I=1;I数组.长度;i ) {
int tmp=array[I];
int j=I-1;
for(;j=0;j - ) {
if(array[j] tmp) {
array[j 1]=array[j];
}否则{
//array[j 1]=tmp;只要J后退,遇到比tmp小的元素就结束这个比较。
打破;
}
}
//j回落到小于0。
array[j 1]=tmp;
}
}
【希尔排序】
(基于知识的面试很少被测试)
【分析步骤 】
【选择排序】
分析步骤;
第一步;将第一个元素的index设置为I,让index和I指向同一个元素。
在第二部分中,J循环用于查找除第一个元素之外的最小元素,并将其交给索引。
第三步是与第一个元素交换索引。
【堆排序】
注释 !其基本原理还是排序.只其用堆来进行无序间排序,不用遍历进行排序
公共静态void createHeap(int[] array) {
for(int parent=(array . length-1-1)/2;父0;parent-){///设置父节点。
shiftDown(array,parent,array . length);//
}
}
public static void shift down(int[]array,int parent,int len) {
int child=2 * parent 1;//设置子节点
while(子len) {
if(child 1 len array[child]array[child 1]){
孩子;//如果有两个子节点,找到两个子节点中最大的一位。
}
if (array[child] array[parent]) {
swap(数组,父,子);//交换父节点和子节点
父母=孩子;//重新设置父节点
子代=2 *父代1;
}否则{
打破;
}
}
}
公共静态void堆排序(int[] array) {//
createHeap(数组);
int end=array . length-1;//每次交换后,从最后一个位元素中减去一位。
while(end 0){
swap(数组,0,end);
shiftDown(array,0,array . length-1);//在此循环中向下转换
end-;
}
}
【冒泡排序】
注释;它可能是几种相对简单的分类之一。
介绍一个冒泡排序的优化方法;
【快速排序】
原理简介-总览
1从要排序的区间中选择一个数字作为参考值(pivot)。
2分区:遍历整个待排序区间,将小于基准的(可以与基准相同)放在基准左侧,大于基准的(可以与基准相同)放在基准右侧。
3.采用分而治之的思想,对左右单元格同样处理,直到单元格之间的长度等于1;它代表顺序,如果长度==0,它代表没有元素。
public static void quick(int[]array,int left,int right) {
If( left=right) {//判断不满足递归条件,退出。
返回;
}
int pivot=partition(数组,左,右);//找到参考值
quick( array,left,pivot-1);//在左侧递归
quick(数组,pivot 1,右);//在右侧递归
}
私有静态int分区(int[] array,int start,int end) {
int tmp=array[start];
while(开始结束){//
while(start end array[end]tmp){//当end值大于tmp时,递减end下标。
end-;
}
数组[开始]=数组[结束];//在右侧遇到小于tmp的元素进行交换
while(start end array[start]tmp){//先从头比较,交换不到tmp小时。
开始;
}
数组[结束]=数组[开始];
}
array[end]=tmp;
返回结束;
}
public static void quick sort(int[]array){
quick(array,0,array . length-1);
}
}
}
【归并排序】
原则-概述
归并排序是一种基于归并操作的有效排序算法,是分而治之的典型应用。组合有序子序列以获得完全有序的序列;也就是说,首先对每个子序列进行排序,然后对子序列段进行排序。如果两个有序表合并成一个有序表,称为双向合并。
在此之前,请复习(链表)【合并两个有序链表】(合并排序的基础)。
public static int[]merge array(int[]array 1,int[] array2) {
//注意判断参数
int[]tmp=new int[array 1 . length array 2 . length];
int I=0;
int S1=0;
int E1=array 1 . length-1;
int S2=0;
int E2=array 2 . length-1;
while( s1e1 s2e2){
if(array1[s1] array2[s2]){
tmp[I]=array 1[S1];
}
if(array1[s1] array2[s2]){
tmp[I]=array 2[S2];
}
}
while( s1=e1){
tmp[I]=array 1[S1];
}
while( s2=e2){
tmp[I]=array 2[S2];
}
返回tmp
【正文】
【代码简介;】
public static void merge sort 1(int[]array){
mergeSortInternal(array,0,array . length-1);
}
private static void mergeSortInternal(int[]array,int low,int high) {
if(低高){
返回;
}
int mid=(低(高-低))/2;//寻找数组的中间位置分为左右两部分
mergeSortInternal( array,low,mid-1);//递归排序左边部分
mergeSortInternal( array,mid 1,high);//递归排序正确的部分
合并(数组,低,中,高);//合并这两个部分
}
私有静态void merge(int[] array,int low,int mid,int high) {
int[]tmp=new int[array . length];//创建一个新数组
int s1=低电平;
int e1=mid
int S2=mid 1;
int e2=高;
int I=0;
While(s1e1 s2e2){//循环的条件
if(array[s1] array[s2]){
tmp[I]=array[S1];
}否则{
tmp[I]=array[S2];
}
}
While(s1 s2){//当这一步显示左侧长于右侧时,将左侧剩余部分加入数组。
tmp[I]=array[S1];
}
while(s2 e2){
tmp[I]=array[S2];//当这一步显示左侧长于右侧时,将左侧剩余部分加入数组。
}
for(int j=0;j I;J ){//将tmp数组中的元素放入array数组中
array[I low]=tmp[j];
}
【排序总结】
以上就是本文对java中几种常见排序算法的总结。更多相关的java排序算法,请搜索我们之前的文章或者继续浏览下面的相关文章。希望大家以后能多多支持我们!
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。