Java经典算法
•发布于   •作者 三国 - 魏  •376 次浏览  •最后一次编辑是   •来自 博客

1.插入排序

       核心思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。

      

public class InsertSort {
	public static void main(String[] args) {
		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
		for (int i = 1; i < a.length; i++) {
			int temp = a[i];
			int j;
			for (j = i - 1; j >= 0 && a[j] > temp; j--) {
				// 将大于temp的往后移动一位
				a[j + 1] = a[j];
			}
			a[j + 1] = temp;
		}
		System.out.println(Arrays.toString(a));
	}
}

2.选择排序

        核心思想:给数组下标找值,一层循环实现需要循环多少次才可以把数组排好序,第二层循环是找到最小的值放在要放置的位置。

   



public class SelectionSort {
	public static void main(String[] args) {
		int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
		for (int i = 0; i < a.length; i++) {
			int min = a[i];//默认第下标为i的数为最小值
			int minIndex = i;//存储最小值的索引
			for (int j = i; j < a.length; j++) {//从i索引处开始查找,找到最小值
				if (a[j] < min) {//如果查找到的当前值比最小值小,就把最小值赋值给min,最小值的索引给minIndex
					minIndex = j;
					min = a[j];
				}
			}
			if (minIndex != i) {//如果最小值索引被改变了,说明一开始默认的最小值并不是真正的最小值,把真正的最小值放到索引处
				int temp = a[i];
				a[i] = a[minIndex];
				a[minIndex] = temp;
			}
		}
		System.out.println(Arrays.toString(a));
	}
}

3.冒泡排序

          核心思想:原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,

public class BubbleSort {
	public static void main(String[] args) {
		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
		for (int i = 0; i < a.length; i++) {
			for (int j = i; j < a.length; j++) {
				if (a[i] > a[j]) {
					int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
				}
			}
		}
		System.out.println(Arrays.toString(a));
	}
}


4.希尔排序

           核心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2

public class ShellSort {
	public static void main(String[] args) {
		int[] arr = { 57, 68, 59, 52, 72, 28, 96, 33, 24, 19 };
		shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void shellSort(int[] arr) {
		int d = arr.length / 2;
		while (d > 1) {
			// 把距离为 d 的元素编为一个组,扫描所有组
			for (int i = d; i < arr.length; i++) {
				int key = arr[i];
				int f = i - d;
				// 对距离为 d 的元素组进行排序
				while (f >= 0 && arr[f] > key) {
					arr[f + d] = arr[f];
					f -= d;
				}
				arr[f + d] = key;
			}
			// 缩小增量
			d = d / 2;
		}
	}
}

5.归并排序

        核心思想:归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:

      1)对数组进行拆分

      2)把拆分的数组进行有序排列

public class MergeSort {
	 
    //归并排序,首选采用分而治之的思想,运用递归方法,将数组分组两半
    public static void guibing(int[] list)
    {
        int L=list.length;
        //将数组递归分成两部分
        if(L>1)
        {
            //第一部分为前一半元素
            int[] firstHalf=new int[L/2];
            //调用arrayCopy方法,将list中的前一半元素复制到firstHalf之中
            System.arraycopy(list, 0, firstHalf, 0, L/2);
            //递归:将这个子数组再分成两半
            guibing(firstHalf);
            //第二部分为后一半元素(不一定与第一部分元素个数相同)
            int[] secondHalf=new int[L-L/2];
            //调用arrayCopy方法,将list中的后一半元素复制到secondHalf之中
            System.arraycopy(list, L/2, secondHalf, 0, secondHalf.length);
            //递归:将这个子数组再分成两半
            guibing(secondHalf);
            //一旦所有的递归拆分都已经结束,那么进行归并
            int[]temp=merge(firstHalf,secondHalf);
            //将temp数组的所有元素复制到list之中
            //参数的含义:源数组,首索引,目标数组,首索引,复制长度
            System.arraycopy(temp, 0, list, 0, temp.length);
        }
    }
    //归并两个数组
    //因为两个数组已经是排序的,所以只需依次比较两个元素的对应值即可,"谁小就谁上"
    private static int[] merge(int[] list1,int[] list2)
    {
        //声明最终数组及长度
        int[] tmp=new int[list1.length+list2.length];
        //设置索引量初始化
        int current1=0,current2=0,current3=0;
        //当两个子数组均没有结束,需要比较它们的值
        while(current1if(list1[current1]tmp[current3++]=list1[current1++];
            else
                tmp[current3++]=list2[current2++];
        }
        //如果只剩下第一个子数组了,就直接把剩下的元素依次放入最终数组之中
        while(current1tmp[current3++]=list1[current1++];
        //如果只剩下第二个子数组了,就直接把剩下的元素依次放入最终数组之中
        while(current2tmp[current3++]=list2[current2++];
        //至此,合并结束,返回最终数组
        return tmp;
    }
    public static void main(String[] args) {
        //首先声明数组
    	int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        //归并排序
        guibing(a);
        //输出结果
        for(int element:a)
            System.out.print(element+"\t");
         
    }
 
}


4 回复
小新

厉害


慕慕

good   job!!!

=.=

哇 ,这图片好!!!容易理解!!

Choices()

题目挺好的,讲的也挺详细的,如果根据代码,只是如果用自己的思想载走一遍的话,还是有难度的,希望老师可以带我们再走一遍过程。 赞赞!!!

回到顶部

©2017 Powered by 三十三行伪代码
皖ICP备17005175号-3